Yoru Karu Studio
Yoru Karu Studio

LeetCode 解題思路：66. Plus One（加一）

陣列模擬加法運算與進位處理技巧

luk 收錄於 Leetcode
 約 1400 字 預計閱讀 7 分鐘 

題目描述

給定一個由整數陣列表示的大整數 digits，其中每個 digits[i] 是該整數的第 i 位數字。數字按照從左到右的順序排列，從最高位到最低位。該大整數不包含任何前導零。

將該大整數加一，並返回結果的數字陣列。

範例

範例 1：

輸入：digits = [1,2,3]
輸出：[1,2,4]
解釋：該陣列表示整數 123。
     123 + 1 = 124

範例 2：

輸入：digits = [4,3,2,1]
輸出：[4,3,2,2]
解釋：該陣列表示整數 4321。
     4321 + 1 = 4322

範例 3：

輸入：digits = [9]
輸出：[1,0]
解釋：該陣列表示整數 9。
     9 + 1 = 10

範例 4：

輸入：digits = [9,9,9]
輸出：[1,0,0,0]
解釋：999 + 1 = 1000

限制條件

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9
  • digits 不包含任何前導零

核心概念理解

1. 問題本質

這題模擬的是我們手算加法的過程：

  • 從最低位（最右邊）開始加 1
  • 處理進位（carry）
  • 如果一直進位到最高位，需要擴展陣列

2. 進位的觸發條件 

當某一位 = 9 時，加 1 會產生進位：
9 + 1 = 10 → 該位變成 0，進位 1

例如：
[1, 2, 9] + 1 = [1, 3, 0]
[9, 9, 9] + 1 = [1, 0, 0, 0]

3. 特殊情況分析 

情況 1：末位不是 9
[1, 2, 3] + 1 = [1, 2, 4]  # 直接加 1，無進位

情況 2：末尾有連續的 9
[1, 2, 9, 9] + 1 = [1, 3, 0, 0]  # 連續進位

情況 3：全部都是 9
[9, 9, 9] + 1 = [1, 0, 0, 0]  # 需要擴展陣列

解法一：從後往前遍歷（推薦）

思路

模擬手算加法的過程，從最低位開始處理進位。

程式碼實現 

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)
        
        # 從最低位（最右邊）開始
        for i in range(n - 1, -1, -1):
            # 當前位加 1
            digits[i] += 1
            
            # 如果小於 10，沒有進位，直接返回
            if digits[i] < 10:
                return digits
            
            # 有進位，當前位設為 0，繼續處理下一位
            digits[i] = 0
        
        # 如果循環結束還沒返回，說明最高位也有進位
        # 例如 [9,9,9] 變成 [0,0,0]，需要在前面加 1
        return [1] + digits

執行過程視覺化 

範例 1：digits = [1,2,3]
[1, 2, 3]
      ↑
    加1=4 (< 10，無進位)
結果：[1, 2, 4]

範例 2：digits = [1,2,9]
[1, 2, 9]
      ↑
    加1=10 (進位)
[1, 2, 0]
   ↑
  加1=3 (< 10，停止)
結果：[1, 3, 0]

範例 3：digits = [9,9,9]
[9, 9, 9]
      ↑
    加1=10 (進位)
[9, 9, 0]
   ↑
  加1=10 (進位)
[9, 0, 0]
 ↑
加1=10 (進位)
[0, 0, 0]
需要在前面加 1
結果：[1, 0, 0, 0]

複雜度分析

  • 時間複雜度：O(n)，最壞情況需要遍歷所有位數
  • 空間複雜度：O(1)，如果不考慮返回值；O(n) 如果考慮可能需要擴展陣列

解法二：使用進位變數

思路

使用一個 carry 變數來追蹤進位狀態。

程式碼實現 

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        carry = 1  # 初始要加的值
        n = len(digits)
        
        # 從後往前處理
        for i in range(n - 1, -1, -1):
            total = digits[i] + carry
            digits[i] = total % 10
            carry = total // 10
            
            # 如果沒有進位了，可以提前結束
            if carry == 0:
                return digits
        
        # 如果還有進位，說明需要在前面加 1
        if carry:
            return [carry] + digits
        
        return digits

變數追蹤 

digits = [9, 9, 9], carry = 1

i = 2: total = 9 + 1 = 10
       digits[2] = 0, carry = 1

i = 1: total = 9 + 1 = 10
       digits[1] = 0, carry = 1

i = 0: total = 9 + 1 = 10
       digits[0] = 0, carry = 1

carry = 1，需要在前面加 1
結果：[1, 0, 0, 0]

解法三：優化版（提前終止）

思路

觀察發現：只有當某位是 9 時才會產生進位，否則加 1 後就可以直接返回。

