加一 - LonelyStar

题目链接：66. 加一 - 力扣（LeetCode）

难度：简单
标签：数组、数学

题目描述#

Note

原题说明：给定一个表示 大整数 的整数数组 digits，其中 digits[i] 是整数的第 i 位数字。这些数字按从左到右、从最高位到最低位排列。这个大整数不包含任何前导 0。

将该大整数加一，并返回结果的数字数组。

示例#

输入: digits = [1,2,3] -> 输出: [1,2,4]
输入: digits = [9,9,9] -> 输出: [1,0,0,0]

方案一：逆序遍历与进位处理#

核心思路：数字加一的操作从最低位（数组末尾）开始。

如果某一位不为 9，加一后直接返回数组。
如果某位为 9，该位变为 0，继续检查前一位。
若所有位都是 9（如 999），则最终需要在数组头部插入一个 1。

源码实现#

1
class Solution {
2
public:
3
    vector<int> plusOne(vector<int>& digits) {
4
        int n = digits.size();
5

6
        // 从后往前遍历
7
        for (int i = n - 1; i >= 0; i--) {
8
            if (digits[i] != 9) {
9
                // 当前位不是 9，直接加 1 后返回
10
                digits[i] += 1;
11
                // 将后面的所有位设为 0（虽然在此逻辑中，后面的位本就已在之前的循环中变为了 0）
12
                for (int j = i + 1; j < n; j++) {
13
                    digits[j] = 0;
14
                }
15
                return digits;
16
            }
17
            // 当前位是 9，变为 0，继续循环处理进位
18
            digits[i] = 0;
19
        }
20

21
        // 如果程序运行到这里，说明所有位数都是 9（如 [9, 9, 9]）
22
        // 此时需要构造一个 [1, 0, 0, 0] 的数组
23
        vector<int> result(n + 1, 0);
24
        result[0] = 1;
25
        return result;
26
    }
27
};

复杂度分析#

时间复杂度： $O(n)$ 。其中 $n$ 是数字的位数。最坏情况下（全是 9）需要遍历整个数组。
空间复杂度： $O(1)$ $O (1)$ 或 $O(n)$ $O (n)$ 。
- 常规情况：原地修改，空间复杂度为 $O(1)$ 。
- 全 9 情况：需要创建一个长度为 $n+1$ 的新数组，空间复杂度为 $O(n)$ 。

总结#

进位意识：这道题本质上是模拟手动加法的个位进位过程。
原地修改优化：通过从后向前找到第一个非 9 数字，可以极大地减少不必要的数组重排。
边界处理：全 9 序列是这道题唯一的“陷阱”，需要通过扩容数组或返回新数组来解决。

Tip

这种“数组模拟大整数运算”的思路，是以后处理更高级算法（如大数乘法、阶乘计算）的基础。

音乐

音乐