[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
};