程式碼實現 

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)
        
        # 從後往前找第一個不是 9 的位置
        for i in range(n - 1, -1, -1):
            if digits[i] != 9:
                digits[i] += 1
                return digits
            # 是 9，設為 0，繼續往前
            digits[i] = 0
        
        # 所有位都是 9
        return [1] + [0] * n

優化說明 

# 更簡潔的寫法
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range(len(digits) - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1
                return digits
            digits[i] = 0
        
        return [1] + digits

解法四：遞迴解法

思路

將問題分解為子問題：如果當前位產生進位，就對前面的部分執行加一操作。

程式碼實現 

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        def addOne(digits, index):
            # 基礎情況：已經處理到最前面
            if index < 0:
                return [1] + digits
            
            # 當前位加 1
            digits[index] += 1
            
            # 如果產生進位
            if digits[index] == 10:
                digits[index] = 0
                return addOne(digits, index - 1)
            
            return digits
        
        return addOne(digits, len(digits) - 1)

解法五：數學轉換（不推薦用於大數）

思路

將陣列轉換成整數，加一後再轉回陣列。

程式碼實現 

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        # 轉換為整數
        num = 0
        for digit in digits:
            num = num * 10 + digit
        
        # 加一
        num += 1
        
        # 轉回陣列
        return [int(d) for d in str(num)]

為什麼不推薦？ 

# 問題：整數溢出
# 題目說 digits.length 可達 100
# 這表示數字可能有 100 位！
# 大多數程式語言的整數類型無法處理這麼大的數

# Python 可以處理任意大的整數，但：
# 1. 效率較低
# 2. 失去了練習陣列操作的意義
# 3. 面試時可能被要求不使用這種方法

常見錯誤與陷阱

錯誤 1：忘記處理全 9 的情況 

# ❌ 錯誤：沒有考慮需要擴展陣列
def plusOne(self, digits: List[int]) -> List[int]:
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0
    # 忘記處理 [9,9,9] → [1,0,0,0]

錯誤 2：修改了原陣列但沒有正確返回 

# ❌ 錯誤：創建新陣列但邏輯錯誤
def plusOne(self, digits: List[int]) -> List[int]:
    result = digits[:]  # 複製陣列
    carry = 1
    
    for i in range(len(result) - 1, -1, -1):
        result[i] += carry
        if result[i] < 10:
            break
        result[i] = 0
    
    # 忘記處理最高位進位
    return result

錯誤 3：邊界索引錯誤 

# ❌ 錯誤：索引計算錯誤
def plusOne(self, digits: List[int]) -> List[int]:
    n = len(digits)
    for i in range(n, 0, -1):  # 應該是 range(n-1, -1, -1)
        digits[i] += 1  # IndexError!

變體問題

1. Plus K（加任意數字） 

def plusK(digits: List[int], k: int) -> List[int]:
    carry = k
    n = len(digits)
    result = []
    
    # 從後往前處理
    for i in range(n - 1, -1, -1):
        total = digits[i] + carry
        result.append(total % 10)
        carry = total // 10
    
    # 處理剩餘的進位
    while carry:
        result.append(carry % 10)
        carry //= 10
    
    # 反轉結果
    return result[::-1]

# 測試
print(plusK([9, 9, 9], 25))  # [1, 0, 2, 4]

2. 減一操作 

def minusOne(digits: List[int]) -> List[int]:
    n = len(digits)
    
    for i in range(n - 1, -1, -1):
        if digits[i] > 0:
            digits[i] -= 1
            # 移除前導零
            if digits[0] == 0 and n > 1:
                return digits[1:]
            return digits
        # 需要借位
        digits[i] = 9
    
    # 不應該到這裡（假設輸入 > 0）
    return digits

3. 二進制加一 

def addBinary(binary: List[int]) -> List[int]:
    """二進制陣列加一"""
    n = len(binary)
    
    for i in range(n - 1, -1, -1):
        if binary[i] == 0:
            binary[i] = 1
            return binary
        binary[i] = 0
    
    return [1] + binary

# 測試
print(addBinary([1, 0, 1]))  # [1, 1, 0]
print(addBinary([1, 1, 1]))  # [1, 0, 0, 0]

4. 加法器（兩個陣列相加） 

def addTwoNumbers(num1: List[int], num2: List[int]) -> List[int]:
    # 確保 num1 是較長的
    if len(num1) < len(num2):
        num1, num2 = num2, num1
    
    n1, n2 = len(num1), len(num2)
    carry = 0
    result = []
    
    # 從後往前處理
    for i in range(n1):
        # 計算對應位置的和
        j = n2 - (n1 - i)
        digit2 = num2[j] if j >= 0 else 0
        
        total = num1[i] + digit2 + carry
        result.append(total % 10)
        carry = total // 10
    
    if carry:
        result.append(carry)
    
    return result[::-1]

效能優化

1. 原地修改 vs 創建新陣列 

# 原地修改（空間 O(1)）
def plusOne_inplace(digits: List[int]) -> List[int]:
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0
    return [1] + digits

# 創建新陣列（空間 O(n)）
def plusOne_new_array(digits: List[int]) -> List[int]:
    result = digits[:]
    # ... 處理邏輯
    return result

2. 提前終止的重要性 

import time

def benchmark_solutions():
    # 最壞情況：全是 9
    worst_case = [9] * 100
    
    # 最好情況：末位不是 9
    best_case = [9] * 99 + [8]
    
    # 測試提前終止的效果
    iterations = 100000
    
    # 最壞情況
    start = time.time()
    for _ in range(iterations):
        plusOne(worst_case[:])
    print(f"最壞情況: {time.time() - start:.4f}s")
    
    # 最好情況
    start = time.time()
    for _ in range(iterations):
        plusOne(best_case[:])
    print(f"最好情況: {time.time() - start:.4f}s")

進階思考

1. 處理負數 

def increment(digits: List[int], sign: int = 1) -> Tuple[List[int], int]:
    """
    處理帶符號的數字
    返回 (digits, sign)
    """
    if sign == 1:
        # 正數，正常加一
        return plusOne(digits), 1
    else:
        # 負數，實際上是減少絕對值
        return minusOne(digits), -1

2. 任意進制 

def plusOne_base(digits: List[int], base: int) -> List[int]:
    """任意進制的加一操作"""
    n = len(digits)
    
    for i in range(n - 1, -1, -1):
        digits[i] += 1
        if digits[i] < base:
            return digits
        digits[i] = 0
    
    return [1] + digits

# 八進制例子
print(plusOne_base([7, 7, 7], 8))  # [1, 0, 0, 0]

3. 大數運算庫的實現思路 

class BigInteger:
    def __init__(self, digits):
        self.digits = digits
        self.base = 10
    
    def add(self, other):
        """加法運算"""
        # 實現細節...
        pass
    
    def multiply(self, other):
        """乘法運算"""
        # 實現細節...
        pass

測試案例 

def test_plusOne():
    test_cases = [
        # (input, expected)
        ([1, 2, 3], [1, 2, 4]),
        ([4, 3, 2, 1], [4, 3, 2, 2]),
        ([9], [1, 0]),
        ([9, 9, 9], [1, 0, 0, 0]),
        ([0], [1]),
        ([1, 9, 9], [2, 0, 0]),
        ([8, 9, 9, 9], [9, 0, 0, 0]),
        ([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], [9, 8, 7, 6, 5, 4, 3, 2, 1, 1]),
    ]
    
    solution = Solution()
    for digits, expected in test_cases:
        result = solution.plusOne(digits[:])  # 複製以避免修改原陣列
        assert result == expected, f"Failed: {digits}"
        print(f"✅ 通過：{digits} + 1 = {result}")

相關題目

  1. LeetCode 67: Add Binary（二進制加法）
  2. LeetCode 369: Plus One Linked List（鏈表加一）
  3. LeetCode 989: Add to Array-Form of Integer（陣列形式的整數加法）
  4. LeetCode 2: Add Two Numbers（兩數相加）
  5. LeetCode 445: Add Two Numbers II（兩數相加 II）

面試技巧

1. 問題澄清 

面試官："實現陣列表示的整數加一。"

你應該問：
1. "陣列是否可能為空？"
2. "是否需要處理負數？"
3. "數字的範圍有多大？會不會超過語言的整數限制？"
4. "可以修改原陣列嗎？"
5. "有前導零嗎？"

2. 解題思路展示 

"""
思路分析：
1. 這是一個進位問題，類似手算加法
2. 從最低位開始處理
3. 關鍵是處理連續的 9
4. 特殊情況：全是 9 時需要擴展陣列

時間複雜度：O(n)
空間複雜度：O(1) 或 O(n)（如果需要擴展）
"""

3. 優化討論

  • 提前終止的重要性
  • 空間複雜度的權衡
  • 是否需要支援更通用的加法

總結

這道題雖然標記為 Easy，但包含了幾個重要概念：

  1. 進位處理：理解數學運算的本質
  2. 邊界情況：特別是全 9 的情況
  3. 陣列操作：從後往前遍歷的技巧
  4. 優化思維：提前終止可以提升效能

核心要點：

  • 從低位到高位處理
  • 遇到不是 9 的位就可以停止
  • 記得處理最高位進位的特殊情況

這道題是理解大數運算的基礎，掌握後可以擴展到更複雜的運算！

更新於 2024-12-27 
CC BY-NC-SA 4.0
閱讀原始文檔
LeetcodeAlgorithmArrayMath
返回 | 主頁
0%