题目描述
思路解析动画文字版
记住这四步顺序,下面每一帧都在套它。
把字符串摊成一格一格。橙色指针从最左边出发,逐个字符往右走。右下角的 RESULT 实时显示「现在在第几步、正负、累加到多少」。
下标 0 是空格。规则第一步「跳过前导空格」——什么都不做,指针往右挪一格。开头的空格全这样一个个跳掉。
下标 1 是空格。规则第一步「跳过前导空格」——什么都不做,指针往右挪一格。开头的空格全这样一个个跳掉。
下标 2 是符号「-」。空格跳完后,紧接着的第一个 +/- 决定正负——这里是「-」,所以结果是负数。符号只认这一个,之后再出现 +/- 都算非法、会触发停。
下标 3 是数字 4。读数字的核心公式:num = num × 10 + 当前位。先把原来的 0 乘 10「腾出个位」,再把 4 加上去。下一帧落值。
落值:num 变成 4。绿色高亮的就是目前已经吃进结果的数字位。继续往后看下一个字符是不是数字。
下标 4 是数字 2。读数字的核心公式:num = num × 10 + 当前位。先把原来的 4 乘 10「腾出个位」,再把 2 加上去。下一帧落值。
落值:num 变成 42。绿色高亮的就是目前已经吃进结果的数字位。继续往后看下一个字符是不是数字。
下标 5 是「a」,不是数字——读数字阶段遇到第一个非数字就立刻停,后面的「abc」一律不看。把累加出的 42 乘上符号,最终结果 -42。
回看整条路径:蓝色是跳过的空格和符号,绿色是真正构成数字的那几位。指针从左到右只走一遍,O(n)。这就是「状态机」——每个字符只看一次,按当前阶段决定怎么处理。
边界要全想到:开头不合法返回 0、超界截断到边界、多个符号只认第一个。
三个高频追问:为什么手写、符号后空格怎么办、规则边界在哪。
参考代码
def myAtoi(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 "+-": # ② 读符号 sign = -1 if s[i] == "-" else 1 i += 1 num = 0 while i < n and s[i].isdigit(): # ③ 逐位累加 num = num * 10 + (ord(s[i]) - ord("0")) if sign * num <= INT_MIN: return INT_MIN # ④ 截断 if sign * num >= INT_MAX: return INT_MAX i += 1 return sign * num复杂度
- 时间:O(n),每个字符最多看一次,指针只向右走一遍
- 空间:O(1),只用几个变量 i / sign / num,不开额外结构
易错点
面试追问把动画讲成自己的话
追问为什么不直接用语言自带的 int(s) / Integer.parseInt?
追问怎么处理「+ 42」这种符号后有空格的?
追问如果允许前后都有空格、中间也有逗号分隔呢?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
最长公共前缀
LeetCode 14 · 简单 · 沿着 数组 & 哈希 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题