LeetCode 7. 整数反转：JavaScript 解法之溢出判断你真的考虑全面了吗？

方法一：数学方法

看到整数反转这个题，最先联想到先对数值取绝对值，然后除十取余以对整数进行反转，之后再考虑是否需要取负数以及数值范围问题。

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    let result = 0;
    let value = Math.abs(x);
    while (value !== 0) {
        result = result * 10 + value % 10;
        value = Math.floor(value / 10);
    }
    result = x > 0 ? result : - result;
    return (result > Math.pow(2,31) - 1 || result < - Math.pow(2,31) ? 0 : result);
};

时间复杂度：O(log(n))
空间复杂度：O(1)

写到这，本以为就完成了，测试用例也都通过了。但是！你回想一下题目中的说明：

假设我们的环境只能存储得下 32 位的有符号整数。

我们测试上面程序的时候并非在这么苛刻的环境下，所以先得到 result，再判断其是否在所要求的数值范围内，不在则 return (0)，所以也正常通过了所有的测试用例。但是当真正在一个只能存储得下 32 位的有符号整数的环境中，如果整数反转后的数值超过要求的数值范围，那我们根本得不到 result，因为会直接溢出。因此需要在整数反转的时候就加上溢出判断。

通过循环将数字 x 的每一位拆开，在进行整数反转时，每一步都判断是否溢出；
溢出条件有两个，一个是大于整数最大值 MAX_VALUE，另一个是小于整数最小值 MIN_VALUE，设当前计算结果为 result，下一位为 pop；
从 result * 10 + pop > MAX_VALUE 这个溢出条件来看：
- 当出现 result > MAX_VALUE / 10 且还有 pop 需要添加时，则一定溢出；
- 当出现 result === MAX_VALUE / 10 且 pop > 7 时，则一定溢出，7 是 2^31 - 1 的个位数（2^31 - 1 = 2147483647）。
从 result * 10 + pop < MIN_VALUE 这个溢出条件来看：
- 当出现 result < MIN_VALUE / 10 且还有 pop 需要添加时，则一定溢出；
- 当出现 result === MIN_VALUE / 10 且 pop < -8 时，则一定溢出，8 是 -2^31 的个位数（-2^31 = -2147483648）。

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    let result = 0;
    let value = Math.abs(x);
    let MIN_VALUE = - Math.pow(2,31);
    let MAX_VALUE = Math.pow(2,31) - 1;
    while (value !== 0) {
        let pop = value % 10;
        // 溢出判断
        if (result > MAX_VALUE / 10 || (result === MAX_VALUE / 10) && pop > 7) return 0;
        if (result < MIN_VALUE / 10 || (result === MIN_VALUE && pop < -8)) return 0;
        result = result * 10 + pop;
        value = Math.floor(value / 10);
    }
    return (x >= 0 ? result : - result);
};

方法二：JavaScript 的 reverse() 方法

可以使用 JavaScript 的字符串转换方法，但字符串转换的效率较低且依赖 API，在 leetcode.com 上测试发现，所耗时间和内存均要大于方法一。

还有一个严重的问题就是，通过字符串转换后乘以系数这一步骤 let ret = coefficient * str.split('').reverse().join('');，如果转换后得到的数值超出了题目要求的范围，那这一步就已经溢出了，所以这种方法不适用。如果你有更好的方法，十分希望与你交流学习。

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    let coefficient = x >= 0 ? 1 : -1;
    let str = Math.abs(x) + '';
    let ret = coefficient * str.split('').reverse().join('');
    return (ret > Math.pow(2, 31) -1 || ret < - Math.pow(2, 31) ? 0 : ret);
};

不知此处方法二的时间复杂度和空间复杂度如何计算，望得到大佬的指导。

LeetCode 7. 整数反转：JavaScript 解法之溢出判断你真的考虑全面了吗？

方法一：数学方法

方法二：JavaScript 的 reverse() 方法

更多题解