0008. String to Integer (atoi)

题目信息

题号:
  1. 字符串转换整数(atoi)

难度:

Medium

主题:

字符串、解析、状态机、溢出边界

原题:

LeetCode 0008

重点:

把前缀语法拆成空格、符号和数字三个阶段,并用负数累积覆盖不对称的 32 位边界

题目重述

给定字符串 s,需要按照固定规则解析其开头,并返回一个 32 位有符号整数:

  1. 跳过开头连续出现的普通空格;

  2. 读取至多一个 + 或 - 作为符号;

  3. 从当前位置连续读取十进制数字,遇到第一个非数字字符时停止;

  4. 若没有读取到数字,返回 0;

  5. 若解析结果小于 -2^31,返回 -2^31;若大于 2^31 - 1,返回 2^31 - 1。

这里只识别字符串开头的合法前缀,不会越过无效字符继续寻找数字。字符串长度位于 [0, 200],可能包含英文字母、数字、空格、+、- 和 .。

自建示例

  • 普通正数:s = "42",返回 42;

  • 空格、符号和前导零:s = "   -001204x7",在 x 处停止,返回 -1204;

  • 非数字截断:s = "4193 with words",只读取连续数字前缀,返回 4193;

  • 无效开头:s = "words and 987",第一个非空格字符不是符号或数字,返回 0;

  • 符号后为空格:s = "  + 17",符号后没有立即出现数字,返回 0;

  • 重复符号:s = "--12",第二个符号终止数字读取,返回 0;

  • 正向溢出:s = "91283472332",返回 2147483647;

  • 负向溢出:s = "-91283472332",返回 -2147483648;

  • 空字符串:s = "",返回 0。

C++ 实现

#include <climits>
#include <string>

class Solution {
private:
    int scanWithWideInteger(const std::string& s) {
        int index = 0;
        while (index < static_cast<int>(s.size()) && s[index] == ' ') {
            ++index;
        }
        int sign = 1;
        if (index < static_cast<int>(s.size()) && (s[index] == '+' || s[index] == '-')) {
            sign = s[index] == '-' ? -1 : 1;
            ++index;
        }
        long long value = 0;
        while (index < static_cast<int>(s.size()) && s[index] >= '0' && s[index] <= '9') {
            value = value * 10 + s[index] - '0';
            if (sign == 1 && value > INT_MAX) {
                return INT_MAX;
            }
            if (sign == -1 && -value < INT_MIN) {
                return INT_MIN;
            }
            ++index;
        }
        return static_cast<int>(sign * value);
    }

    int scanWithinInt(const std::string& s) {
        int index = 0;
        while (index < static_cast<int>(s.size()) && s[index] == ' ') {
            ++index;
        }
        int sign = 1;
        if (index < static_cast<int>(s.size()) && (s[index] == '+' || s[index] == '-')) {
            sign = s[index] == '-' ? -1 : 1;
            ++index;
        }
        const int limit = sign == -1 ? INT_MIN : -INT_MAX;
        int value = 0;
        while (index < static_cast<int>(s.size()) && s[index] >= '0' && s[index] <= '9') {
            const int digit = s[index] - '0';
            if (value < limit / 10 || (value == limit / 10 && -digit < limit % 10)) {
                return sign == -1 ? INT_MIN : INT_MAX;
            }
            value = value * 10 - digit;
            ++index;
        }
        return sign == -1 ? value : -value;
    }

public:
    int myAtoi(std::string s) {
        return scanWithinInt(s);
    }
};

题解

前缀语法

本题不是在字符串任意位置搜索整数,而是识别从下标 0 开始的一段固定前缀。合法字符顺序只能是 若干空格 → 可选符号 → 连续数字。

三个阶段一旦离开就不会返回:

  • 空格阶段结束后,后续空格会直接终止数字读取;

  • 符号阶段最多消费一个字符,第二个符号不会被接受;

  • 数字阶段遇到第一个非数字字符后立即停止,后面的字符全部忽略。

因此 "words 42" 返回 0,而 "42words17" 返回 42。解析指针始终只向右移动,不需要回溯。

宽整数累积

最直接的整数实现是把符号与绝对值分开。数字阶段每读取一个 digit,执行 value = value * 10 + digit,把已有数字左移一位并追加当前数字。

scanWithWideInteger 使用 long long 保存 value,因此可以先完成当前乘加,再与 INT_MAX 或 INT_MIN 比较并钳制。它删除了字符缓冲区和二次转换,只保留一次顺序扫描。

这版代码清楚,但边界安全依赖更宽整数。为了让中间状态始终保持在 32 位范围内,需要在乘十和追加数字之前完成判断。

负数累积

32 位有符号范围并不对称:INT_MAX 是 2147483647,INT_MIN 是 -2147483648。若始终累积非负绝对值,负数最小值的绝对值无法放入 int。

主解法让 value 始终非正,每次执行 value = value * 10 - digit。正数最终返回 -value,负数直接返回 value。这样两种符号的中间值都能落在 int 范围内,包括 INT_MIN。

根据符号选择允许的最小值:

  • 负数使用 limit = INT_MIN;

  • 正数使用 limit = -INT_MAX。

两种情况都转化为同一个要求:追加数字后的 value 不能小于 limit。

乘减边界

下一状态为 value * 10 - digit。危险运算发生前,先比较 value 与 limit / 10:

  • value < limit / 10 时,单独乘十就会低于边界;

  • value > limit / 10 时,本次追加一定安全;

  • 两者相等时,需要继续比较最后一位,要求 -digit >= limit % 10。

因此越界条件统一为 value < limit / 10 || (value == limit / 10 && -digit < limit % 10)。

正数对应的负边界是 -2147483647,最后一位限制为 -7;负数边界是 -2147483648,最后一位限制为 -8。同一段判断自然覆盖两侧钳制。

状态推演

以 s = "   -001204x7" 为例:

阶段

字符

sign

原 value

新 value

动作

空格

三个空格

1

0

0

移动到负号

符号

-

-1

0

0

记录负号

数字

0, 0, 1, 2, 0, 4

-1

0

-1204

逐位乘十减数字

停止

x

-1

-1204

-1204

结束解析

负号输入直接返回 value = -1204。后面的 7 位于第一个非数字字符之后,不再参与解析。

代码演进

scanWithWideInteger 把解析分成空格、符号和数字三个顺序阶段,使用一次循环累积数字,并依靠 long long 在更新后检查范围。

scanWithinInt 保留相同的前缀扫描结构,把正绝对值改为负数累积。宽整数和更新后的范围检查消失,替换为乘减之前的统一边界判断。

公开入口采用 scanWithinInt。它只扫描有效前缀,使用 O(1) 状态,并在所有中间步骤中保持 32 位安全。

复杂度分析

方法

时间复杂度

工作空间

边界策略

宽整数累积

O(n)

O(1)

使用 64 位中间值后钳制

负数累积

O(n)

O(1)

在 32 位乘减前预判边界

两种方法都只访问从字符串开头到第一个无效字符之间的内容,最坏扫描整个字符串。主解法不创建子串、字符数组或额外状态表。

边界处理

  • 只跳过普通空格 ' ',不会把其他字符当作前导空白;

  • 字符串结束、只有空格或只有符号时,数字循环不执行,返回 0;

  • 符号后必须立即出现数字,否则结果为 0;

  • 数字前导零只会重复执行 value = value * 10,不会改变结果;

  • 遇到第一个非数字字符立即停止,不会在后续位置重新寻找数字;

  • 越界判断发生在乘十和减数字之前,避免 32 位有符号整数溢出。