LeetCode 8: String to Integer (atoi) (Parsing + Overflow Clamp)
LeetCode 8StringParsingToday we solve LeetCode 8 - String to Integer (atoi).
Source: https://leetcode.com/problems/string-to-integer-atoi/
English
Problem Summary
Implement myAtoi(string s) and convert a string into a 32-bit signed integer. Ignore leading spaces, process optional sign, parse digits, and clamp result into [-2^31, 2^31-1].
Key Insight
The parser is stateful: skip spaces → optional sign → consecutive digits. Once a non-digit appears after parsing starts, stop immediately. Overflow must be checked before multiplying by 10 and adding the next digit.
Algorithm (Step-by-Step)
1) Move pointer past leading spaces.
2) Read optional +/- to determine sign.
3) Iterate while current char is a digit.
4) Before updating result, check if adding the new digit would overflow.
5) If overflow, return INT_MAX or INT_MIN based on sign.
6) Return sign * result.
Complexity Analysis
Time: O(n) where n is string length.
Space: O(1).
Common Pitfalls
- Forgetting to stop at first invalid non-digit after parsing starts.
- Parsing sign after digits (wrong order).
- Overflow check done after updating result (too late).
- Not clamping to 32-bit signed range.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int myAtoi(String s) {
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) == '-')) {
sign = s.charAt(i) == '-' ? -1 : 1;
i++;
}
int ans = 0;
while (i < n && Character.isDigit(s.charAt(i))) {
int d = s.charAt(i) - '0';
if (ans > Integer.MAX_VALUE / 10 || (ans == Integer.MAX_VALUE / 10 && d > 7)) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
ans = ans * 10 + d;
i++;
}
return ans * sign;
}
}func myAtoi(s string) int {
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++
}
ans := 0
for i < n && s[i] >= '0' && s[i] <= '9' {
d := int(s[i] - '0')
if ans > 214748364 || (ans == 214748364 && d > 7) {
if sign == 1 {
return 2147483647
}
return -2147483648
}
ans = ans*10 + d
i++
}
return ans * sign
}class Solution {
public:
int myAtoi(string s) {
int i = 0, n = (int)s.size();
while (i < n && s[i] == ' ') i++;
int sign = 1;
if (i < n && (s[i] == '+' || s[i] == '-')) {
sign = s[i] == '-' ? -1 : 1;
i++;
}
int ans = 0;
while (i < n && isdigit(s[i])) {
int d = s[i] - '0';
if (ans > INT_MAX / 10 || (ans == INT_MAX / 10 && d > 7)) {
return sign == 1 ? INT_MAX : INT_MIN;
}
ans = ans * 10 + d;
i++;
}
return ans * sign;
}
};class Solution:
def myAtoi(self, s: str) -> int:
i, n = 0, len(s)
while i < n and s[i] == ' ':
i += 1
sign = 1
if i < n and s[i] in ['+', '-']:
sign = -1 if s[i] == '-' else 1
i += 1
ans = 0
while i < n and s[i].isdigit():
d = ord(s[i]) - ord('0')
if ans > 214748364 or (ans == 214748364 and d > 7):
return 2147483647 if sign == 1 else -2147483648
ans = ans * 10 + d
i += 1
return ans * signvar myAtoi = function(s) {
let i = 0;
const n = s.length;
while (i < n && s[i] === ' ') i++;
let sign = 1;
if (i < n && (s[i] === '+' || s[i] === '-')) {
sign = s[i] === '-' ? -1 : 1;
i++;
}
let ans = 0;
while (i < n && s[i] >= '0' && s[i] <= '9') {
const d = s.charCodeAt(i) - '0'.charCodeAt(0);
if (ans > 214748364 || (ans === 214748364 && d > 7)) {
return sign === 1 ? 2147483647 : -2147483648;
}
ans = ans * 10 + d;
i++;
}
return ans * sign;
};中文
题目概述
实现 myAtoi(string s)：将字符串转换为 32 位有符号整数。需要跳过前导空格、处理可选正负号、读取连续数字，并将结果限制在 [-2^31, 2^31-1]。
核心思路
这是一个按状态推进的解析流程：先跳空格，再读符号，再读数字。数字读取开始后，遇到非数字立即停止。溢出必须在 ans = ans * 10 + d 之前判断。
算法步骤
1）跳过前导空格。
2）读取可选的 + / -。
3）循环读取连续数字。
4）每次更新前先做溢出判断。
5）若会溢出，按符号返回 INT_MAX 或 INT_MIN。
6）最终返回 sign * ans。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
常见陷阱
- 读到非数字后没有及时停止。
- 符号处理顺序写错（在数字之后才处理）。
- 先更新再判溢出。
- 忘记限制到 32 位有符号整数范围。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int myAtoi(String s) {
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) == '-')) {
sign = s.charAt(i) == '-' ? -1 : 1;
i++;
}
int ans = 0;
while (i < n && Character.isDigit(s.charAt(i))) {
int d = s.charAt(i) - '0';
if (ans > Integer.MAX_VALUE / 10 || (ans == Integer.MAX_VALUE / 10 && d > 7)) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
ans = ans * 10 + d;
i++;
}
return ans * sign;
}
}func myAtoi(s string) int {
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++
}
ans := 0
for i < n && s[i] >= '0' && s[i] <= '9' {
d := int(s[i] - '0')
if ans > 214748364 || (ans == 214748364 && d > 7) {
if sign == 1 {
return 2147483647
}
return -2147483648
}
ans = ans*10 + d
i++
}
return ans * sign
}class Solution {
public:
int myAtoi(string s) {
int i = 0, n = (int)s.size();
while (i < n && s[i] == ' ') i++;
int sign = 1;
if (i < n && (s[i] == '+' || s[i] == '-')) {
sign = s[i] == '-' ? -1 : 1;
i++;
}
int ans = 0;
while (i < n && isdigit(s[i])) {
int d = s[i] - '0';
if (ans > INT_MAX / 10 || (ans == INT_MAX / 10 && d > 7)) {
return sign == 1 ? INT_MAX : INT_MIN;
}
ans = ans * 10 + d;
i++;
}
return ans * sign;
}
};class Solution:
def myAtoi(self, s: str) -> int:
i, n = 0, len(s)
while i < n and s[i] == ' ':
i += 1
sign = 1
if i < n and s[i] in ['+', '-']:
sign = -1 if s[i] == '-' else 1
i += 1
ans = 0
while i < n and s[i].isdigit():
d = ord(s[i]) - ord('0')
if ans > 214748364 or (ans == 214748364 and d > 7):
return 2147483647 if sign == 1 else -2147483648
ans = ans * 10 + d
i += 1
return ans * signvar myAtoi = function(s) {
let i = 0;
const n = s.length;
while (i < n && s[i] === ' ') i++;
let sign = 1;
if (i < n && (s[i] === '+' || s[i] === '-')) {
sign = s[i] === '-' ? -1 : 1;
i++;
}
let ans = 0;
while (i < n && s[i] >= '0' && s[i] <= '9') {
const d = s.charCodeAt(i) - '0'.charCodeAt(0);
if (ans > 214748364 || (ans === 214748364 && d > 7)) {
return sign === 1 ? 2147483647 : -2147483648;
}
ans = ans * 10 + d;
i++;
}
return ans * sign;
};
Comments