LeetCode 加一：逆向遍歷模擬進位原地修改

題目描述

給定非負整數數組（最高位在前），在該數字上加一，返回結果數組。

範例：

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

解題思路：從低位到高位處理進位

1. 初始化 carry = 1（加一）
2. 逆向遍歷：digits[i] += carry
3. 若 < 10：carry = 0，提前結束
4. 否則：digits[i] -= 10，繼續向高位傳遞進位
5. 遍歷結束若 carry == 1：頭部插入 1

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

Python 參考實現

class Solution:
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        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 == 1:
            digits.insert(0, 1)
        return digits

# 測試
if __name__ == "__main__":
    sol = Solution()
    assert sol.plusOne([1, 2, 3, 4, 9]) == [1, 2, 3, 5, 0]
    assert sol.plusOne([9]) == [1, 0]
    assert sol.plusOne([9, 9, 9]) == [1, 0, 0, 0]
    print("所有測試通過")

核心要點總結

• 逆向遍歷：符合人類手工加法邏輯（個位→十位→百位）
• 進位標記：carry 控制是否繼續向高位傳遞
• 提前結束：無進位時 break 避免無效循環
• 邊界情況：全 9 導致位數增加，insert(0, 1) 處理

這道題是大數加法的最簡形式，掌握「逆向 + 進位標記 + 提前退出」模式，可擴展至任意大數加減乘除實現。