LeetCode 66 加一：陣列表示整數的進位處理技巧

題目描述

給定一個非負整數，以數組形式存儲（最高位在前），請在該數字上加一，並以數組形式返回結果。

範例：

輸入: [1, 2, 3, 4, 9]
輸出: [1, 2, 3, 5, 0]

解題思路：從低位向高位模擬加法

最直觀的方法是將數組轉為整數加一再轉回，但會面臨大數溢出問題（題目暗示不允許）。正確做法是原地模擬手工加法：

1. 從數組末尾（個位）開始，加 1
2. 若當前位 ≥ 10，置為 val - 10，向前一位進 1
3. 繼續向前處理進位，直到無進位或到達最高位
4. 若最高位仍進位（如 999 + 1 = 1000），在數組頭部插入 1

時間複雜度：O(n)，空間複雜度：O(1)（不計輸出空間）。

C++ 參考實現

class Solution {
public:
    vector plusOne(vector& digits) {
        int n = digits.size();
        // 從最低位開始加 1
        digits[n - 1] += 1;
        
        // 處理進位
        for (int i = n - 1; i > 0; --i) {
            if (digits[i] >= 10) {
                digits[i] -= 10;
                digits[i - 1] += 1;
            }
        }
        
        // 處理最高位進位
        if (digits[0] >= 10) {
            vector result;
            result.push_back(digits[0] - 9); // 10 -> 1, 11 -> 2...
            digits[0] -= 10;
            for (int d : digits) result.push_back(d);
            return result;
        }
        return digits;
    }
};

Python 參考實現（更簡潔）

class Solution:
    def plusOne(self, digits):
        carry = 1
        for i in range(len(digits) - 1, -1, -1):
            digits[i] += carry
            if digits[i] < 10:
                carry = 0
                break
            digits[i] -= 10
        if carry:
            digits.insert(0, 1)
        return digits

核心要點總結

• 逆向遍歷：從個位開始，符合人類直覺的加法邏輯
• 進位標記：用 carry 變量控制是否繼續向高位傳遞
• 邊界情況：全 9 導致位數增加，需在頭部插入 1
• 原地修改：盡量在原數組上操作，僅在必要時擴容

這道題看似簡單，實則考察對進位邏輯的完整處理能力，是大數運算基礎訓練的經典入門題。