Leetcode No.2(Reverse Integer) 心得

ChingYuanYang
Aug 22, 2017 · 5 min read

題目:
Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

Note:
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

想法:
用mod去得到每個數字,並倒轉順序再乘10的倍數。

(1) 由於有正負號,有鑒於 INT_MAX 和 INT_MIN 數字部位只差一 (2147483647 -2147483648),所以一律換成正數作處理,這裡要特別注意,-2147483648換成正數會overflow,要另外處理。

(2) 300 -> 3; 0 -> 0; 這種比較特別的也要特別注意。

(3) Overflow的話回傳0。這部分也是一個麻煩,我想的方法是判斷加上某個數字後會不會overflow,那要避免這個判斷就overflow的方法,就是 “INT_MAX - 目前的值 > 要加上的值”。
這個部份我在寫的過程有犯一個錯誤,就是在要拿來判斷的值在運算過程就overflow了,所以就看不出來會overflow。

Note: 我在設定 testcase_input x= -2147483648,遇到compiler不會過的問題,很有意思是遇到錯誤訊息:
錯誤 C4146 一元減號運算子套用 unsigned 類型,所得的結果也會是 unsigned 類型
後來發現 “-”負號這個運算子其實就是減號,是 A-B,所以當寫-2147483648會轉成 0-2147483648U,而2147483648 是 十位數常數並且沒有任何的字尾(ex: U, L),compiler會先嘗試 “fit in” int,然後 long,再來 long long,都沒有的話就是 undefined behavior。
以我的compiler訊息來看,他沒有找到能 fit in 的 type,所以轉成 unsigned int,但是 unsigned int 可以相減成為另外一個 unsigned int,但是不能減成負數,因此就報錯了。結論是要寫成 x= -2147483647 -1;
所以定義 #INT_MIN -2147483647-1 而不是 #INT_MIN -2147483648

下面列出我的程式,落落長。

class Solution {
public:
int reverse(int x) {
int target = 0;
int mod;
int mul = 10;
int rev[32];
int count = 0;

bool flag = 0;
if (x == (-2147483647–1))
return 0;
else if (x < 0) {
x = -x;
flag = 1;
} else if (x == 0)
return 0;
for (int i = 0; i < 32; i++)
rev[i] = -1;
while (x > 0) {
mod = x % 10;
rev[count] = mod;
x = x — mod;
x = x / 10;
count++;
}
count — ;

mul = 1;
while (count > -1) {
if (mul != 1000000000)
target = target + rev[count] * mul;
else {
if (rev[count] > 2) return 0;
if ((2147483647 — target) < rev[count] * mul)
return 0;
else
target = target + rev[count] * mul;
}

mul = mul * 10;
count — ;
}

if (flag == 1)
target = -target;
return target;
}
};

其他人解法:
看了其他人解法,比我的簡潔容易懂,但是可能我有一些 hard code,所以我的程式慢。

改進方法:
(1) 負數被 mod 之後還是負數,這點很好用,就不用特地轉成正數來算。
(2) 我倒轉數字的方法是一個個digit乘以該digit的位數。網路上有很好的方法是每找到一個digit就乘以10,這個會簡潔很多。
ex: Target = old_Target * 10 + x % 10
14528 -> X
1452 -> 8
145 -> 82
14 -> 825
1 -> 8254
X -> 82541

(3) 判斷 overflow的方法: 這道題會 overflow 的部分在於加上倒轉數字和位數的時候 overflow , ex: target = old_target * 10 + newDigit。
因為overflow會把超過的部分抹掉,所以如果 (target-newDigit)/10 != old_target 就是 overflow。
一開始我心存懷疑,寫程式暴力搜尋,真的找不到反例,雖然沒辦法證明,但是因為overflow後會讓超過部分消失,也就是值會變小,因此這個不等式應該是可以拿來判斷。

答案:
class Solution {
public:
int reverse(int x) {
int ans = 0;
while (x) {
int temp = ans * 10 + x % 10;
if (temp / 10 != ans)
return 0;
ans = temp;
x /= 10;
}
return ans;
}
};

)