0008. String to Integer (atoi)
==============================
题目信息
--------
:题号: 0008. 字符串转换整数(atoi)
:难度: Medium
:主题: 字符串、解析、状态机、溢出边界
:原题: `LeetCode 0008 `_
:重点: 把前缀语法拆成空格、符号和数字三个阶段,并用负数累积覆盖不对称的 32 位边界
题目重述
--------
给定字符串 ``s``,需要按照固定规则解析其开头,并返回一个 32 位有符号整数:
#. 跳过开头连续出现的普通空格;
#. 读取至多一个 ``+`` 或 ``-`` 作为符号;
#. 从当前位置连续读取十进制数字,遇到第一个非数字字符时停止;
#. 若没有读取到数字,返回 ``0``;
#. 若解析结果小于 ``-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++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
int scanWithWideInteger(const std::string& s) {
int index = 0;
while (index < static_cast(s.size()) && s[index] == ' ') {
++index;
}
int sign = 1;
if (index < static_cast(s.size()) && (s[index] == '+' || s[index] == '-')) {
sign = s[index] == '-' ? -1 : 1;
++index;
}
long long value = 0;
while (index < static_cast(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(sign * value);
}
int scanWithinInt(const std::string& s) {
int index = 0;
while (index < static_cast(s.size()) && s[index] == ' ') {
++index;
}
int sign = 1;
if (index < static_cast(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(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"`` 为例:
.. list-table::
:header-rows: 1
* - 阶段
- 字符
- ``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 位安全。
复杂度分析
~~~~~~~~~~
.. list-table::
:header-rows: 1
* - 方法
- 时间复杂度
- 工作空间
- 边界策略
* - 宽整数累积
- ``O(n)``
- ``O(1)``
- 使用 64 位中间值后钳制
* - 负数累积
- ``O(n)``
- ``O(1)``
- 在 32 位乘减前预判边界
两种方法都只访问从字符串开头到第一个无效字符之间的内容,最坏扫描整个字符串。主解法不创建子串、字符数组或额外状态表。
边界处理
~~~~~~~~
* 只跳过普通空格 ``' '``,不会把其他字符当作前导空白;
* 字符串结束、只有空格或只有符号时,数字循环不执行,返回 ``0``;
* 符号后必须立即出现数字,否则结果为 ``0``;
* 数字前导零只会重复执行 ``value = value * 10``,不会改变结果;
* 遇到第一个非数字字符立即停止,不会在后续位置重新寻找数字;
* 越界判断发生在乘十和减数字之前,避免 32 位有符号整数溢出。