0008. String to Integer (atoi)¶
题目信息¶
- 题号:
字符串转换整数(atoi)
- 难度:
Medium
- 主题:
字符串、解析、状态机、溢出边界
- 原题:
- 重点:
把前缀语法拆成空格、符号和数字三个阶段,并用负数累积覆盖不对称的 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++ 实现¶
#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" 为例:
阶段 |
字符 |
|
原 |
新 |
动作 |
|---|---|---|---|---|---|
空格 |
三个空格 |
1 |
0 |
0 |
移动到负号 |
符号 |
|
-1 |
0 |
0 |
记录负号 |
数字 |
|
-1 |
0 |
-1204 |
逐位乘十减数字 |
停止 |
|
-1 |
-1204 |
-1204 |
结束解析 |
负号输入直接返回 value = -1204。后面的 7 位于第一个非数字字符之后,不再参与解析。
代码演进¶
scanWithWideInteger 把解析分成空格、符号和数字三个顺序阶段,使用一次循环累积数字,并依靠 long long 在更新后检查范围。
scanWithinInt 保留相同的前缀扫描结构,把正绝对值改为负数累积。宽整数和更新后的范围检查消失,替换为乘减之前的统一边界判断。
公开入口采用 scanWithinInt。它只扫描有效前缀,使用 O(1) 状态,并在所有中间步骤中保持 32 位安全。
复杂度分析¶
方法 |
时间复杂度 |
工作空间 |
边界策略 |
|---|---|---|---|
宽整数累积 |
|
|
使用 64 位中间值后钳制 |
负数累积 |
|
|
在 32 位乘减前预判边界 |
两种方法都只访问从字符串开头到第一个无效字符之间的内容,最坏扫描整个字符串。主解法不创建子串、字符数组或额外状态表。
边界处理¶
只跳过普通空格
' ',不会把其他字符当作前导空白;字符串结束、只有空格或只有符号时,数字循环不执行,返回
0;符号后必须立即出现数字,否则结果为
0;数字前导零只会重复执行
value = value * 10,不会改变结果;遇到第一个非数字字符立即停止,不会在后续位置重新寻找数字;
越界判断发生在乘十和减数字之前,避免 32 位有符号整数溢出。