中等

中频

自动机

字符串转换整数 (atoi)

这是一道围绕字符串展开的高频练习。建议先掌握「自动机」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

字符串

题目分析

这道题表面上是在处理「字符串转换整数 (atoi)」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考字符串这些能力。这题适合把输入过程看成状态机，先拆清楚状态，再定义不同字符会触发什么转移。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：按状态机顺序处理空格、符号和数字，边读边构造结果并做溢出截断。

推荐代码

推荐解法：自动机

时间复杂度： O(n)

空间复杂度： O(1)

核心思路：按状态机顺序处理空格、符号和数字，边读边构造结果并做溢出截断。

class Solution {
    public int myAtoi(String str) {
        Automaton automaton = new Automaton();
        int length = str.length();
        for (int i = 0; i < length; ++i) {
            automaton.get(str.charAt(i));
        }
        return (int) (automaton.sign * automaton.ans);
    }
}

class Automaton {
    public int sign = 1;
    public long ans = 0;
    private String state = "start";
    private Map<String, String[]> table = new HashMap<String, String[]>() {{
        put("start", new String[]{"start", "signed", "in_number", "end"});
        put("signed", new String[]{"end", "end", "in_number", "end"});
        put("in_number", new String[]{"end", "end", "in_number", "end"});
        put("end", new String[]{"end", "end", "end", "end"});
    }};

    public void get(char c) {
        state = table.get(state)[get_col(c)];
        if ("in_number".equals(state)) {
            ans = ans * 10 + c - '0';
            ans = sign == 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE);
        } else if ("signed".equals(state)) {
            sign = c == '+' ? 1 : -1;
        }
    }

    private int get_col(char c) {
        if (c == ' ') {
            return 0;
        }
        if (c == '+' || c == '-') {
            return 1;
        }
        if (Character.isDigit(c)) {
            return 2;
        }
        return 3;
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会用状态机思路处理输入，因为它的规则分阶段很明显。

核心过程

先跳过前导空格。
读取可选正负号。
连续读取数字并构造结果。
每一步都提前判断是否会超出 32 位整型范围。

复杂度总结

时间复杂度 O(n)，空间复杂度 O(1)。

面试补一句：这题最容易丢分的不是主体逻辑，而是溢出和停止条件。

核心思路

atoi 真正麻烦的是边界规则很多：前导空格、正负号、数字停止点、以及 32 位溢出。状态机写法把这些规则拆成清晰阶段。

步骤讲解

先跳过前导空格

扫描开头连续空格，直到遇到非空字符。

为什么这样做：题目要求忽略前导空白。

对应代码提示：while (index < n && s.charAt(index) == ' ') index++;

处理可选符号位

若当前字符是 + 或 -，记录符号并前进一步。

为什么这样做：符号会影响最终结果的正负。

对应代码提示：if (s.charAt(index) == '-') sign = -1;

连续读取数字并检测溢出

每读一位数字，都更新当前值；若即将溢出，直接返回边界值。

为什么这样做：整型范围限制是这题最重要的边界之一。

对应代码提示：if (result > Integer.MAX_VALUE / 10 ...) return ...;

易错点

遇到非数字后继续解析

会把非法尾串也算进结果。

正确理解：数字读取阶段一旦遇到非数字，就立即停止。

最后才检查溢出

中间乘 10 和加位时就可能已经越界。

正确理解：每次更新结果前就做溢出判断。

忽略前导空格和符号的顺序

规则顺序写错会让很多边界例子失败。

正确理解：固定流程：空格 -> 符号 -> 数字。

复杂度与适用判断

时间复杂度：O(n)

空间复杂度：O(1)

比其他方案更好在哪里：比一长串 if/else 更结构化，适合覆盖复杂输入规则。

适用判断：字符串解析题若规则明确分阶段，优先考虑状态机视角。

额外提醒

溢出必须在更新结果之前判断。

动画演示

如果你还没完全看懂，可以展开动画演示。

自动机动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

输入字符串:

准备就绪 - 输入字符串，然后点击开始

动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。