阅读 270

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

题目链接: leetcode-cn.com/problems/re…

方法一:数学方法

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

/**
 * @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,因为会直接溢出。因此需要在整数反转的时候就加上溢出判断。

  1. 通过循环将数字 x 的每一位拆开,在进行整数反转时,每一步都判断是否溢出;
  2. 溢出条件有两个,一个是大于整数最大值 MAX_VALUE,另一个是小于整数最小值 MIN_VALUE,设当前计算结果为 result,下一位为 pop
  3. result * 10 + pop > MAX_VALUE 这个溢出条件来看:
    • 当出现 result > MAX_VALUE / 10 且还有 pop 需要添加时,则一定溢出;
    • 当出现 result === MAX_VALUE / 10pop > 7 时,则一定溢出,7 是 2^31 - 1 的个位数(2^31 - 1 = 2147483647)。
  4. result * 10 + pop < MIN_VALUE 这个溢出条件来看:
    • 当出现 result < MIN_VALUE / 10 且还有 pop 需要添加 时,则一定溢出;
    • 当出现 result === MIN_VALUE / 10pop < -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);
};
复制代码

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

更多题解

请关注:github.com/leviding/le…


加微信 imleviding 并填写验证信息 算法,加入 JavaScript 算法群,天天打卡 LeetCode。

本人水平有限,欢迎交流分享你的想法,欢迎大佬批评指正。

关注下面的标签,发现更多相似文章
评论