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)`` 时间。