剑指Offer题解 - Day59

剑指 Offer 67. 把字符串转换成整数

力扣题目链接[1]

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−2^31, 2^31 − 1]。如果数值超过这个范围，请返回 INT_MAX (2^31 − 1) 或 INT_MIN (−2^31) 。

思路：

首先需要考虑什么情况下可以将字符串转换为整数。需要考虑以下情况：

• 当遇到首部的空格时，直接跳过；
• 当遇到符号位时，使用变量1、-1保存符号位+、-。
• 当遇到首个非数字字符时，直接返回。
• 当遇到数字字符时，进一步进行处理。

那需要如何处理数字字符呢？

首先需要将字符转换为字符串。可以通过隐式转换来达到目的。其次还要进行数字的拼接，可以声明一个变量「res」用来保存初始结果，那么数字的拼接就是res = res * 10 + (i - '0') ，i为当前数字字符。

最后还要判断数字的大小是否在[−2^31, 2^31 − 1]。由于环境只能存储 32 位大小的有符号整数，因此要在上面代码执行之前就需要进行判断。是否越界分为两种情况：

因为数字的拼接需要与上次的结果乘以10，并加上当前数字字符，因此我们需要存储const BOUNDARY = 2^31 / 10，以此来判断最终结果是否为越界。

• 如果上一次的拼接结果大于BOUNDARY，那么最终结果肯定越界，此时直接根据符号位返回−2^31或者2^31 − 1。
• 如果上一次的拼接结果等于BOUNDARY，那么还需要判断当前数字字符是否大于7。为什么是7呢？是因为2^31 - 1等于2147483647 ，所以如果最后一位超过7，那就说明数字越界。此时直接根据符号位返回−2^31或者2^31 − 1。
• 如果上一次的拼接结果小于BOUNDARY，则正常执行数字拼接逻辑。

当遍历字符串时，就执行处理数字字符的逻辑。遇到非数字字符时，直接中断循环，直接返回上一轮保存的结果。如果数字越界，就返回相应结果。如果一切顺利，则会跳出循环，返回最终结果。不要忘记符号位与最终结果相乘。

遍历

/**
 * @param {string} str
 * @return {number}
 */
var strToInt = function(str) {
    let i = 0;
    let sign = 1;
    let res = 0;
    let length = str.length;
    let pow = Math.pow(2, 31);
    const MAX_VALUE = pow - 1;
    const MIN_VALUE = -pow;
    const BOUNDARY = Math.floor(pow / 10);
    while(str.charAt(i) === ' ') {
        if (++i === length) return 0;
    }
    if (str.charAt(i) === '-') sign = -1;
    if (str.charAt(i) === '-' || str.charAt(i) === '+') i++;
    for (let j = i; j < length; j++) {
        if (str.charAt(j) < '0' || str.charAt(j) > '9') break;
        if (res > BOUNDARY || (res === BOUNDARY && (str.charAt(j) > '7'))) {
            return sign === 1 ? MAX_VALUE : MIN_VALUE;
        }
        res = res * 10 + (str.charAt(j) - '0');
    }
    return sign * res;
};

• 时间复杂度 O(n)。
• 空间复杂度 O(1)。

分析：

上述代码就是根据思路得来的代码。有几点需要特别注意：

1. 由于JS中没有原生的Number静态属性来表示32位的最大整数和最小整数，因此这里提前计算好并存储到相应常量当中；
2. 边界的计算不可以直接对2^31进行除以10，这样算出的结果是默认有小数点的，最终会导致边界判断出错，因此需要向下取整；
3. 数字拼接时，需要对于str.charAt(j) 获取到的字符串进行转换为数字，否则最终结果就变成了字符拼接，结果出错。

总结

本题考查了字符串相关知识点。尤其是前端会涉及到隐式转换以及存储方式为64位，因此需要额外做一些处理。

复杂度方面，由于需要遍历整个字符串，因此时间复杂度是O(n) ，声明了几个变量和常量，占用常数级别的空间，因此空间复杂度是O(1) 。

参考资料

[1]

力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/58pq8g/