企业官网建设流程全解析

• 教程
• 文档
• 知识库

本篇文章基于「算法通关手册」AlgoNote 仓库中的 string-to-integer-atoi.md 题解文档展开，围绕 LeetCode 第 0008 题「字符串转换整数 (atoi)」的完整算法规则、模拟实现、边界条件与复杂度分析进行深入讲解。读完本文，你将掌握如何用单指针线性扫描实现一个严格符合 C/C++atoi语义的myAtoi(s)函数，并能在面试中精准处理前导空格、正负号、非法字符与 32 位有符号整数溢出截断等全部边界场景。

题目定位与背景

本题是 LeetCode 热题中的字符串模拟类经典题，在「算法通关手册」中标记为字符串标签、中等难度。它同时被收录于仓库的 面试 100 题列表 与 面试 200 题列表，可见其在算法面试中的高频地位。题目的核心难点不在于算法本身（仅需一次线性扫描），而在于对题意中繁琐边界规则的逐条精确还原，这正是考察候选人对需求细节把控能力的经典场景。

题目大意与输入约束

给定一个字符串s，要求实现myAtoi(s)函数，使其能转换成一个 32 位有符号整数（类似 C/C++ 中的atoi函数）。需要检测有效性，无法读取时返回0。

输入与规则约束如下：

• 本题中的空白字符只包括空格字符' '；
• 除前导空格或数字后的其余字符串外，请勿忽略任何其他字符；
• 字符串长度满足 $0 \le s.length \le 200$；
• s由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-'和'.'组成。

之所以明确限定字符集与"仅空格"这一细节，是因为真实的 Catoi在具体实现上存在平台差异，而本题将这些规则显式固定下来，避免了歧义——例如真实atoi可能把"1.5"解析为1，而本题规定遇到第一个非数字字符即停止读取，"."之后的内容被忽略。

函数算法规则（六步流程）

官方算法描述是本题一切实现的"规格说明书"，共六步，任何解都必须逐条满足：

1. 丢弃前导空格：读入字符串并丢弃无用的前导空格。
2. 判定符号：检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。
3. 连续读入数字：读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
4. 数值转换：将前面步骤读入的这些数字转换为整数（即"123"->123，"0032"->32）。如果没有读入数字，则整数为0。必要时更改符号（从步骤 2 开始）。
5. 溢出截断：如果整数数超过 32 位有符号整数范围 $[−2^{31}, 2^{31} − 1]$，需要截断这个整数，使其保持在这个范围内。具体来说，小于 $−2^{31}$ 的整数应该被固定为 $−2^{31}$，大于 $2^{31} − 1$ 的整数应该被固定为 $2^{31} − 1$。
6. 返回结果：返回整数作为最终结果。

可以提炼出一个判断要点：只有"前导空格 + 可选正负号 + 连续数字"这一前缀模式才能被合法解析，一旦前缀中出现非数字字符（字母、点号等），解析立即终止；若第一个非空格字符本身就不是合法起始字符，则直接返回0。

示例逐步解析

文档中给出了两个关键示例，用"插入符号^"标记当前读取位置，直观展示了算法逐字符推进的过程。

示例 1：正数基础场景

输入：s = "42" 输出：42

• 第 1 步："42"，当前没有读入字符，因为没有前导空格；
• 第 2 步："42"，当前没有读入字符，因为这里不存在'-'或'+'，符号默认为正；
• 第 3 步：读入"42"，解析得到整数42。

由于42在范围 $[-2^{31}, 2^{31} - 1]$ 内，最终结果为42。

示例 2：前导空格与负号场景

输入：s = " -42" 输出：-42

• 第 1 步：" -42"，读入前导空格但忽视掉；
• 第 2 步：" -42"，读入'-'字符，所以结果应该是负数；
• 第 3 步：" -42"，读入"42"，解析得到整数-42。

由于-42在范围内，最终结果为-42。

解题思路：单指针线性模拟

模拟流程设计

文档给出的解法是直接模拟，核心流程分五步：

1. 先去除前后空格（实际只需去除前导空格，用lstrip()即可）；
2. 检测正负号；
3. 读入数字，并用字符串存储数字结果；
4. 将数字字符串转为整数，并根据正负号转换整数结果；
5. 判断整数范围，并返回最终结果。

