[每日一题] 124. 整数反转(数学、溢出判断、样例踩坑题、多方法）

1. 题目来源

链接：整数反转
来源：LeetCode

2. 题目说明

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

示例1：

输入: 123
输出: 321

示例 2:

输入: -123
输出: -321

示例 2:

输入: 120
输出: 21

注意:

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

3. 题目解析

方法一：精简溢出条件判断、忽略正负号处理

这道题本来没什么好说的，主要是养成一个良好的溢出条件判断习惯，不是遇到 int 类型搞不定的就直接上 long long 的，这样就没意思了，要是摆明考这个溢出判断知识点，就让你翻转一个 long long 的整数呢？

int 型数值范围是 -2147483648～2147483647
long 型数值范围为 -9223372036854775808~9223372036854775807

OJ 给出的官方解答并不需要使用 long，确实相当精简，没有特意处理正负号，仔细一想，果然正负号不影响计算，而且没有用 long 型数据，感觉写的更好一些，那么就贴出来吧：

参见官方代码如下：

class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
            if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
};

紧接着就有大牛评论了： 我觉得官方的代码有多余，因为int类型最大数和最小数开头的数字只能是1或2，所以如果有最后一次循环的话，pop的值一定为1或2，所以(rev == INT_MAX / 10 && pop > 7)和(rev == INT_MIN / 10 && pop < -8)判断可以省略。本人已测。????

紧接着又有大牛反驳了： 在不知道最大正数是2147683647的情况，可以用数学归纳法知道2的31次方个位数是8，从而最大正数 INT_MAX 个位数是7。但是怎么知道 INT_MAX最大位是2？换句话说如果题目把整数范围限定在-2^21 ,2 ^21-1怎么知道开头数字是多少。????

编程真是妙不可言！

确实针对本题来讲不需要上述判断，但心里时刻要知道就行了，感谢两位大牛的教育！

参见代码如下：

// 执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户
// 内存消耗 :8.3 MB, 在所有 C++ 提交中击败了19.02%的用户

class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while (x != 0) {
            if (abs(res) > INT_MAX / 10) return 0;
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
};

方法二：long 类型快速解决问题

我们也可以用 long 型变量保存计算结果，最后返回的时候判断是否在 int 返回内，但其实题目中说了只能存整型的变量，所以这种方法就只能当个思路扩展了。

参见代码如下：

// 执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户
// 内存消耗 :8.3 MB, 在所有 C++ 提交中击败了10.92%的用户

class Solution {
public:
    int reverse(int x) {
        long res = 0;
        while (x != 0) {
            res = 10 * res + x % 10;
            x /= 10;
        }
        return (res > INT_MAX || res < INT_MIN) ? 0 : res;
    }
};