如何实现字符串转整数（atoi）？（LeetCode 8）

简化版

实现 myAtoi：把字符串转成 32 位有符号整数，规则是——① 跳过前导空格；② 读一个可选的正负号；③ 读连续数字直到非数字字符停止；④ 结果超出 int 范围 [-2³¹, 2³¹-1] 则夹到边界值。难点全在边界处理：空格、符号、非法字符、以及最关键的整型溢出（要在累加前判断是否会越界，不能等溢出后再补救）。

详细版

int myAtoi(String s) {
    int i = 0, n = s.length();
    while (i < n && s.charAt(i) == ' ') i++;        // ① 跳过前导空格
    if (i == n) return 0;

    int sign = 1;
    if (s.charAt(i) == '+' || s.charAt(i) == '-') { // ② 读符号
        sign = s.charAt(i) == '-' ? -1 : 1;
        i++;
    }

    int res = 0;
    while (i < n && Character.isDigit(s.charAt(i))) { // ③ 读数字
        int digit = s.charAt(i) - '0';
        // ④ 溢出判断：累加前先判，防止越界
        if (res > (Integer.MAX_VALUE - digit) / 10) {
            return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }
        res = res * 10 + digit;
        i++;
    }
    return sign * res;
}

四步：跳空格 → 读符号 → 读数字 → 边读边判溢出。
溢出必须提前判：res * 10 + digit 一旦溢出 int 就得到错误负值，所以在乘加之前用 res > (MAX - digit) / 10 判断。
越界处理：正溢出返回 Integer.MAX_VALUE，负溢出返回 Integer.MIN_VALUE。
复杂度：O(n) 时间、O(1) 空间。

完整版教学

一、这题考的是「边界处理的严谨性」

atoi 算法本身不难（读数字累加），但它是经典的「细节考察题」——面试官想看你能否把所有边界情况都想全、处理干净：前导空格、正负号、中途遇到非数字、空字符串、纯符号无数字、以及最容易翻车的整型溢出。写这题要像状态机一样，一步步严格推进。

这些规则有严格先后关系：空格只能出现在有效前缀之前，符号只能紧跟前导空格，数字必须连续。只要进入数字阶段后遇到其他字符，解析就结束，不能越过非法字符继续寻找后续数字。

二、四个步骤按顺序处理

① 跳过前导空格：从头 while 跳过所有空格。注意只跳前导空格，数字中间或之后的空格视为结束符。

② 读可选符号：空格后若是 + 或 -，记录符号并前进一位。只能有一个符号，"+-2" 这种第二个符号会在读数字阶段被当作非法字符停止。

③ 读连续数字：从当前位置读连续的数字字符，char - '0' 转数值，res = res * 10 + digit 累加。一旦遇到非数字字符立即停止（不管后面还有什么）。

④ 应用符号：返回 sign * res（溢出已在步骤③处理）。

三、溢出处理：必须在累加前判断（核心难点）

这是本题的灵魂。res = res * 10 + digit 如果 res 已经很大，这一步会溢出 int，溢出后 res 变成错误的负数，再判断就晚了。所以要在做乘加之前，预判它会不会越界：

int 上限 Integer.MAX_VALUE = 2147483647。
若 res > (Integer.MAX_VALUE - digit) / 10，说明 res * 10 + digit 将超过 MAX_VALUE——立即返回边界值（正号返 MAX_VALUE，负号返 MIN_VALUE）。

为什么这样判：把 res * 10 + digit <= MAX 变形为 res <= (MAX - digit) / 10，反向即溢出条件。这样在溢出发生前就拦截。

也有做法用 long 累加再判范围（res > Integer.MAX_VALUE），简单但依赖更大的类型；若要求纯 int，就得用上面的「提前判断」。负数边界 MIN_VALUE = -2147483648 的绝对值比 MAX 多 1，用「统一按正数累加、最后乘符号 + 分别夹边界」的写法能正确覆盖。

四、各种边界情况清单

