[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_MAXchar 合法。然而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_MAXINT_MIN 可以发现,除去正负符号,两者之间的差异仅在末位数:78。那么,我们可以认为,除去符号后,当正数 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
};