LeetCode 66：加一 - 數組模擬大整數加法

題目描述

給定非負整數的數組表示（最高位在前），對該整數加一，返回結果數組。

示例：[1,2,3] → [1,2,4]，[9,9] → [1,0,0]。

解題思路

從最低位（數組末尾）向前處理進位：

1. 初始進位 carry = 1（即加一）。
2. 逆序遍歷數組：sum = digits[i] + carry，digits[i] = sum % 10，carry = sum / 10。
3. 遍歷結束若 carry > 0，在數組頭部插入 carry。

代碼實現

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        int carry = 1;
        for (int i = n - 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;
    }
};

關鍵點

• 原地修改數組，避免額外空間。
• 提前終止：若無進位則直接跳出循環。
• 處理全 9 導致進位擴展的情況（如 999 → 1000）。

複雜度

• 時間：O(n)，最多遍歷一次。
• 空間：O(1)（不計輸出），或 O(n) 若需擴容。

總結

簡單的模擬題，核心是從低位向高位處理進位，注意邊界條件與擴容。