每日一道 LeetCode (2)：整数反转

题目：整数反转

题目来源：https://leetcode-cn.com/problems/reverse-integer

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 1:

输入: 123
输出: 321

示例 2:

输入: -123
输出: -321

示例 3:

输入: 120
输出: 21

注意:

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31,  2^31 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

解题思路

题目中对数字反转的结果有最大最小限制，这个限制实际上在 Java 中也是 int 类型的大小限制，把 [−2^31,  2^31 − 1] 这个公式计算一下，结果就是 [-2147483648, 2147483647] 。

接下来的就只剩下一个问题了，如何把一个整数进行反转。

我这里提供一个思路，我们对原数字除以 10 以后进行取模运算（取余数）:

大体思路就是上面这样，然后注意边缘值判断，代码基本上就按照这个思路来：

public int reverse(int x) {
    int res = 0;
    while (x != 0) {
        // 先获取末尾数字
        int tmp = x % 10;

        if (res < -214748364 || (res == -214748364 && tmp < -8)) {
            return 0;
        }

        if (res > 214748364 || (res == 214748364 && tmp > 7)) {
            return 0;
        }

        res = res * 10 + tmp;
        x /= 10;
    }
    return res;
}

这种边界判断方式稍显笨重，我看了看别人的答案，看到一种溢出的判断思路，感觉不错分享下：

public int reverse_1(int x) {
    int res = 0;
    while (x != 0) {

        if (res > 214748364 || res < -214748364) {
            return 0;
        }

        res = res * 10 + x % 10;
        x /= 10;
    }
    return res;
}

这个结果提交 LeetCode 以后，直接看到 LeetCode 说执行耗时超过 100% 的用户。

简直意外的惊喜，这里的判断极限值的含义如下：1463847412

极限最大值是 2147483648 ，除以 10 以后是 214748364 ，这里当 res 是 214748364 时，输入的 x 只能是 1463847412 ，因为 2463847412 、 3463847412 这些数字本身已经 int 溢出了。

思路非常巧妙，利用了 int 本身的溢出范围，限制了输入数据的大小，减少了需要判断的可能性。