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.

tag: math

9/25/2015 update

//how to deal with overflow?
//0 should be reversed to 0
//10000 => 1
class Solution {
public:
    int reverse(int x) {
        int flag = x < 0? -1: 1;
        x = x * flag;
        long ans = 0;
        while(x / 10){
            int digit = x % 10;
            ans = ans * 10 + digit;
            x = x / 10;
        }
        ans = ans * 10 + x;
        ans = ans * flag;
        if(ans < (int)0x80000000 || ans > (int)0x7fffffff){
            ans = 0;
        }
        return (int)ans;
    }
};

Leetcode上有很多关于math的题，都被标为了easy，虽然我并不认为math的题简单，即使不涉及任何复杂的数据结构，但却足以做成脑筋急转弯。

关于此题，reverse部分，我直接转化成了字符串，检查然后交换字符，再将字符串转换成数字。

其中，stoll函数会自动正确转化例如-00002这样的字符串为-2.如果自己写转化函数的话，需要注意处理这种情况。

关于数字溢出，我用了个偷懒的方法，直接转换成long long 64位，如果大于0x7FFFFFFF或者小于0x80000000的话，则判为数字溢出。

这里有同学可能会问，如果我的输入也是64位呢？

Leetcode官方solution给出了一种解法。

在转换后的字符串的最低位转换成数字之前，（也即缩小十倍）将它和214748364比较，如果大于214748364或小于-214748364的话，则判为溢出。如果等于214748364的话，那么则比较最低位和7的关系，进一步判断是否溢出。

To check for overflow/underflow, we could check if ret > 214748364 or ret < –214748364 before multiplying by 10. On the other hand, we do not need to check if ret == 214748364, why?

class Solution {
public:
    int reverse(int x) {
        long long maxNum = 0x7FFFFFFF;//2147483647
        string s = to_string(x);
        reverse(s);
        long long reversedNum = stoll(s);
        if (reversedNum > maxNum || reversedNum < -maxNum){
            return 0;
        }
        else{
            return (int)reversedNum;
        }
    }
    void reverse(string& s){
        int start = 0;
        int end = s.size() - 1;
        if(s[0] == '-'){
            start = 1;
            end = s.size();
        }
        for(int i = start; i < end - i; i++){
            char tmp = s[i];
            s[i] = s[end - i];
            s[end - i] = tmp;
        }
    }
};