0008. 字符串转换整数 (atoi)
题目描述
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。
函数 myAtoi(string s) 的算法如下：
- 跳过前导空格：读入字符串，忽略开头的空白字符。
- 判断符号：检查下一个字符（若不超出字符串末尾）是否为
'-'或'+'，读取该字符（若存在）并确定符号。若既不是'-'也不是'+'，则默认为正号。 - 读取数字：读入下一个字符，直到到达下一个非数字字符或到达字符串末尾，将这些数字字符转换为整数。
- 夹紧溢出：如果整数超过 32 位有符号整数范围
[−2³¹, 2³¹ − 1]，则夹紧到边界值。
示例 1：
输入：s = "42"
输出：42
示例 2：
输入：s = " -042"
输出：-42
解释：跳过前导空格，读取 '-' 号，读取 "042" 转为 42，结果 -42。
示例 3：
输入：s = "1337c0d3"
输出：1337
解释：读到非数字字符 'c' 时停止。
示例 4：
输入：s = "0-1"
输出：0
解释：读到非数字字符 '-' 时停止，结果为 0。
示例 5：
输入：s = "words and 987"
输出：0
解释：第一个非空格字符 'w' 不是数字也不是符号，结果为 0。
解题思路
第一步：理解问题本质
这道题考查的是字符串状态机：字符串中的每个字符在不同阶段有不同的含义和处理方式。处理流程本质上是一个顺序状态机：
[开始] → 跳过空格 → 读符号 → 读数字 → 夹紧边界 → [结束]
每个阶段一旦进入，就不会倒退。遇到不符合当前阶段规则的字符就立即停止并返回已读取的结果。
第二步：暴力解法——用 Python 内置函数处理
利用 Python 字符串方法逐步处理：
def myAtoi(s: str) -> int:
s = s.strip() # 去掉前导和尾部空格
if not s:
return 0
# 提取符号
sign = 1
start = 0
if s[0] in '+-':
sign = -1 if s[0] == '-' else 1
start = 1
# 提取连续数字
num_str = ''
for i in range(start, len(s)):
if s[i].isdigit():
num_str += s[i]
else:
break
if not num_str:
return 0
result = sign * int(num_str)
# 夹紧到 32 位范围
return max(-2**31, min(2**31 - 1, result))
- 时间复杂度：O(n)
- 空间复杂度：O(n)——
num_str字符串拼接
问题：字符串拼接效率较低；int(num_str) 转换可能产生任意大的整数，不受 32 位限制。虽然在 Python 中可行，但思路上没有体现逐字符构建整数的过程。
第三步：优化——逐字符构建整数
不拼接字符串，而是直接逐字符将数字追加到整数 num 上：
num = num * 10 + int(char)
这样每一步的 num 都是一个整数，最终再乘以符号 sign。夹紧操作放在最后一次性处理。
问题：如果字符串中有大量数字（如 10 亿位），num 会非常大。更好的做法是在每次追加之前进行溢出检测，提前终止。
第四步：最优解法——流程化 + 实时夹紧
按照四个步骤顺序处理字符串，同时在最终结果上做夹紧处理。Python 整数本身无限制，可以在最后统一夹紧，代码最简洁。
处理流程：
s.strip()去除前导空格- 检测首字符是否为
'-'或'+'，确定sign，并跳过该字符 - 逐字符读取数字，遇到非数字立即
break - 最终
result = num * sign，夹紧到[-2147483648, 2147483647]
完整代码实现
class Solution:
def myAtoi(self, s: str) -> int:
# 步骤 1：去除前导空格
s = s.strip()
if not s:
return 0
# 步骤 2：读取符号
sign = 1
if s[0] == '-':
sign = -1
s = s[1:]
elif s[0] == '+':
s = s[1:]
# 步骤 3：逐字符读取数字，遇到非数字停止
num = 0
for char in s:
if char not in '0123456789':
break
num = num * 10 + int(char)
# 步骤 4：乘以符号后夹紧到 32 位范围
result = num * sign
if result < -2147483648:
return -2147483648
if result > 2147483647:
return 2147483647
return result
示例推演
示例 1：s = " -042"
strip()后：s = "-042"- 首字符为
'-'，sign = -1，s = "042" - 逐字符读取：
'0'：num = 0 * 10 + 0 = 0'4'：num = 0 * 10 + 4 = 4'2'：num = 4 * 10 + 2 = 42
result = 42 * (-1) = -42-2147483648 ≤ -42 ≤ 2147483647，直接返回-42✓
示例 2：s = "1337c0d3"
strip()后：s = "1337c0d3"- 首字符为
'1'，无符号，sign = 1，s不变 - 逐字符读取：
'1'：num = 1'3'：num = 13'3'：num = 133'7'：num = 1337'c'：非数字，break
result = 1337 * 1 = 1337，直接返回1337✓
示例 3：s = "2147483648"（超出正数上界一个）
strip()后：s = "2147483648"，sign = 1- 逐字符读取所有 10 位数字：
num = 2147483648 result = 2147483648 * 1 = 21474836482147483648 > 2147483647，夹紧，返回2147483647✓
示例 4：s = "words and 987"
strip()后：s = "words and 987"- 首字符为
'w'，不是'-'或'+'，sign = 1，s不变 - 逐字符读取：
'w'不是数字，立即break num = 0，result = 0，返回0✓
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 字符串拼接 | O(n) | O(n) | 拼接中间字符串，最终统一转换 |
| 逐字符构建整数（最优） | O(n) | O(1) | 每步直接构建整数，无额外字符串 |
n 为字符串长度。实际有效数字位数最多 10 位，因此实际运行时间接近 O(1)。
易错点总结
strip()只去前导空格：本题strip()去掉了前导和尾部的空格，但有效数字读取在首个非数字字符处就停止，所以尾部空格不影响结果。使用lstrip()只去前导空格也是正确的。- 符号只在数字之前有效：
"+1"和"-1"有效，但"+-1"或"1-2"中第二个符号已经是数字阶段的非法字符，读到第一个'-'时就会break，这是正确行为。 char not in '0123456789'与not char.isdigit()的区别：isdigit()会将某些 Unicode 数字字符（如全角数字１２３）也识别为数字，而'0123456789'的成员检测严格限定为 ASCII 数字，更符合题意。- 夹紧方向：夹紧时注意
−2³¹ = −2147483648，2³¹ − 1 = 2147483647，正方向上界比绝对值小 1。 - 空字符串的处理：
strip()后若为空串，直接返回0，避免后续s[0]越界。
扩展思考
1. 有限状态机（DFA）建模
这道题是有限状态机的经典应用。定义以下状态：
| 状态 | 含义 |
|---|---|
start | 初始状态，只接受空格或数字或符号 |
signed | 已读到符号，只接受数字 |
in_number | 正在读数字 |
end | 终止状态，不再读取任何字符 |
用状态转移表描述所有字符类型的跳转，代码更加结构化，适合扩展到更复杂的解析场景。
2. 溢出检测的提前终止
本题代码在最后统一夹紧，Python 整数可以任意大，所以没问题。如果要严格限制"不使用超 32 位整数"（如第 7 题的要求），需要在每次 num = num * 10 + digit 之前检查是否会溢出，检测逻辑与第 7 题相同。