LeetCode 66：加一——數組表示大整數加一的進位處理

題目描述

非負整數以數組形式存儲（最高位在前），對其加 1，返回新數組。

算法思路

從最低位（數組末尾）向高位遍歷，維護進位 carry：

1. digit = digits[i] + carry
2. digits[i] = digit % 10
3. carry = digit / 10
4. 若 carry == 0 提前結束。

遍歷結束若 carry > 0，在數組頭部插入 carry。

C++ 實現

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int carry = 1;
        for (int i = digits.size() - 1; i >= 0 && carry; --i) {
            int sum = digits[i] + carry;
            digits[i] = sum % 10;
            carry = sum / 10;
        }
        if (carry) digits.insert(digits.begin(), carry);
        return digits;
    }
};

關鍵點

• 原地修改，空間 O(1)（不計輸出）。
• 提前跳出優化：一旦無進位即可停止。
• 擴展：加任意整數 k 同理，將 k 分解為各位逐位相加。

複雜度

• 時間：O(n)，最壞全 9 需遍歷整個數組。
• 空間：O(1) 額外空間。