完整代码实现

以下是题解文档中的完整参考实现：

class Solution: def myAtoi(self, s: str) -> int: num_str = "" positive = True start = 0 s = s.lstrip() if not s: return 0 if s[0] == '-': positive = False start = 1 elif s[0] == '+': positive = True start = 1 elif not s[0].isdigit(): return 0 for i in range(start, len(s)): if s[i].isdigit(): num_str += s[i] else: break if not num_str: return 0 num = int(num_str) if not positive: num = -num return max(num, -2 ** 31) else: return min(num, 2 ** 31 - 1)

代码关键点逐行解读

• 前导空格处理：s.lstrip()只移除开头的空格字符，与题意"空白字符只包括空格"严格对应。若去除后字符串为空（原串为空或全为空格），直接返回0。
• 符号识别：判断s[0]：
  • 为'-'时置positive = False，并从下标1开始读数字；
  • 为'+'时保持正号，同样从下标1开始；
  • 既非正负号又非数字（如字母'a'、点号'.'），立即返回0。
  • 这里需要注意：符号之后必须紧跟数字才有效，如果s[0]是符号但s[1]不是数字，后续循环不会读入任何字符，num_str为空，最终也会返回0。例如"+a"、"- "都会正确返回0。
• 连续数字读取：从start开始遍历，isdigit()为真则累加进num_str，遇到第一个非数字字符立即break。这意味着"4193 with words"会解析出4193，而"words and 987"因首个字符不是数字而返回0。
• 无数字保护：num_str为空说明没有读到任何数字，返回0，覆盖"+-12"、"--42"等无效符号组合。
• 溢出截断：利用 Python 整数无位数限制的特性先做int()转换，再通过max(num, -2 ** 31)与min(num, 2 ** 31 - 1)分别钳制下界与上界，一次性完成负数下溢与正数上溢的截断，逻辑简洁且无需预先判断长度。

边界用例快速验证

其中"0032" -> 32的效果由int("0032")自动完成，无需手工处理前导零。

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串s的长度。整个流程只对字符串做一次从左到右的线性扫描（lstrip()与数字读取合计至多遍历每个字符一次）。
• 空间复杂度：$O(1)$。虽然代码中用num_str暂存数字字符，但从算法本身看，只使用了常数级别的额外变量（num_str、positive、start），不随输入规模增长；若追求极致，也可直接边扫描边累加数值，将空间严格降至 $O(1)$。

仓库中的同源变体：LCR 192 把字符串转换成整数

值得一提的是，这道题在《剑指 Offer》体系中有同源变体——LCR 192. 把字符串转换成整数 (atoi)，二者算法思想完全一致，仅在描述措辞与函数命名（strToInt）上有所不同。仓库中的该题解给出了几乎相同的模拟实现，可作为对照练习：

class Solution: def strToInt(self, str: str) -> int: num_str = "" positive = True start = 0 s = str.lstrip() if not s: return 0 if s[0] == '-': positive = False start = 1 elif s[0] == '+': positive = True start = 1 elif not s[0].isdigit(): return 0 for i in range(start, len(s)): if s[i].isdigit(): num_str += s[i] else: break if not num_str: return 0 num = int(num_str) if not positive: num = -num return max(num, -2 ** 31) else: return min(num, 2 ** 31 - 1)

对比可见，刷题时掌握一个版本的实现，即可同时覆盖 LeetCode 0008 与 LCR 192 两道题目，性价比很高。

相关学习路径

• 字符串基础概念、比较规则与存储结构可参考 04_01_string_basic.md；
• 全部题解索引见 00_05_solutions_list.md，其中第 0008 题的完整题解位于 string-to-integer-atoi.md。

小结

字符串转换整数 (atoi) 是一道"规则即算法"的典型模拟题：不需要复杂的数据结构与高级算法，拼的是对题意的精确拆解与边界兜底。掌握"去空格 → 判符号 → 连续取数字 → 转整数 → 溢出截断"这条主线，配合isdigit()逐字符校验与max/min钳位技巧，即可在面试中稳定、快速地完成本题，并顺带解决其剑指 Offer 变体。

• 教程
• 文档
• 知识库