LeetCode 8. 字符串转换整数 (atoi)

约 6 分钟
文章信息 24 个分类 1 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 历史考题 100-200 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 华为 拼多多 网易 小米 亚马逊 虾皮 携程
标签
字符串
目录

题目描述

✅ 8. 字符串转换整数 (atoi)

image-20250419022104874

题意分析

这道题的算法几乎没有难度，难度全在把题面规则读全、读准。规则一条都不能漏，逐条列清如下。

第一条，丢弃前导空格。只丢弃字符串最开头的连续空格字符，并且只有空格算空格。一旦读到第一个非空格字符，丢弃阶段就永久结束——后面再出现空格，它就是一个普通的「非数字字符」，作用是终止解析而不是被跳过。

第二条，可选的正负号。空格之后最多允许出现一个 + 或 -，并且必须紧贴在数字前面。没有符号时按正数处理。出现第二个符号（如 "+-12"）时，第二个符号就是终止字符，此时前面还没读到任何数字。

第三条，连续读取数字直到读不动。从符号后的位置开始，一位一位地读 '0' 到 '9'，遇到第一个非数字字符或字符串结束就停下。停下来不是错误，后面剩下的内容全部丢弃即可——这就是所谓的「非数字字符截断」。"4193 with words" 的答案是 4193，"3.14" 的答案是 3（小数点不是数字，读到它就停）。

第四条，前导零无意义。"0032" 读出来是 32，因为逐位累加时前导零对结果没有贡献，不需要专门处理。

第五条，没读到任何数字就返回 0。这一条覆盖了空串、全是空格、开头就是字母（"words and 987"）、只有符号（"+"）、符号后紧跟非数字（"+-12"、"- 42"）等所有情形，统一返回 0 而不是抛异常。

第六条，溢出钳制。结果必须落在 32 位有符号整数范围 $[-2^{31}, 2^{31} - 1]$ 内。小于下界的钳到 -2147483648，大于上界的钳到 2147483647。注意是钳制而不是取模、也不是返回 0，并且钳到哪一端由符号决定。

溢出这一条还藏着一个不对称：正数的上界是 2147483647，负数的下界是 -2147483648，两者的绝对值相差 1。所以「先按绝对值累加、最后乘符号」的写法必须想清楚绝对值恰好等于 2147483648 时会走哪个分支。

其余边界情形：字符串可能为空，任何 charAt 之前都要先做长度判断；数字段可能长达几十位，远超整型范围，所以不能先累完再检查。

解法：按状态顺序逐字符解析

核心思路

按题目顺序处理三件事：跳过前导空格、读取一个可选符号、连续读取数字。遇到第一个非数字字符立即停止。

数字按 ans = ans * 10 + digit 累加。为避免 int 先溢出再判断，必须在乘加前检查：

ans > (Integer.MAX_VALUE - digit) / 10

条件成立时，正数返回 Integer.MAX_VALUE，负数返回 Integer.MIN_VALUE。

解题步骤

  1. 移动下标，跳过字符串开头的连续空格。
  2. 读取至多一个 + 或 -，记录符号。
  3. 连续读取 '0' 到 '9'，每次累加前检查是否溢出。
  4. 遇到非数字或字符串结束时，返回 sign * ans；未读到数字时 ans 为 0。

代码实现

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)$，只使用常数个变量。

关键点总结

  • 解析顺序固定：空格 → 符号 → 数字。
  • 只接受 ASCII 数字 '0' 到 '9'，遇到其他字符立即停止。
  • 溢出判断必须放在乘加之前。
  • 正负边界不对称，溢出时分别返回 MAX_VALUE 和 MIN_VALUE。

易错点总结

  • 跳空格或读符号前忘记判断下标，空串和全空格会越界。
  • 用循环读取符号，会把 "+-12" 错误解析为 -12。
  • 遇到非数字后继续扫描，会把 "4193 with words" 解析错误。
  • 先乘加再判断溢出，此时 int 已经发生回绕。
  • 负数溢出返回 -Integer.MAX_VALUE，会漏掉合法下界 -2147483648。

相似题目

题目 难度 考察点
剑指 Offer 67. 把字符串转换成整数 中等 与本题同题异名，规则一致，代码可直接照搬
7. 整数反转 中等 输入已经是整数，没有解析阶段，只剩溢出判断，且越界时要返回 0 而不是钳制到边界
65. 有效数字 困难 只判断合法性不求值，需支持小数点与指数 e，状态之间有分支，值得真写状态机
165. 比较版本号 中等 要按 . 切成多段整数逐段比较，缺失的段按 0 补齐，考点是分段游标而非溢出
468. 验证IP地址 中等 分段解析加格式校验，考的是分类讨论的完备性，前导零在这里是非法而非可忽略
13. 罗马数字转整数 简单 字符到数值靠查表，需比较相邻两位决定加减，不涉及符号位和溢出
227. 基本计算器 II 中等 在逐位读数之外还要处理运算符优先级，需要用栈保存待计算项