2026-09-14
#66 数学模拟 简单

加一

在 LeetCode 上查看 ↗

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

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

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

示例 1

输入：digits = [1,2,3]
输出：[1,2,4]

解释：123 + 1 = 124。

示例 2

输入：digits = [4,3,2,1]
输出：[4,3,2,2]

解释：4321 + 1 = 4322。

示例 3

输入：digits = [9]
输出：[1,0]

解释：9 + 1 = 10，位数变长，首位为 1。

💭 模拟答题者思考

1. 最直接：把数组拼成字符串或整数，加 1 再拆回数组——但长度可达 100，Python 大整数虽可行，C++ 会溢出，且没体现「按位进位」的模拟过程。

2. 重复在哪里？人类做竖式加法也是从最低位开始，只有当前位是 9 且还要进位时才继续向左；一旦某位加完不进位，左边所有位都不变。

3. 设 carry=1，从 i=n-1 往左：sum = digits[i] + carry，digits[i] = sum % 10，carry = sum // 10；若 carry==0 直接返回 digits。

4. 若扫完全部位仍有 carry==1（如 [9,9,9]+1），位数加一，结果是 [1,0,0,0]，不能只在原数组上改——需要多一位。

5. 平均情况只需改尾部少数位（如 [1,2,3] 只改最后一位），最坏 O(n) 当全是 9。

🧠 变量语义（先读这三句再编码）

变量类型语义（三句法）
carryint定义：当前位加完后需要向高位传递的进位，本题初始为 1（表示「加一」）
维护：某位处理完后，若该位和为 10 则 carry=1 否则 carry=0
更新：从最低位向高位扫描，每处理一位用新 carry 进入下一位；carry==0 时可提前结束
iint定义：当前处理的数位下标，从 len(digits)-1 向 0 递减
维护：只访问尚未确定最终值的尾部数字
更新：每轮 i -= 1，直到进位消尽或遍历完最高位
digits[i]int定义：大整数从高位到低位存储的每一位（0–9）
维护：在 carry>0 的区间内原地改写为 (digits[i]+carry) % 10
更新：若循环结束仍有 carry==1（全 9 进位），需新建长度为 n+1 的数组，首元素为 1

⌨️ 落码步骤

1. n = len(digits)，carry = 1

2. for i 从 n-1 downto 0：carry += digits[i]（或 sum = digits[i]+carry），digits[i] = carry % 10，carry //= 10

3. 若 carry == 0，返回当前 digits（左侧未动，已正确）

4. 循环结束仍 carry == 1：返回 [1] + [0]*n（或 C++ 中 vector 前插 1）

💻 代码实现 

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        carry = 1  # 表示要加的这一「1」
        for i in range(len(digits) - 1, -1, -1):
            carry += digits[i]
            digits[i] = carry % 10
            carry //= 10
            if carry == 0:
                return digits
        # 全是 9：999... + 1 → 1000...
        return [1] + [0] * len(digits)
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int carry = 1;
        for (int i = (int)digits.size() - 1; i >= 0; --i) {
            carry += digits[i];
            digits[i] = carry % 10;
            carry /= 10;
            if (carry == 0) return digits;
        }
        // 全是 9，最高位多一位
        vector<int> ans(digits.size() + 1, 0);
        ans[0] = 1;
        return ans;
    }
};
// 时间 O(n)，空间 O(1) 原地 / O(n) 全 9

📈 复杂度分析

时间复杂度 O(n)
空间复杂度 O(1)（原地修改）/ O(n)（全 9 需新数组）

⚠️ 常见坑

❗ 忘记全 9 进位：[9] → [1,0]、[9,9] → [1,0,0]，原数组长度不够，必须新建或前插 1。

❗ 从高位往低位加会漏进位传播；必须从最低位（数组末尾）开始。

❗ carry==0 后仍继续改左边数字会破坏正确结果（如 [1,2,3] 改完末位后应立刻返回）。

🔍 必测边界 Case

Case 1：无进位传播
[1,2,3] → [1,2,4]（仅末位变化，循环一次后 carry=0）
Case 2：连续进位
[1,9,9] → [2,0,0]（末两位变 0，最高位加 1）
Case 3：单元素进位变长
[9] → [1,0]（示例 3）
Case 4：全 9
[9,9,9,9] → [1,0,0,0,0]（长度 +1）
Case 5：单元素无进位
[8] → [9]（一位数加一）