空字符串 / 全是空格：返回 0。
纯符号无数字（"+", "-"）：读符号后没有数字，res=0，返回 0。
数字前有非法字符（"abc123", " -0012a"）："abc..." 开头非空格非符号非数字，直接返回 0；" -0012a" 读到 a 停止，得 -12。
前导零（"0032"）：累加时前导零不影响，得 32。
中间空格 / 小数点（"3.14", "1 2"）：遇到 . 或空格就停，"3.14" → 3。
溢出（"91283472332"）：超过 MAX，返回 2147483647。

把这些都测一遍，代码才算健壮。

五、状态机视角（进阶理解）

LeetCode 官方题解用**确定有限状态机（DFA）**建模：状态有「start（读空格/符号前）、signed（读符号）、in_number（读数字）、end（结束）」，用一张转移表根据当前字符类型（空格/符号/数字/其他）决定状态迁移。这种写法把边界逻辑表格化，更不易漏 case，是工程/编译器里 lexer 的思路。面试能提到「可以用状态机建模」是加分项。

六、用状态顺序拒绝“回头解析”

atoi 的关键不是数位累加，而是字符类别出现的顺序：前导空格只能在开始阶段，符号最多一个且必须在数字前，进入数字阶段后遇到其他字符立即停止。解析器不应跳过中间非法字符后继续找数字，否则会把 "12a34" 错读成 1234。

输入 "   -42xyz"
start: 跳过 3 个空格
signed: 读取 -，sign=-1
number: 读 4，ans=4
number: 读 2，ans=42
遇 x 立即停止
返回 -42

校验维度	本题必须保持的结论
循环/递推不变量	ans 始终是已消费连续数字前缀的非负幅值，sign 单独保存且只设置一次。
边界条件	没有数字时返回 0；越界时钳制到 `Integer.MIN_VALUE` 或 `Integer.MAX_VALUE`。
复杂度与代价	每个字符最多读取一次 O(n)，只维护索引、符号和累积值 O(1)。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

字符串题首先要固定“处理的是字符、UTF-16 代码单元还是 Unicode 码点”，再讨论下标与窗口。本题应先复述这条不变量：ans 始终是已消费连续数字前缀的非负幅值，sign 单独保存且只设置一次。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“输入 ” -42xyz””开始手推，最后应得到“返回 -42”。
边界复核：没有数字时返回 0；越界时钳制到 Integer.MIN_VALUE 或 Integer.MAX_VALUE。
代价复核：每个字符最多读取一次 O(n)，只维护索引、符号和累积值 O(1)。
用空串、单字符、全相同字符和首尾命中检查下标边界。
涉及窗口或双指针时，明确区间是闭区间还是左闭右开，并在移动后再判断长度。
涉及计数数组时，先确认题目字符集；超出小写英文字母就不能硬套 26 个桶。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“ans 始终是已消费连续数字前缀的非负幅值，sign 单独保存且只设置一次。”这条正确性主线不能省。

八、常见误区与追问

误区：可以先 trim 再任意查找第一个数字。 atoi 只接受规定前缀，遇到非数字终止，不能跳过中间字符。
误区：+-12 应解析为 -12。 符号只能出现一次，第二个符号使数字部分为空，应返回 0。
误区：累加后再检查 int 溢出即可。 若累积变量本身是 int，乘加已经溢出，事后值不再可信。
追问：为什么边界最后一位正数是 7、负数是 8？ int 范围不对称：最大 2147483647，最小 -2147483648。
追问："words and 987" 返回什么？ 首个非空字符不是符号或数字，未读到数字，因此返回 0。
追问：状态机写法的优势是什么？ 它显式限制字符类别转移，适合扩展规则并减少顺序分支错误。

九、加强记忆

字符串转整数 atoi = 四步 + 严格边界处理：① 跳前导空格 → ② 读可选正负号 → ③ 读连续数字累加 res=res*10+digit，遇非数字即停 → ④ 乘符号返回。灵魂是溢出必须在累加前预判：res > (Integer.MAX_VALUE - digit) / 10 就返回边界（正 MAX_VALUE、负 MIN_VALUE），不能等溢出后补救。边界清单：空串/纯符号返 0、非法开头返 0、中途非数字截断、前导零忽略。进阶可用 DFA 状态机建模。核心：四步顺序走，溢出提前判。

简化版

详细版