题目描述
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
注意： 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
示例：
输入: 123
输出: 321
输入: -123
输出: -321
输入: 120
输出: 21
题目链接： https://leetcode-cn.com/problems/reverse-integer/
思路
题目的难点在于反转过程中整数可能溢出，所以在反转过程中要判断是否溢出。有符号int的范围为-2147483648到2147483647，所以有两种情况会溢出（假设当前反转的结果为ans，输入为x, MAX_VALUE=2147483647, MIN_VALUE=-2147483648）：
- ans > MAX_VALUE/10 || (ans==MAX_VALUE/10 && x%10>7) // x>=0
- ans < MIN_VALUE/10 || (ans==MIN_VALUE/10 && x%10<-8) // x<0
有一点需要注意，上面的条件中ans > MAX_VALUE/10不能写成ans*10 > MAX_VALUE，因为ans*10可能会超过int的表示范围从而出现runtime error。
代码如下：
class Solution {
public:
int reverse(int x) {
int MAX_INT = 0x7fffffff;
int ans = 0;
bool isNegative = x<0? true:false;
x = abs(x);
while(x>0){
if(ans>MAX_INT/10 || (ans==MAX_INT/10 && x%10>7)) return 0;
ans = ans*10 + x%10;
x /= 10;
}
if(isNegative) ans = -ans;
return ans;
}
};
在上面的代码中，将数取绝对值统一转为正数后判断。
- 时间复杂度：O(n)
n为数字的长度（lgx）。 - 空间复杂度：O(1)
这题还有一点需要注意，下面的写法虽然能通过，但是是不对的，因为题目假设环境只能存储得下 32 位的有符号整数，而代码却使用了long：
class Solution {
public:
int reverse(int x) {
int MAX_INT = 0x7fffffff;
long ans = 0;
bool isNegative = x<0? true:false;
x = abs(x);
while(x>0){
ans = ans*10+x%10;
x/=10;
if(ans>MAX_INT) return 0; // 溢出
}
if(isNegative) ans = -ans;
return ans;
}
};