LeetCode 66. 加一
题目描述
✅ 66. 加一
题意分析
数组从高位到低位保存一个非负十进制整数，每个元素是一个数字。求这个整数加一后的数字数组，仍按高位在前返回。
输入可能有很多位，不能先转换成普通整数再计算。加一主要影响最低位及连续向前的进位；现有实现会直接修改原数组，只有结果多出一位时才创建新数组。
解法：从低位模拟进位
核心思路
[!blue]
从最右侧开始处理，因为一先加到个位。进入每一轮时，仍然有一份进位需要加到当前位；右边已经处理过的位都是由九加一变成的零。
如果当前位小于九，直接加一即可，结果仍是一个合法数字，进位在这里消失。更高的位完全不受影响，所以可以立即返回原数组，而不必继续扫描。
如果当前位是九，加一得到十，当前位写零，将那一份进位继续传给左侧。这个过程中进位始终只可能是一，因此无需额外保存复杂的加法状态。
若整段循环没有提前返回，说明所有原始数位都是九，进位穿过了最高位，结果长度必须增加一。创建长度为
n + 1的全零数组，只将最高位置一，即可表达新的结果；单独的零输入则会在最低位直接完成加一。
解题步骤
- 从数组最后一个位置开始，向前逐位处理仍未消失的进位。
- 当前位小于九时加一，立即返回原数组。
- 当前位等于九时改成零，继续向前。
- 全部数位都处理完仍未返回时，创建多一位的新数组，首位设为一，返回它。
代码实现
class Solution {
// 非 9 位加一后没有继续进位，直接原数组返回即可。
public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++;
return digits;
}
digits[i] = 0;
}
// 走完整个循环说明全部原位都是九，新结果只需最高位一
int[] res = new int[digits.length + 1];
res[0] = 1;
return res;
}
}
func plusOne(digits []int) []int {
// 非 9 位加一后没有继续进位，直接原数组返回即可。
for i := len(digits) - 1; i >= 0; i-- {
if digits[i] < 9 {
digits[i]++
return digits
}
digits[i] = 0
}
// 走完整个循环说明全部原位都是九，新结果只需最高位一
res := make([]int, len(digits)+1)
res[0] = 1
return res
}
复杂度分析
- 时间复杂度：最坏 $O(n)$，原数全为九时处理全部位并创建新结果；最低位无需进位时为 $O(1)$。
- 空间复杂度：辅助空间为 $O(1)$。若所有位都是九，返回的新数组需要 $O(n)$ 输出空间；其他情况直接返回原数组。
关键点总结
[!green]
- 每轮都带着一份尚未消失的进位，从低位向高位传播。
- 第一个非九位负责吸收进位，高位此后不变，可以提前结束。
- 只有原数每一位都是九时才需要增加长度。
- 按位运算避免依赖原生整数的数值范围。
易错点总结
[!yellow]
- 非九位加一后仍继续循环，会错误改变更高位，或者误进入扩展长度的分支。
- 遇到九只清零却没有继续处理左侧，丢失了进位。
- 全九时返回已经清零的旧数组，遗漏新产生的最高位一。
- 从最左侧开始加一，改变的不是整数的个位，数值含义错误。
- 将全部数字转成整数，输入长度超出类型范围时会溢出，逐位处理没有这个问题。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 67. 二进制求和 | 简单 | 同样从低位处理进位，本题第二个加数固定为1，原题相加两个二进制字符串。 |
| 415. 字符串相加 | 简单 | 同样处理十进制进位，原题加数由字符串给出，本题直接修改数字数组。 |
| 2. 两数相加 | 中等 | 逐位计算并维护进位；本题加一时只传播单次进位，该题链表低位在前可直接遍历相加。 |
| 445. 两数相加 II | 中等 | 逐位计算并维护进位；本题加一时只传播单次进位，该题高位在前需反转或栈辅助。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！