[LC8] String to Integer
Sunday, January 6, 2019
这道算法题来自 LeetCode #8:实现字符串转整型的函数 atoi
。这里使用了 JavaScript 实现,但 JavaScript 没有整型数值。为了解决这道算法题,人为设定存在整型,同时也不能使用 parseInt
函数,因为它相当于 atoi
函数。
去除空格
用正则 /^\s+/
把所有起始的空格符号去掉:
const nstr = str.replace(/^\s+/g, '')
正负符号判断
尝试判断是否存在 +
或 -
符号。由于这个符号位只能出现在第一位,需要 i === 0
来限制:
let sign = 1
...
if (i === 0 && (strarr[i] === '-' || strarr[i] === '+')) {
sign = strarr[i] === '-' ? -1 : 1
continue
}
处理非法字符
按照题目要求,遇到非数字字符则忽略后续的子串,此时终止转换,返回已计算的结果即可。由于正负符号并非数字字符,所以这个处理应放在“正负符号判断”之后:
if ('0' > strarr[i] || strarr[i] > '9') {
return result * sign
}
处理正数溢出
假定当前转换成整数的合法字符为 char
,已经完成转换的整型结果为 result
,那么可以判断:result
增加一位尾数 char
后是否超过 INT_MAX
。
我们可以认为满足 result * 10 + char <= INT_MAX
则 char
合法。然而result * 10
很可能发生溢出,导致 result * 10 + char > INT_MAX
。
为了更好地处理溢出的问题,我们只需在式子两边同除以 10,即 result + char / 10 <= INT_MAX / 10
,这样就巧妙地规避了 result * 10
可能溢出的问题。
现在通过具体例子,分两种情况处理追加 char
导致溢出的问题。
(1) 假设要转换的字符为 214748365X
(其中 X 为任意合法数字字符),现在扫描到最后一位即 X
。这种情况下,无论 X
为任何数字,都会溢出。所以当 result > INT_MAX / 10
时,终止转换,直接返回 INT_MAX
INPUT 214748365X
INTMAX 2147483647
(2)假设要转换的字符为 2147483648
,现在扫描到最后一位即 8
。这种情况下,存在 result === INT_MAX / 10
,即此时 result
的各位数与 INT_MAX
的前 N - 1 位相等。如果继续追加 char
必然溢出。所以,我们需要把 INT_MAX
的最后一位数字 7
提取出来,即 INT_MAX % 10
,并与 char
进行比较:若 char
大于 7
则溢出。
INPUT 2147483648
INTMAX 2147483647
综合以上分析,代码实现如下:
const MAX_PREV_DIGITS = (INT_MAX / 10 | 0)
const MAX_LAST_DIGIT = (INT_MAX % 10 | 0)
if (sign > 0
&& (result > MAX_PREV_DIGITS
|| (result === MAX_PREV_DIGITS
&& Number(strarr[i]) > MAX_LAST_DIGIT))) {
return INT_MAX
}
处理负数溢出
与处理正数相似,不过由于 result
在转换过程中一直都是正数,所以 INT_MIN
需要转成正数,但不能直接 INT_MIN * -1
,因为结果必然溢出:$-2^{31} * (-1) = 2^{31} > 2^{31} - 1$。那么,在取 INT_MIN
前 N 位时,应该 先整除 10 再乘以 -1 从而避免溢出,$2^{31} / 10 = 2^{30} < 2^{31} - 1$
const MIN_PREV_DIGITS = (INT_MIN / 10 | 0) * -1
const MIN_LAST_DIGIT = (INT_MIN % 10 | 0) * -1
if (sign < 0
&& (result > MIN_PREV_DIGITS
|| (result === MIN_PREV_DIGITS
&& Number(strarr[i]) >= MIN_LAST_DIGIT)) {
return INT_MIN
}
简化正数与负数的处理逻辑
由于 result
在转换过程都是正数,考虑把对正数与负数的溢出判断整合成对正数的判断,从而简化处理逻辑。
INT_MAX 214748364 7
INT_MIN - 214748364 8
对于 32 位整型来说,简单对比一下 INT_MAX
与 INT_MIN
可以发现,除去正负符号,两者之间的差异仅在末位数:7
与 8
。那么,我们可以认为,除去符号后,当正数 result
的各位数与 INT_MAX
前 N - 1 位相同时,如果 char > 7
,则发生溢出。
if ((result > MAX_PREV_DIGITS
|| (result === MAX_PREV_DIGITS
&& Number(strarr[i]) > MAX_LAST_DIGIT))) {
return sign > 0 ? INT_MAX : INT_MIN
}
Implementation
处理完正数与负数的溢出问题后,更新 result
的值,即 result = result * 10 + Number(char)
。完整代码参考如下:
const MAX_PREV_DIGITS = (INT_MAX / 10 | 0)
const MAX_LAST_DIGIT = (INT_MAX % 10 | 0)
var myAtoi = function(str) {
if (!str) {
return 0
}
const nstr = str.replace(/^\s+/g, '')
if (nstr.length === 0) {
return 0
}
const strarr = nstr.split('')
let sign = 1
let result = 0
let i = 0
if (strarr[i] === '-' || strarr[i] === '+') {
sign = strarr[i] === '-' ? -1 : 1
i++
}
while (i < strarr.length) {
if ('0' > strarr[i] || strarr[i] > '9') {
return result * sign
}
if ((result > MAX_PREV_DIGITS
|| (result === MAX_PREV_DIGITS
&& Number(strarr[i]) > MAX_LAST_DIGIT))) {
return sign > 0 ? INT_MAX : INT_MIN;
}
result = result * 10 + Number(strarr[i])
i++
}
return result * sign
};