[Leetcode]Reverse Integer

[Leetcode]Reverse Integer

Reverse digits of an integer.

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

click to show spoilers.

Have you thought about this?

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Update (2014-11-10):

Test cases had been added to test the overflow behavior.

這道題11月10號有一個更新，加上了反轉會溢出的test case。因此要把這一部分數找出來，然後喀嚓掉，返回0。

這裡先上沒更新前的AC代碼，供大家先熟悉思路。

class Solution {
public:
    int reverse(int x) {
        int flag = (x > 0) ? 1:-1;
        int y =abs(x);
        int result = 0;
        while(y){
            result = result*10 + y%10;
            y = y/10;
        }
        return flag*result;
    }
};

思路很簡單，就是取最後一位加到result上，然後乘以10，如此往復，取到原數的最高位，加到result上，result的最高位正好是原數的最低位。

但是現在問題來了，如果原數的反轉數溢出的話，這樣寫就錯了。

那現在想一下，只要得到的反轉數比INT_MAX大，就會溢出，這個數在內存中就變了，所以沒辦法比較它和INT_MAX的大小。所以這裡換一種思路，比較上一步結果和INT_MAX/10的大小，如果某一步result比INT_MAX/10大，並且這時y > 0，那麼結果就會溢出。

這個代碼AC了，但是仔細想想會帶幾個間諜進來。如果某個數，翻轉的倒數第二個結果result == INT_MAX/10，並且剩下的最高位y>INT_MAX%10,也會溢出，所以也許要把這一部分排除掉。

這個方法其實就是在原來的方法上打了個補丁，實在想不出更好的辦法了。

還有一個就是INT_MIN需要排除掉，這貨取絕對值後比INT_MAX大1，直接溢出了。

class Solution {
public:
    int reverse(int x) {
        if(x == INT_MIN) return false;
        int flag = (x > 0) ? 1:-1;
        int y =abs(x);
        int result = 0;
        while(y){
            result = result*10 + y%10;
            y = y/10;
            if(result>(INT_MAX/10)&&y > 0 || result==(INT_MAX/10)&&y>INT_MAX%10) return false;
        }
        return flag*result;
    }
};

希望能拋磚引玉，大家如果想到更好的方法記得告訴我。