加一 - 题目笔记

算法笔记66. 加一 (Plus One)1. 题目描述给定一个由整数数组表示的非负大整数数组每个元素存一个数字最高位在数组首部。将该数加 1并返回结果数组。输入digits [1, 2, 9]输出[1, 3, 0]2. 核心思路贪心遍历 (Greedy Approach)这道题的核心在于处理进位。由于只加 1进位只会发生在当前数字是9的情况下。从后向前遍历数组如果当前位 9直接加 1 并返回数组因为不会产生更高的进位。如果当前位 9将当前位设为0继续循环处理前一位。特殊情况如果循环结束仍未返回例如输入为[9, 9, 9]说明产生了最高位进位。此时直接在数组最前面补一个1即可。3. 代码实现 (Python)Pythonclass Solution: def plusOne(self, digits: List[int]) - List[int]: n len(digits) # 1. 从低位到高位反向遍历 for i in range(n - 1, -1, -1): if digits[i] 9: digits[i] 1 # 找到第一个不需进位的数加 1 return digits # 关键直接返回结果 # 如果是 9则该位变 0继续循环处理前一位 digits[i] 0 # 2. 如果循环走完还没返回说明是 99...9 的情况 # 此时 digits 已全变成 0只需在最前面加个 1 return [1] digits4. 复杂度分析时间复杂度$O(n)$最好情况末尾不是 9只需 $O(1)$。最坏情况全是 9需要遍历一遍整个数组$O(n)$。空间复杂度$O(1)$ 或 $O(n)$如果不算返回数组的空间我们在原数组上操作是 $O(1)$。如果是全 9 情况需要额外构造一个长度为 $n1$ 的结果空间复杂度为 $O(n)$。5. 进阶思考为什么这是最优解避开了数值转换不需要先将数组转成整数Python 虽然支持大整数但在其他语言如 C 中会溢出直接操作数组鲁棒性更强。提前终止一旦遇到不需要进位的位立即return避免了无效的遍历。内存效率相比使用链表数组在连续内存中处理速度更快CPU 缓存友好且不需要额外的指针空间。