# 7. 整数反转:JavaScript 的两种解法之溢出判断你真的考虑全面了吗?
tags:
- math
# 题目链接
https://leetcode-cn.com/problems/reverse-integer/
# 方法一:数学方法
看到整数反转这个题,最先联想到先对数值取绝对值,然后除十取余以对整数进行反转,之后再考虑是否需要取负数以及数值范围问题。
/**
* @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);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
- 时间复杂度: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);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 方法二:JavaScript 的 reverse() 方法
可以使用 JavaScript 的字符串转换方法,但字符串转换的效率较低且依赖 API,在 https://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);
};
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
不知此处方法二的时间复杂度和空间复杂度如何计算,望得到大佬的指导。