力扣-8. 字符串转整数（String to Integer atoi）

最后编辑于2025-06-01

8. 字符串转整数（String to Integer, atoi）

Medium

实现 myAtoi(string s) 函数，将字符串转换为 32 位带符号整数（类似 C/C++ 的 atoi）。算法规则如下：

  1. 读取并忽略开头的空白字符。
  2. 检查下一个字符是否为 - 或 +，若是则记录符号并读取该字符；否则默认正数。
  3. 继续读取后续的数字字符直到遇到非数字或字符串末尾，其他字符均忽略。
  4. 将读取的数字字符转换为整数（例如 “0032” -> 32）；若没有读取到任何数字，则返回 0。根据步骤 2 中的符号调整正负。
  5. 若转换后的整数超出 32 位带符号整数范围 [-2^31, 2^31 - 1]，则截断为边界值。
  6. 返回最终结果。

示例 1：

输入： s = "42"
输出： 42

示例 2：

输入： s = " -42"
输出： -42

示例 3：

输入： s = "4193 with words"
输出： 4193

示例 4：

输入： s = "words and 987"
输出： 0

示例 5：

输入： s = "-91283472332"
输出： -2147483648

约束：

  • 0 <= s.length <= 200
  • s 由大小写英文字母、数字、空格、+、-、. 组成

解题思路（要点）

此题本质是对字符串进行逐字符解析并做边界处理，关键点：

  • 按照指定顺序处理：跳过前导空格 -> 读取可选符号 -> 连续读取数字字符。
  • 在逐位构造整数时必须做溢出检测，避免超出 32 位范围；常见做法是在将 base 乘 10 并加上新数位之前判断 base > INT_MAX/10 或 base == INT_MAX/10 && digit > 7（针对正数）等情况并直接返回边界值。
  • 只处理前导空格和首段连续数字，遇到其他非数字字符即停止解析。

实现上可直接按流程写模拟解析（指针推进、条件判断），也可用有限状态机（状态：起始、符号、数字、结束）来严格控制输入流的处理。

C++ 实现（直接模拟）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int myAtoi(string str) {
        if (str.empty()) return 0;
        int sign = 1, base = 0, i = 0, n = str.size();
        // 跳过前导空格
        while (i < n && str[i] == ' ') ++i;
        // 读取符号
        if (i < n && (str[i] == '+' || str[i] == '-')) {
            sign = (str[i++] == '+') ? 1 : -1;
        }
        // 读取数字并转换
        while (i < n && str[i] >= '0' && str[i] <= '9') {
            int digit = str[i++] - '0';
            // 溢出检测
            if (base > INT_MAX / 10 || (base == INT_MAX / 10 && digit > 7)) {
                return (sign == 1) ? INT_MAX : INT_MIN;
            }
            base = base * 10 + digit;
        }
        return base * sign;
    }
};
  • 时间复杂度： O(n)（一次线性扫描）
  • 空间复杂度： O(1)

作者想说的话：
字符串转整数主要考验对输入流的严格解析能力与边界判断：先按步骤跳过空白、读取符号、逐位累加数字并实时做溢出检测。使用有限状态机可以让实现更规范、更易验证，但对该题直接流程化实现也很清晰。