0066. Plus One¶
题目信息¶
- 题号:
加一
- 难度:
Easy
- 主题:
数组、十进制进位、反向扫描
- 原题:
- 重点:
从整数还原限制,推导到只处理十进制末尾进位链
题目重述¶
非空数组 digits 按从最高位到最低位的顺序表示一个非负十进制整数。除整数 0 外,数组没有前导零。
返回该整数加一后的数字数组。
约束为 1 <= digits.length <= 100、0 <= digits[i] <= 9。
自建示例¶
输入:digits = [3,4,8]
输出:[3,4,9]
最低位小于 9,加一后不会继续产生进位。
输入:digits = [8,9,9]
输出:[9,0,0]
末尾两个 9 依次变为 0,进位最终由最高位 8 吸收。
输入:digits = [9,9]
输出:[1,0,0]
全部原有数位都传出进位,因此结果需要增加一个最高位。
C++ 实现¶
#include <vector>
class Solution {
private:
std::vector<int> copyAndPropagate(
const std::vector<int>& digits
) {
std::vector<int> result = digits;
for (int index = static_cast<int>(result.size()) - 1;
index >= 0;
--index) {
if (result[index] < 9) {
++result[index];
return result;
}
result[index] = 0;
}
result.insert(result.begin(), 1);
return result;
}
std::vector<int> mutateInPlace(std::vector<int>& digits) {
for (int index = static_cast<int>(digits.size()) - 1;
index >= 0;
--index) {
if (digits[index] < 9) {
++digits[index];
return digits;
}
digits[index] = 0;
}
digits.insert(digits.begin(), 1);
return digits;
}
public:
std::vector<int> plusOne(std::vector<int>& digits) {
return mutateInPlace(digits);
}
};
题解¶
整数还原限制¶
最直观的做法是把数组还原成普通整数,加一后再拆成数字数组。但数组最多包含 100 个十进制数位,远超固定宽度 整数的表示范围。即使最终操作只有加一,中间的整数还原仍会溢出。
数组本身已经给出了十进制数位,因此只需模拟竖式加法中的进位传播。
末尾进位链¶
加一从最低位开始。当前位只有两种情况:
数位小于 9:该位增加 1,不再产生进位;
数位等于 9:该位变为 0,并把进位继续传向左侧。
所以真正可能变化的部分只是数组末尾连续的 9,以及它左侧第一个非 9 数位。例如:
[4,8,9,9]
^^^^^
末尾两个 9 变成 0,数位 8 增加为 9,更高位 4 保持不变。
扫描不变量¶
从右向左扫描到下标 index 时,右侧已经处理过的数位全部属于原数组末尾连续的 9,并已被正确改写为 0;
当前仍有一个值为 1 的进位等待处理。
若当前数位小于 9,它可以吸收这个进位。该位加一后不会再产生新进位,因此左侧更高位无需改变,算法可以立即 返回。
若当前数位等于 9,它加一后应变为 0,进位继续存在,不变量在下一轮仍成立。
全 9 情况¶
若扫描越过最高位仍未返回,说明原数组的每一位都是 9:
99...9 + 1 = 100...0
循环已经把原有数位全部改写为 0,只需在数组最前面插入 1。结果长度从 n 增加到 n + 1,并且这也是
唯一会扩展数组长度的情况。
原地修改¶
copyAndPropagate 先复制输入,再在副本中传播进位。它保持调用者的数组不变,语义清晰,但需要保存一个完整
工作副本。
题目接口允许修改 digits,因此主方法 mutateInPlace 直接覆盖原数组。普通情况只改写末尾一段;全 9
情况还需要在首部插入 1。公开入口调用该方法,避免无必要的整数组复制。
结果规范¶
输入除单个 0 外没有前导零。普通情况不会把原最高位改成 0;全 9 情况新增的最高位是 1。因此两种分支都会 返回规范的十进制表示。
数字 0 也由同一逻辑覆盖:[0] 的最低位小于 9,直接变为 [1]。
方法关系¶
两种实现使用完全相同的进位不变量,区别只在结果存储位置:
复制方案保持输入不变;
原地方案复用输入数组,减少工作空间。
优化的核心不是改变扫描次数,而是识别出加一只影响末尾进位链,并在接口允许时直接复用原数组。
复杂度分析¶
设数组长度为 n。
复制方案需要 O(n) 时间复制数组,最坏再扫描全部数位;总时间为 O(n),工作副本占用 O(n) 空间。
原地方案最坏扫描全部数位,时间为 O(n)。除返回数组本身外只使用常数个变量,额外空间为 O(1);全 9
情况下首部插入会移动原有元素,但仍属于 O(n) 时间。