LeetCode 7 整数反转

目录 

题目

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。

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

示例 1
输入：x = -123
输出：-321

示例 2
输入：x = 120
输出：21

思路 数学

重复「弹出」x 的末尾数字，将其「推入」rev 的末尾，直至 x 为 0。

要在没有辅助栈或数组的帮助下「弹出」和「推入」数字，我们可以使用如下数学方法：

// 弹出 x 的末尾数字 digit
digit = x % 10
x /= 10

// 将数字 digit 推入 rev 末尾
rev = rev * 10 + digit

为了防止反转后数据溢出，需要在 「推入」数字之前判断一下：

-2^31 <= rev * 10 + digit <= 2^31 - 1

①当x>0时，设INT_MAX = 2^31 - 1 = 2147483647

INT_MAX = (INT_MAX/10)*10 + 7（这里的除法是整除，不考虑余数）

rev * 10 + digit < INT_MAX

10*(rev - INT_MAX/10) < 7- digit

不等式右边 -2 <= 7- digit <= 7

(1)首先，rev肯定不能大于INT_MAX/10，不然rev * 10 + digit必然大于 INT_MAX

(2)当rev < INT_MAX/10

由于rev和INT_MAX/10都是整数，所以10*(rev - INT_MAX/10)最大也是-10，不等式恒成立

(3)当rev = INT_MAX/10

说明 x 的位数与 INT_MAX 的位数相同，且要推入的数字 digit 为 x的最高位

由于 x <= INT_MAX = 2147483647，所以0<=digit<=2，不等式恒成立

综上，rev <= (2^31-1)/10

②当x<0时，同理可得rev >= -2^31/10

所以，判断的不等式可改为-2^31/10 <= rev <= (2^31-1)/10，不成立返回0

class Solution {
    public int reverse(int x) {
        int rev = 0;
        while(x != 0){
            if(rev < Integer.MIN_VALUE/10 || rev > Integer.MAX_VALUE/10){
                return 0;
            }
            int digit = x%10;
            x /= 10;
            rev = rev * 10 + digit;
        }
        return rev;
    }
}