1 题目

给定一个 32 位有符号整数，将整数中的数字进行反转。

示例 1:

1
2

输入: 123
输出: 321

示例 2:

1
2

输入: -123
输出: -321

示例 3:

1
2

输入: 120
输出: 21

注意

假设我们的环境只能存储 32 位有符号整数，其数值范围是$[-2^{31},2^{31}-1]$。根据这个假设，如果反转后的整数溢出，则返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

2 解题

思路

我们可以一次构建反转整数的一位数字。在这样做的时候，我们可以预先检查向原整数附加另一位数字是否会导致溢出。

算法

反转整数的方法可以与反转字符串进行类比。

我们想重复 “弹出” $x$的最后一位数字，并将它 “推入” 到 rev 的后面。最后,$rev$将与 $x$ 相反。

要在没有辅助堆栈 / 数组的帮助下 “弹出” 和 “推入” 数字，我们可以使用数学方法。

1
2
3
4
5
6
7

//pop operation:
pop = x % 10;
x /= 10;

//push operation:
temp = rev * 10 + pop;
rev = temp;

但是，这种方法很危险，因为当 $temp = rev * 10 + pop$时会导致溢出。

幸运的是，事先检查这个语句是否会导致溢出很容易。

为了便于解释，我们假设 $rev$是正数。

  • 如果$temp = rev * 10 + pop$导致溢出，那么一定有 $rev \geq \frac{INTMAX}{10}$。
  • 如果 $rev > \frac{INTMAX}{10}$，那么$temp = rev * 10 + pop$一定会溢出。
  • 如果$ rev = \frac{INTMAX}{10}$，那么只要 $pop > 7$，$temp = rev * 10 + pop$就会溢出。

当 $rev$为负时可以应用类似的逻辑。

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

int reverse(int x) 
{
    int rev = 0;
    while(x!=0)
    {
        int pop = x%10;
        x = x/10;
        //情况1，当前rev还未乘以10就比INT_MAX大
        //情况2，当前rev等于乘以10等于INT_MAX，再加上大于7的pop（余数）
        if(rev > INT_MAX/10 || (rev == INT_MAX/10 && pop >7))	rev = 0;
        //情况1，当前rev还未乘以10就比INT_MIN小
        //情况2，当前rev等于乘以10等于INT_MIN，再加上小于-8的pop（余数）
        if(rev < INT_MIN/10 || (rev == INT_MIN/10 && pop <-8))	rev = 0;
        
        rev = rev * 10 + pop;             
    }
    revurn rev;
}

复杂度分析：

  • 时间复杂度：$O(\log(x))$,x中大约有$\log_{10}(x)$。

  • 空间复杂度：$O(1)$