LeetCode 解題練習：Plus One

題目原文描述 https://leetcode.com/problems/plus-one/

中文描述

給定一個用陣列 digits 表示大整數 large integer，digits[i] 代表大整數的第 i 位數之值。例如 12345 會以 digits = [1, 2, 3, 4, 5] 來表示。請將 digits 的數值加一。

範例一：

輸入 digits = [9,9,9,9] 

輸出  [1, 0, 0, 0, 0]

說明：整數 9999  加一後為 10000。

範例二：

輸入 digits = [2, 2, 3, 4, 5] 

輸出  [2, 2, 3, 4, 6]

說明：整數 22345  加一後為 22346。

解法：

這是一題非常經典的 LeetCode 基礎題（Plus One）。這題的核心考點在於「如何處理進位（Carry）」，特別是當連續出現數字 9，或是整個陣列都是 9 的極端情況（Corner Case）。

以下為您將這個演算法的邏輯、步驟與程式碼做更深入、詳細的拆解與說明：

💡 核心解題邏輯

我們從小學數學的直式加法可以知道，加 1 都是從最右邊的個位數開始加。這時候會遇到三種情況：

1. 普通情況（無進位）：最右邊的數不是 9（例如：[1, 2, 3]）。我們直接把個位數加 1 變成 [1, 2, 4]，任務就結束了。

2. 部分進位：結尾有連續的 9（例如：[1, 2, 9]）。個位數的 9 加 1 變成 10，必須進位。所以個位數變成 0，再往前看十位數的 2，它不是 9，所以加 1 變成 3。結果為 [1, 3, 0]，任務結束。

3. 全數進位（極端情況）：所有數字都是 9（例如：[9, 9, 9]）。每個位置都會因為進位變成 0，最後陣列會變成 [0, 0, 0]。這時候我們必須在最左邊手動補一個 1，讓它變成 [1, 0, 0, 0]。

注意：若目前 digits[i] 為 9 ，將 digits[i] 設定為 0；否則 digits[i] 加一並回傳 digits。若每位數都是9，在最左邊補1。

🛠️ Python 程式碼

1. class Solution:
2. def plusOne(self, digits: List[int]) -> List[int]:
3. # 1. 從最後一個元素（個位數）開始，倒序往前檢查
4. # len(digits) - 1 是最後一個索引，-1 是結束邊界（不包含），-1 是每次往前走一步
5. for i in range(len(digits) - 1, -1, -1):
7. # 情況 A：如果目前這一位數是 9
8. if digits[i] == 9:
9. digits[i] = 0 # 加 1 後變成 10，所以這一位寫 0，然後繼續 loop 往前看前一位數
11. # 情況 B：如果目前這一位數「不是」9
12. else:
13. digits[i] += 1 # 直接加 1
14. return digits # 既然沒有產生進位，代表前面的數字都不會被影響，直接回傳結果結束函式！
16. # 情況 C：如果迴圈全部跑完了都沒有 return，代表原本全部都是 9（例如 [9, 9, 9] 變成了 [0, 0, 0]）
17. # 這時候我們要在最前面拼接一個 [1]
18. return [1] + digits

🏃 實例模擬走一遍

為了讓您更清楚，我們拿最複雜的情況 C（全部都是 9） 來當例子。假設輸入是 digits = [9, 9]（代表 99）：

• 進入迴圈，第一次（i = 1，指向最後一個 9）：

  • 檢查 digits[1] == 9 成立。

  • 執行 digits[1] = 0。此時陣列變成 [9, 0]。

  • 繼續下一次迴圈。

• 第二次迴圈（i = 0，指向第一個 9）：

  • 檢查 digits[0] == 9 成立。

  • 執行 digits[0] = 0。此時陣列變成 [0, 0]。

  • 迴圈結束。

• 離開迴圈後：

  • 執行 return [1] + [0, 0]。

  • 最終輸出 [1, 0, 0]（代表 100），完全正確！

📈 複雜度分析 (Complexity Analysis)

• 時間複雜度：$O(N)$ 其中 $N$ 是陣列的長度。最壞的情況下（全都是 9），我們需要把整個陣列走過一遍，所以是線性時間。如果是普通情況（個位數不是 9），時間複雜度甚至只要 $O(1)$。

• 空間複雜度：$O(1)$ 或 $O(N)$ 我們直接在原本的 digits 陣列上做修改（In-place），沒有額外開闢新記憶體。只有在全部都是 9 的特殊情況下，因為回傳 [1] + digits 建立了新陣列，才會需要 $O(N)$ 的空間。

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.