[LeetCode] Reverse Integer

Reverse digits of an integer.

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

思路:

凡是整数操作类的题目，都需要注意几类情况：

1. 整数为负数。

2. 整数为0或者数字中含有0的情况。

3. 是否可能溢出。

具体到这题：

1. 负数情况可以先记录符号，并转为正数

2. x = 10, return 1

3. x的reverse很可能大于INT_MAX或小于INT_MIN。需用一个unsigned long long来存储x。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: int reverse(int x) { unsigned long long xx; if(x==INT_MIN) xx = (unsigned long long)INT_MAX+1; else xx = x<0 ? -x : x; unsigned long long res = 0; while(xx) { res = (res*10) + (xx%10); xx /= 10; } if((res>(unsigned long long)INT_MAX && x>0) || (res>(unsigned long long)INT_MAX+1 && x<0)) return 0; return x<0 ? -res : res; } };

网上参考的一个更优解：

1 2 3 4 5 6 7 8 9 10 11 12 13

class Solution { public: int reverse(int x) { int ret = 0; while (x != 0) { // handle overflow/underflow if (abs(ret) > 214748364) return 0; ret = ret * 10 + x % 10; x /= 10; } return ret; } };

由于INT_MAX = 2147483647, INT_MIN = -21474836478
如果ret > 214748364，那么abs(ret*10)>=2147483650一定会overflow。
反之如果ret = 214748364，则一定有x % 10 = 1。若x%10 = 2，则原来的x = 2463847412 > INT_MAX，与输入参数为int类型矛盾。