LeetCode 66. 加一

约 8 分钟
文章信息 10 个分类 4 个标签
分类
LeetCode CodeTop 简单 未解决 需复习 2-5 字节跳动 阿里巴巴 虾皮 面试经典 150 题
标签
数组 数学 数学经典题 加法问题
目录

题目描述

✅ 66. 加一

image-20230312173014312

题意分析

给一个数组 digits，它按从高位到低位的顺序逐位存放一个非负整数（digits[0] 是最高位），要求返回这个整数加 1 之后的结果，同样按逐位数组的形式返回。

题目为什么不直接让你把数组转成整数再加 1？因为数组长度可以到 100，对应的数远超 long 的表示范围。这个约束是整道题最重要的信号：必须在数字的十进制表示上直接操作，不能借助任何原生整数类型，也就是要手写竖式加法。

加数固定是 1，这是本题相对一般大数加法的最大简化。它意味着只有最低位真正参与加法，其余位只可能受到「进位」的影响；而进位只有 0 和 1 两种取值，一旦某一位加完不产生进位，前面所有位就都不会再变。

题目还保证输入不含前导零（除非这个数本身就是 0），返回值也应该满足这个性质。

边界主要有三类：最低位不是 9（完全不进位）；末尾有一串连续的 9（进位传播若干位后停下）；全部是 9（进位一直传到最高位之外，结果比原数多一位）。第三类是本题唯一需要改变数组长度的情况。

解法：从低位模拟进位

核心思路

最朴素的想法是把数组还原成整数、加 1、再拆回数组。它在 digits.length 小的时候能过，但长度一到 20 就溢出了，题目给到 100，这条路直接堵死。瓶颈很明确：不能把整个数当成一个值来算，只能逐位算。

于是退回到竖式加法：从最低位开始，把当前位加上进位，取模写回、取商作为新进位，向高位推进。加数为 1 时，这个过程可以进一步简化——初始进位为 1，之后每一位的运算只有两种结果。

关键观察是：设当前位为 d，待加的进位为 1。若 d < 9，则 d + 1 ≤ 9，写回 d + 1，新进位为 0，加法到此结束，更高位一个都不用碰；若 d == 9，则 9 + 1 = 10，写回 0，新进位仍是 1，必须继续向高位传播。也就是说进位不会「变大也不会中途凭空出现」，它要么在某一位被吸收，要么原样传递。

这里的循环不变量是：每次进入循环体时，进位恒为 1，且下标 i 右侧的所有位都已经被置为 0。第一条让代码里完全不需要一个 carry 变量——它的值是常量；第二条解释了为什么循环自然退出（i < 0）时，整个数组已经是全 0，我们只需要在前面补一个 1。

循环正常走完意味着进位穿透了最高位，说明原数是 99...9，结果是 10...0，长度恰好多 1。此时新开一个长度为 n + 1 的数组，它在 Java 和 Go 里默认全零，只要把首位设成 1 就是答案，连拷贝都省了。

解题步骤

  • 从 i = digits.length - 1 开始向前遍历：数组是高位在前，所以最低位在数组末尾，加法必须从这一端开始。方向写反会变成给最高位加 1。
  • 判断 digits[i] < 9：这是「本位能吸收进位」的充要条件。用 < 9 而不是 != 9，语义上更贴近「加 1 后不会溢出本位」，迁移到其他进制时只要改这个上界。
  • 能吸收就 digits[i]++ 并立刻 return digits：立刻返回是这段代码的核心优化，也是正确性的一部分——更高位没有任何变化，继续遍历只会做无用功。返回原数组而不是新数组，是因为题目允许原地修改，也让常见情形下不产生额外分配。
  • 不能吸收就 digits[i] = 0，让循环继续：9 + 1 的本位结果就是 0，进位保持 1 交给下一轮。这里不需要写 carry = 1，因为不变量已经保证了进位恒为 1。
  • 循环正常结束说明全是 9：只有每一位都走了 digits[i] = 0 分支，循环才会跑到 i < 0。此时数组已被清成全 0。
  • 新建长度 n + 1 的数组，首位置 1 后返回：新数组其余位默认为 0，恰好就是 10...0 的形态，不需要把清零后的原数组拷过来。这一步也解释了为什么前面可以放心地把原数组改成全 0——那些 0 本来就是答案的一部分形状。

以 digits = [1, 2, 9] 走一遍（期望 [1, 3, 0]）。

i = 2：digits[2] = 9，不满足 < 9，置 0，数组变为 [1, 2, 0]，进位继续。

i = 1：digits[1] = 2 < 9，自增为 3，数组变为 [1, 3, 0]，立即返回。下标 0 的那个 1 根本没被访问过——这就是「遇到第一个非 9 就停」省下的工作。

