8. 字符串转换整数 (atoi)
题目描述
实现函数 myAtoi(s)，把字符串 s 解析成一个 32 位有符号整数。按下面的顺序处理：
第一步，跳过开头所有空格 ' '。第二步，如果下一个字符是 '-' 或 '+'，读入它作为符号，最多读一个；没有符号则视为正数。
第三步，从当前位置起连续读取数字字符，直到遇到非数字字符或字符串结束。数字前面的 0 不影响数值。一个数字都没读到时，结果为 0。
第四步，若结果小于 -2^31，返回 -2^31；若大于 2^31 - 1，返回 2^31 - 1。其余情况直接返回读到的整数。
示例 1
输入：s = "42" 输出：42
解释：没有空格和符号，直接读入 42。
示例 2
输入：s = " -042" 输出：-42
解释：跳过 3 个空格，读入负号，再读 042，前导零不计，结果为 -42。
示例 3
输入：s = "1337c0d3" 输出：1337
解释：读到 1337 后遇到字母 c，停止。
示例 4
输入：s = "0-1" 输出：0
解释：读入 0 后遇到 '-'，它不是数字，停止，结果为 0。
示例 5
输入：s = "words and 987" 输出：0
解释：第一个字符 w 既不是空格、符号，也不是数字，没有读到任何数字，返回 0。
数据范围
0 <= s.length <= 200s中的字符只可能是大小写英文字母、数字0-9、' '、'+'、'-'和'.'。
解题思路：顺序扫描模拟
用一个下标 i 按规则依次处理三个阶段：空格→符号→数字。读数字时每一步 num = num*10 + 当前数字，并立即检查 sign*num 是否越界，越界就直接返回边界值——不必读完剩下的数字，也保证中间值不会大到溢出 64 位。
为什么正确
读数字阶段的每一步，sign*num 都在 [INT_MIN, INT_MAX] 内，否则已经返回。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
符号最多只读一个："+-12" 读完 + 后遇到 - 不是数字，结果是 0。空格只在开头跳过，"0 123" 只读到 0。越界要在累加过程中判断，而不是读完再判断，否则 C++/Java 里长串数字会先溢出。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def myAtoi(self, s: str) -> int:
INT_MAX, INT_MIN = 2 ** 31 - 1, -2 ** 31
i, n = 0, len(s)
while i < n and s[i] == ' ':
i += 1
sign = 1
if i < n and s[i] in '+-':
if s[i] == '-':
sign = -1
i += 1
num = 0
while i < n and s[i].isdigit():
num = num * 10 + int(s[i])
if sign * num > INT_MAX:
return INT_MAX
if sign * num < INT_MIN:
return INT_MIN
i += 1
return sign * numclass Solution {
public int myAtoi(String s) {
long INT_MAX = 2147483647L, INT_MIN = -2147483648L;
int i = 0, n = s.length();
while (i < n && s.charAt(i) == ' ') {
i++;
}
int sign = 1;
if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
if (s.charAt(i) == '-') {
sign = -1;
}
i++;
}
long num = 0;
while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
num = num * 10 + (s.charAt(i) - '0');
if (sign * num > INT_MAX) {
return (int) INT_MAX;
}
if (sign * num < INT_MIN) {
return (int) INT_MIN;
}
i++;
}
return (int) (sign * num);
}
}class Solution {
public:
int myAtoi(string s) {
const long long INT_MAX_ = 2147483647LL, INT_MIN_ = -2147483648LL;
int i = 0, n = s.size();
while (i < n && s[i] == ' ') {
i++;
}
int sign = 1;
if (i < n && (s[i] == '+' || s[i] == '-')) {
if (s[i] == '-') {
sign = -1;
}
i++;
}
long long num = 0;
while (i < n && isdigit((unsigned char)s[i])) {
num = num * 10 + (s[i] - '0');
if (sign * num > INT_MAX_) {
return (int)INT_MAX_;
}
if (sign * num < INT_MIN_) {
return (int)INT_MIN_;
}
i++;
}
return (int)(sign * num);
}
};func myAtoi(s string) int {
const INT_MAX, INT_MIN = 1<<31 - 1, -1 << 31
i, n := 0, len(s)
for i < n && s[i] == ' ' {
i++
}
sign := 1
if i < n && (s[i] == '+' || s[i] == '-') {
if s[i] == '-' {
sign = -1
}
i++
}
num := 0
for i < n && s[i] >= '0' && s[i] <= '9' {
num = num*10 + int(s[i]-'0')
if sign*num > INT_MAX {
return INT_MAX
}
if sign*num < INT_MIN {
return INT_MIN
}
i++
}
return sign * num
}var myAtoi = function(s) {
const INT_MAX = 2147483647, INT_MIN = -2147483648;
let i = 0; const n = s.length;
while (i < n && s[i] === ' ') {
i++;
}
let sign = 1;
if (i < n && (s[i] === '+' || s[i] === '-')) {
if (s[i] === '-') {
sign = -1;
}
i++;
}
let num = 0;
while (i < n && s[i] >= '0' && s[i] <= '9') {
num = num * 10 + (s.charCodeAt(i) - 48);
if (sign * num > INT_MAX) {
return INT_MAX;
}
if (sign * num < INT_MIN) {
return INT_MIN;
}
i++;
}
return sign * num + 0;
};function myAtoi(s: string): number {
const INT_MAX = 2147483647, INT_MIN = -2147483648;
let i = 0; const n = s.length;
while (i < n && s[i] === ' ') {
i++;
}
let sign = 1;
if (i < n && (s[i] === '+' || s[i] === '-')) {
if (s[i] === '-') {
sign = -1;
}
i++;
}
let num = 0;
while (i < n && s[i] >= '0' && s[i] <= '9') {
num = num * 10 + (s.charCodeAt(i) - 48);
if (sign * num > INT_MAX) {
return INT_MAX;
}
if (sign * num < INT_MIN) {
return INT_MIN;
}
i++;
}
return sign * num + 0;
}其他解法
两者都是一次扫描。模拟法把规则写在控制流里，自动机把规则写在转移表里。
解法 2：有限状态自动机 时间 O(n)，空间 O(1)
定义 start、signed、in_number、end 四个状态，把字符分为空格、符号、数字、其他四类，用一张 4×4 的转移表描述规则。逐字符查表转移：进入 signed 时记录符号，进入 in_number 时累加数字并把绝对值截断到上限，进入 end 就停止。
把易错的 if-else 分支换成一张可以逐格核对的表，规则变复杂时更不容易漏情况，也是编译原理里词法分析的基本思想。对本题这样简单的规则来说代码更长。
class Solution:
def myAtoi(self, s: str) -> int:
INT_MAX, INT_MIN = 2 ** 31 - 1, -2 ** 31
# 状态：0 start，1 signed，2 in_number，3 end
# 列：0 空格，1 符号，2 数字，3 其他
table = [
[0, 1, 2, 3],
[3, 3, 2, 3],
[3, 3, 2, 3],
[3, 3, 3, 3],
]
def col(c):
if c == ' ':
return 0
if c in '+-':
return 1
if c.isdigit():
return 2
return 3
state, sign, num = 0, 1, 0
for c in s:
state = table[state][col(c)]
if state == 1:
sign = -1 if c == '-' else 1
elif state == 2:
num = num * 10 + int(c)
num = min(num, INT_MAX if sign == 1 else -INT_MIN)
elif state == 3:
break
return sign * numclass Solution {
public int myAtoi(String s) {
// 状态：0 start，1 signed，2 in_number，3 end
// 列：0 空格，1 符号，2 数字，3 其他
int[][] table = {
{0, 1, 2, 3},
{3, 3, 2, 3},
{3, 3, 2, 3},
{3, 3, 3, 3},
};
int state = 0, sign = 1;
long num = 0;
for (char c : s.toCharArray()) {
state = table[state][col(c)];
if (state == 1) {
sign = c == '-' ? -1 : 1;
} else if (state == 2) {
num = num * 10 + (c - '0');
num = Math.min(num, sign == 1 ? (long) Integer.MAX_VALUE : -(long) Integer.MIN_VALUE);
} else if (state == 3) {
break;
}
}
return (int) (sign * num);
}
private int col(char c) {
if (c == ' ') return 0;
if (c == '+' || c == '-') return 1;
if (c >= '0' && c <= '9') return 2;
return 3;
}
}class Solution {
public:
int myAtoi(string s) {
// 状态：0 start，1 signed，2 in_number，3 end
// 列：0 空格，1 符号，2 数字，3 其他
int table[4][4] = {
{0, 1, 2, 3},
{3, 3, 2, 3},
{3, 3, 2, 3},
{3, 3, 3, 3},
};
int state = 0, sign = 1;
long long num = 0;
for (char c : s) {
state = table[state][col(c)];
if (state == 1) {
sign = c == '-' ? -1 : 1;
} else if (state == 2) {
num = num * 10 + (c - '0');
num = min(num, sign == 1 ? (long long)INT_MAX : -(long long)INT_MIN);
} else if (state == 3) {
break;
}
}
return (int)(sign * num);
}
int col(char c) {
if (c == ' ') return 0;
if (c == '+' || c == '-') return 1;
if (isdigit(c)) return 2;
return 3;
}
};func myAtoi(s string) int {
// 状态：0 start，1 signed，2 in_number，3 end
// 列：0 空格，1 符号，2 数字，3 其他
table := [4][4]int{
{0, 1, 2, 3},
{3, 3, 2, 3},
{3, 3, 2, 3},
{3, 3, 3, 3},
}
col := func(c byte) int {
if c == ' ' {
return 0
}
if c == '+' || c == '-' {
return 1
}
if c >= '0' && c <= '9' {
return 2
}
return 3
}
state, sign, num := 0, 1, 0
for i := 0; i < len(s); i++ {
c := s[i]
state = table[state][col(c)]
if state == 1 {
if c == '-' {
sign = -1
}
} else if state == 2 {
num = num*10 + int(c-'0')
limit := 2147483647
if sign == -1 {
limit = 2147483648
}
if num > limit {
num = limit
}
} else if state == 3 {
break
}
}
return sign * num
}var myAtoi = function(s) {
// 状态：0 start，1 signed，2 in_number，3 end
// 列：0 空格，1 符号，2 数字，3 其他
const table = [
[0, 1, 2, 3],
[3, 3, 2, 3],
[3, 3, 2, 3],
[3, 3, 3, 3],
];
const col = (c) => {
if (c === ' ') return 0;
if (c === '+' || c === '-') return 1;
if (c >= '0' && c <= '9') return 2;
return 3;
};
let state = 0, sign = 1, num = 0;
for (const c of s) {
state = table[state][col(c)];
if (state === 1) {
sign = c === '-' ? -1 : 1;
} else if (state === 2) {
num = num * 10 + (c.charCodeAt(0) - 48);
num = Math.min(num, sign === 1 ? 2147483647 : 2147483648);
} else if (state === 3) {
break;
}
}
return sign * num;
};function myAtoi(s: string): number {
// 状态：0 start，1 signed，2 in_number，3 end
// 列：0 空格，1 符号，2 数字，3 其他
const table = [
[0, 1, 2, 3],
[3, 3, 2, 3],
[3, 3, 2, 3],
[3, 3, 3, 3],
];
const col = (c: string): number => {
if (c === ' ') return 0;
if (c === '+' || c === '-') return 1;
if (c >= '0' && c <= '9') return 2;
return 3;
};
let state = 0, sign = 1, num = 0;
for (const c of s) {
state = table[state][col(c)];
if (state === 1) {
sign = c === '-' ? -1 : 1;
} else if (state === 2) {
num = num * 10 + (c.charCodeAt(0) - 48);
num = Math.min(num, sign === 1 ? 2147483647 : 2147483648);
} else if (state === 3) {
break;
}
}
return sign * num;
};