0066. Plus One
==============
题目信息
--------
:题号: 0066. 加一
:难度: Easy
:主题: 数组、十进制进位、反向扫描
:原题: `LeetCode 0066 `_
:重点: 从整数还原限制,推导到只处理十进制末尾进位链
题目重述
--------
非空数组 ``digits`` 按从最高位到最低位的顺序表示一个非负十进制整数。除整数 0 外,数组没有前导零。
返回该整数加一后的数字数组。
约束为 ``1 <= digits.length <= 100``、``0 <= digits[i] <= 9``。
自建示例
--------
.. code-block:: text
输入:digits = [3,4,8]
输出:[3,4,9]
最低位小于 9,加一后不会继续产生进位。
.. code-block:: text
输入:digits = [8,9,9]
输出:[9,0,0]
末尾两个 9 依次变为 0,进位最终由最高位 8 吸收。
.. code-block:: text
输入:digits = [9,9]
输出:[1,0,0]
全部原有数位都传出进位,因此结果需要增加一个最高位。
C++ 实现
--------
.. code-block:: cpp
#include
class Solution {
private:
std::vector copyAndPropagate(
const std::vector& digits
) {
std::vector result = digits;
for (int index = static_cast(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 mutateInPlace(std::vector& digits) {
for (int index = static_cast(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 plusOne(std::vector& digits) {
return mutateInPlace(digits);
}
};
题解
----
整数还原限制
~~~~~~~~~~~~
最直观的做法是把数组还原成普通整数,加一后再拆成数字数组。但数组最多包含 100 个十进制数位,远超固定宽度
整数的表示范围。即使最终操作只有加一,中间的整数还原仍会溢出。
数组本身已经给出了十进制数位,因此只需模拟竖式加法中的进位传播。
末尾进位链
~~~~~~~~~~
加一从最低位开始。当前位只有两种情况:
* 数位小于 9:该位增加 1,不再产生进位;
* 数位等于 9:该位变为 0,并把进位继续传向左侧。
所以真正可能变化的部分只是数组末尾连续的 9,以及它左侧第一个非 9 数位。例如:
.. code-block:: text
[4,8,9,9]
^^^^^
末尾两个 9 变成 0,数位 8 增加为 9,更高位 4 保持不变。
扫描不变量
~~~~~~~~~~
从右向左扫描到下标 ``index`` 时,右侧已经处理过的数位全部属于原数组末尾连续的 9,并已被正确改写为 0;
当前仍有一个值为 1 的进位等待处理。
若当前数位小于 9,它可以吸收这个进位。该位加一后不会再产生新进位,因此左侧更高位无需改变,算法可以立即
返回。
若当前数位等于 9,它加一后应变为 0,进位继续存在,不变量在下一轮仍成立。
全 9 情况
~~~~~~~~~
若扫描越过最高位仍未返回,说明原数组的每一位都是 9:
.. code-block:: text
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)`` 时间。