LeetCode 8. 字符串转换整数 (atoi)
题目描述
题意分析
只解析字符串开头符合规则的整数部分：先跳过连续的前导空格，再读取至多一个正负号，随后连续读取十进制数字。没有符号时按正数处理；进入数字阶段后，遇到任何非数字字符都立即结束，包括空格和另一个符号，不再从后面的数字重新开始。
没有读到数字就返回
0；读到了数字，就返回带符号的数值。结果必须限制在[-2147483648, 2147483647]：超过上界返回上界，低于下界返回下界。空串、全空格或只有符号的字符串都可能出现，需要按同一套规则处理。
解法：按状态顺序逐字符解析
核心思路
[!blue]
解析阶段只能依次向前，不能返回之前的阶段，因此用一个下标
idx顺序完成即可：先用循环跳过前导空格，再用一次条件判断读取可选符号，最后用循环读取数字。每次读取字符前都检查idx < n，便能自然处理字符串提前结束的情况。用
sign保存正负号，用非负的ans保存已读数字的绝对值。新读到一位digit，原来的各位都向高位移动一位，更新式就是ans * 10 + digit。前导零不需要单独跳过，按同样的式子累积仍然是零。关键在于乘加之前判断是否越界。为了保证更新后不超过正数上界
MAX = 2147483647，需要满足ans * 10 + digit <= MAX，等价于ans <= (MAX - digit) / 10。这里都是非负整数，整数除法向下取整，恰好得到允许的最大旧值；因此代码在ans > (MAX - digit) / 10时直接返回对应边界。负数下界的绝对值比
MAX多一。使用相同判断时，精确读到绝对值2147483648也会触发返回，但返回的-2147483648正是正确结果；更大的绝对值同样应截断到这个下界。这样既不需要更宽的整数类型，也不会先把正的绝对值算溢出。一旦触及上述边界，后续继续读取数字只可能使绝对值不变或增大，遇到非数字则停止，所以可以立即返回。正常结束时返回
sign * ans；若一个数字都未读取，ans保持为零。
解题步骤
- 令
idx = 0，在下标有效且当前字符为' '时继续前进。- 初始化
sign = 1。若当前字符是+或-，记录符号并将下标前进一步；只执行一次，不循环读取符号。- 初始化
ans = 0，连续读取'0'到'9'，用当前字符减去'0'得到digit。先检查乘加上限，超出时按符号直接返回边界，否则更新ans并前进下标。- 数字循环因遇到非数字或到达末尾而结束，返回
sign * ans。
代码实现
class Solution {
public int myAtoi(String s) {
int n = s.length();
int idx = 0;
while (idx < n && s.charAt(idx) == ' ') {
idx++;
}
int sign = 1;
// 只读取一次可选符号，之后遇到非数字就结束数字扫描。
if (idx < n && (s.charAt(idx) == '+' || s.charAt(idx) == '-')) {
if (s.charAt(idx) == '-') {
sign = -1;
}
idx++;
}
int ans = 0;
while (idx < n && s.charAt(idx) >= '0' && s.charAt(idx) <= '9') {
int digit = s.charAt(idx) - '0';
// 乘加前反推界限，负号下精确下界与超界都返回最小整数。
if (ans > (Integer.MAX_VALUE - digit) / 10) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
// 只有确认安全后，才把本位数字拼入累计值。
ans = ans * 10 + digit;
idx++;
}
return sign * ans;
}
}
func myAtoi(s string) int {
n := len(s)
idx := 0
for idx < n && s[idx] == ' ' {
idx++
}
sign := 1
// 只读取一次可选符号，之后遇到非数字就结束数字扫描。
if idx < n && (s[idx] == '+' || s[idx] == '-') {
if s[idx] == '-' {
sign = -1
}
idx++
}
maxInt := 1<<31 - 1
minInt := -1 << 31
ans := 0
for idx < n && s[idx] >= '0' && s[idx] <= '9' {
digit := int(s[idx] - '0')
// 乘加前反推界限，负号下精确下界与超界都返回最小整数。
if ans > (maxInt-digit)/10 {
if sign == 1 {
return maxInt
}
return minInt
}
// 只有确认安全后，才把本位数字拼入累计值。
ans = ans*10 + digit
idx++
}
return sign * ans
}
复杂度分析
- 时间复杂度：$O(n)$，每个字符最多扫描一次。
- 空间复杂度：$O(1)$，只使用常数个变量。
关键点总结
[!green]
- 解析顺序固定：空格 → 符号 → 数字。
- 只接受 ASCII 数字
'0'到'9'，遇到其他字符立即停止。- 溢出判断必须放在乘加之前。
- 正负边界不对称，溢出时分别返回
MAX_VALUE和MIN_VALUE。
易错点总结
[!yellow]
- 跳空格或读符号前忘记判断下标，空串和全空格会越界。
- 用循环读取符号，会错误接受多个连续符号；读完第一个符号后，下一位不是数字就应结束。
- 遇到非数字后继续寻找后续数字，会把本应停止的两段内容错误拼接；符号后的空格也不能再次跳过。
- 先乘加再判断溢出，此时
int已经发生回绕。- 负数溢出返回
-Integer.MAX_VALUE，会漏掉合法下界-2147483648。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 65. 有效数字 | 困难 | 原题验证整串是否为合法数值，本题按atoi规则读取前缀并返回整数，停止规则不同。 |
| 7. 整数反转 | 中等 | 同样要在十进制累积过程中处理32位溢出，本题返回截断边界，反转题按题意返回0。 |