题目描述
思路解析动画文字版
核心只有两种结局:这一位加完没满 10 → 当场收工;满了 10 → 本位归 0、进位继续向左。看下面把 299999 加 1 一位位走完。
开始之前:整个数是 299999,我们手里攥着一个要加进去的 1(记成 carry = 1)。指针从最右边出发。
指针走到下标 5,这一位现在是 9。手里还有 carry = 1 要加进来。
这一位加上进位:9 + 1 = 10。满了 10,这位要归 0、进位继续往左带。
下标 5 写成 0(标红的就是它),进位 carry 还是 1,接着去处理它左边那一位。
指针走到下标 4,这一位现在是 9。手里还有 carry = 1 要加进来。
这一位加上进位:9 + 1 = 10。满了 10,这位要归 0、进位继续往左带。
下标 4 写成 0(标红的就是它),进位 carry 还是 1,接着去处理它左边那一位。
指针走到下标 3,这一位现在是 9。手里还有 carry = 1 要加进来。
这一位加上进位:9 + 1 = 10。满了 10,这位要归 0、进位继续往左带。
下标 3 写成 0(标红的就是它),进位 carry 还是 1,接着去处理它左边那一位。
指针走到下标 2,这一位现在是 9。手里还有 carry = 1 要加进来。
这一位加上进位:9 + 1 = 10。满了 10,这位要归 0、进位继续往左带。
下标 2 写成 0(标红的就是它),进位 carry 还是 1,接着去处理它左边那一位。
指针走到下标 1,这一位现在是 9。手里还有 carry = 1 要加进来。
这一位加上进位:9 + 1 = 10。满了 10,这位要归 0、进位继续往左带。
下标 1 写成 0(标红的就是它),进位 carry 还是 1,接着去处理它左边那一位。
指针走到下标 0,这一位现在是 2。手里还有 carry = 1 要加进来。
这一位加上进位:2 + 1 = 3。没满 10,写下它就彻底结束了。
下标 0 写成 3(绿色高亮),进位用完了 carry = 0。左边的位一个都不用碰,可以收工。
一路走完,进位被消化干净,最终结果是 [3,0,0,0,0,0],也就是 299999 + 1 = 300000。
三个高频追问:为何从右起、何时变长、为何不转整数。
参考代码
def plusOne(digits): i = len(digits) - 1 # 从最低位(最右)开始 while i >= 0: if digits[i] < 9: # 不满 9:加 1 就收工 digits[i] += 1 return digits digits[i] = 0 # 是 9:本位归 0,进位继续 i -= 1 return [1] + digits # 一路 9:最高位再补个 1复杂度
- 时间:O(n),最坏情况(全是 9)要从最右一直进位到最左,每位看一次
- 空间:O(1),原地在数组上改;只有全 9 时才新建一个长度加一的数组
易错点
面试追问把动画讲成自己的话
追问为什么要从数组最右边开始处理?
追问什么情况下结果数组会比原来长?
追问能不能把数组转成整数加 1 再转回去?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
Pow(x, n)
LeetCode 50 · 中等 · 沿着 数学 & 几何 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题