再以 digits = [9, 9] 走一遍（期望 [1, 0, 0]）。

i = 1：是 9，置 0，数组变为 [9, 0]。

i = 0：是 9，置 0，数组变为 [0, 0]。

i 变成 -1，循环退出。此时不变量的第二条告诉我们数组已全 0。新建长度 3 的数组 [0, 0, 0]，首位设 1 得 [1, 0, 0]，返回。若这里错误地把清零后的原数组当成答案返回，就会得到 [0, 0]，即数字 0。

代码实现

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)$，其中 n 是位数。凭什么：最坏情况是全 9，进位要穿过每一位，循环跑满 n 轮，每轮做常数次比较赋值；平均情况下最低位是 9 的概率只有十分之一，通常一两轮就返回了。
  • 空间复杂度：$O(1)$（不计返回值）。凭什么：主流程在原数组上原地改写，没有任何辅助容器；只有全 9 这一种情况才分配长度 n + 1 的结果数组，而那是必须返回的输出本身，不算额外开销。

关键点总结

  • 位数超出原生整数范围时，唯一出路是在十进制表示上手写竖式；看到「数组存数字」「长度上百」就该立刻放弃「转成 long 再算」的念头，这是大数题的统一入口。
  • 加数是常数 1 时，进位恒为 1、只有 0 / 1 两种状态，可以把 carry 变量整个消掉——识别出「变量其实是常量」是化简模拟题的常用手段。
  • 「遇到第一个可吸收进位的位就立刻返回」既是剪枝也是正确性的一部分，它保证了更高位不会被误改。
  • 全 9 是唯一改变长度的情形，且结果一定是 1 后跟 n 个 0，利用数组默认零值可以零拷贝构造，这个小技巧在 43、415 等题里同样适用。
  • 面试时值得主动说明的是「为什么不能先转成整数」和「为什么只有全 9 需要扩容」，这两句话能证明你分析过边界而不是背模板。

易错点总结

  • 先把数组拼成 int / long 再加 1：digits 为 100 个 9 时数值远超 long 上界，结果溢出成负数或截断，返回完全错误的数组。
  • 循环方向写成从 0 递增：[1, 2, 3] 会变成 [2, 2, 3]，即给最高位加了 1，答案是 223 而不是 124。
  • 全 9 时返回被清零的原数组：[9, 9] 返回 [0, 0]，缺了最高位的 1。
  • 全 9 时新建数组后又把原数组内容拷贝进去：[9] 会得到 [1, 0] 之外还多拷一位，或错位成 [1, 9]，取决于拷贝的起止下标。
  • 判断条件写成 digits[i] != 9 但忘了本位自增：[1, 2, 3] 里 digits[2] 被判定为可吸收却没执行 ++，直接返回 [1, 2, 3]，等于没加。
  • 在非 9 分支自增后没有 return，继续循环：[8, 9] 里 digits[1] 置 0、digits[0] 自增为 9 后若不返回，下一轮 i = -1 退出循环，反而落进扩容分支返回 [1, 0, 0]，把 90 算成了 100。
  • 扩容数组长度写成 digits.length：[9, 9] 得到长度 2 的数组，首位设 1 后返回 [1, 0]，即 10 而不是 100。
  • 多开一位后把 1 写在末尾：[9] 返回 [0, 1]，既有前导零又是错误数值。
  • 用 digits[i] = (digits[i] + 1) % 10 配合 carry 变量却忘了在 carry == 0 时跳出：[1, 2, 3] 虽然结果对，但会把整个数组扫完；若同时漏写 carry 的初始化，[9, 9, 9] 会返回全 0 数组。

相似题目

题目 难度 考察点
989. 数组形式的整数加法 简单 加数不再是 1 而是任意整数，进位可能大于 1，carry 变量无法省掉
415. 字符串相加 简单 两个等待相加的数长度不同，需要用双指针分别推进并处理其中一方先耗尽
67. 二进制求和 简单 进制换成 2，本位上界从 9 变成 1，模板其余部分完全照搬
43. 字符串相乘 中等 乘法要按下标 i + j + 1 累加到中间数组，最后统一处理进位与前导零
2. 两数相加 中等 数字存在链表里且低位在前，天然从低位开始，不需要反向遍历
445. 两数相加 II 中等 链表高位在前，必须借助栈或反转链表才能从低位开始加
369. 给单链表加一 中等 与本题同构但载体是链表，找不到前驱，通常用哨兵节点记录最后一个非 9 的位置
1073. 负二进制数相加 中等 基数为 -2，进位可能是 -1，本位取值规则完全改变
LCR 002. 二进制求和 简单 与 67 同题，可直接套用二进制版模板