把字符串转换成整数 (atoi)

难度: Medium

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−2³¹, 2³¹− 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2³¹ 的整数应该被固定为 −2³¹ ，大于 2³¹− 1 的整数应该被固定为 2³¹− 1 。
返回整数作为最终结果。

注意：

本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

示例 1：

输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："42"（读入 "42"）
           ^
解析得到整数 42 。
由于 "42" 在范围 [-2³¹, 2³¹ - 1] 内，最终结果为 42 。

示例 2：

输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
            ^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
             ^
第 3 步："   -42"（读入 "42"）
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-2³¹, 2³¹ - 1] 内，最终结果为 -42 。

示例 3：

输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
             ^
解析得到整数 4193 。
由于 "4193" 在范围 [-2³¹, 2³¹ - 1] 内，最终结果为 4193 。

提示：

0 <= s.length <= 200
s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成

注意：本题与主站 8 题相同：https://leetcode-cn.com/problems/string-to-integer-atoi/

Submission

运行时间: 44 ms

内存: 14.8 MB

class Solution:
    def strToInt(self, str: str) -> int:
        s = str.strip()
        if s == '':
            return 0
        if s[0] == '+':
            sign = 1
            i = 1
        elif s[0] == '-':
            sign = -1
            i = 1
        else:
            sign = 1
            i = 0
        res = 0
        boundary = (2**31-1) // 10
        while i < len(s):
            c = s[i]
            if not '0' <= c <= '9':
                break
            int_c = ord(c) - ord('0')
            if (res == boundary and int_c > 7) or res > boundary:
                return -2147483648 if sign == -1 else 2147483647
            else:
                res = res * 10 + int_c
            i += 1
        return sign * res

Explain

该题解首先使用strip()去除字符串s的前导和后续空格。若处理后的字符串为空，则直接返回0。接下来，判断字符串首字符是否为正负号，以确定结果的符号并设置起始索引。然后，初始化结果变量res为0，并设置一个界限值boundary，用于判断结果是否溢出。遍历字符串中的字符，如果字符是数字，则计算其整数值并更新结果res；如果遇到非数字字符或者结果溢出，则停止遍历。最后，根据符号变量sign调整res的符号，并返回最终结果。

时间复杂度: O(n)

空间复杂度: O(1)

# 解题类
class Solution:
    def strToInt(self, str: str) -> int:
        s = str.strip()  # 去除前后空格
        if s == '':
            return 0  # 空字符串直接返回0
        # 判断并处理正负号
        if s[0] == '+':
            sign = 1
            i = 1
        elif s[0] == '-':
            sign = -1
            i = 1
        else:
            sign = 1
            i = 0
        res = 0  # 初始化结果
        boundary = (2**31-1) // 10  # 计算边界值
        while i < len(s):  # 遍历数字字符
            c = s[i]
            if not '0' <= c <= '9':  # 如果非数字字符则停止遍历
                break
            int_c = ord(c) - ord('0')  # 计算字符的整数值
            # 检查是否溢出
            if (res == boundary and int_c > 7) or res > boundary:
                return -2147483648 if sign == -1 else 2147483647
            else:
                res = res * 10 + int_c  # 更新结果
            i += 1
        return sign * res  # 根据符号返回结果

Explore

在`myAtoi`函数中，我们通过在循环内部检查每个字符是否属于'0'到'9'的范围来决定何时停止读取数字。如果遇到一个字符不在这个范围内，循环将会中断，因此后续的字符将不会被进一步处理或转换成数字。这种方式确保了只有连续的数字字符会被转换，一旦遇到第一个非数字字符，转换过程即停止。

函数使用`strip()`仅移除字符串开头和结尾的空格。如果字符串中间包含空格，那么在数字读取过程中一旦遇到这些空格，读取将会停止。例如，对于字符串`'123 456'`，函数只会识别出`123`，而在遇到第一个中间空格时停止读取。这意味着中间空格会被视为非数字字符，从而终止数字的进一步解析。

这个边界值`boundary`是为了确保在进行数字转换时不会超过32位整数的最大值2147483647（对于正数）或最小值-2147483648（对于负数）。通过设置`boundary`为214748364（即`(2**31-1) // 10`），我们在每次迭代中检查`res`变量是否大于或等于这个边界值。如果`res`已接近边界值，再加上一个大于7的数字会导致溢出（因为2147483647的最后一位是7）。这种预先设定的边界检查方法可以有效防止溢出，同时简化代码逻辑。

使用`'0' <= c <= '9'`来判断字符是否为数字是一种非常直接且有效的方法，适用于所有基于ASCII编码的环境。这种方法的局限性主要在于它仅适用于ASCII字符集中的数字。对于其他语言或编码系统（如Unicode中的全角数字等），这种方法可能无效。此外，这种方法假设输入是合法的ASCII字符，对于非法字符或二进制数据，此方法可能不适用。