66. Plus One

Easy

Description

給定一個由整數陣列表示的非負整數 digits，其中 digits[i] 是第 i 位數字，最高位在陣列開頭。將這個整數加一後回傳結果陣列。

Example:

Input: digits = [1,2,9] Output: [1,3,0]

Intuition#

核心思路：從最低位開始加一，如果產生進位就繼續向前傳遞，全部進位完則前方補 1。

大部分情況只需要把最後一位加 1 即可
需要處理進位的情況，例如 [1,2,9] -> [1,3,0]
特殊情況：所有位都是 9（如 [9,9,9] -> [1,0,0,0]），需要擴展陣列長度

Approaches#

1: 模擬進位（通用）#

概念: 從最低位開始，加上進位值，計算新的進位和當前位的值
時間複雜度: O(n) - n 為陣列長度
空間複雜度: O(1) - 原地修改（最壞情況 O(n) 需要新陣列）

class Solution {
    fun plusOne(digits: IntArray): IntArray {
        var carry = 1
        for (i in digits.lastIndex downTo 0) {
            val sum = digits[i] + carry
            digits[i] = sum % 10
            carry = sum / 10
            if (carry == 0) return digits
        }
        // 全部進位完還有剩餘進位，如 999 -> 1000
        val result = IntArray(digits.size + 1)
        result[0] = 1
        return result
    }
}

⭐2: 簡化版（針對加一優化）#

概念: 由於只加 1，進位只可能是 0 或 1。如果當前位不是 9，加完就可以直接回傳；是 9 則設為 0 繼續
時間複雜度: O(n) - 最壞全是 9
空間複雜度: O(1) - 原地修改（最壞 O(n)）

class Solution {
    fun plusOne(digits: IntArray): IntArray {
        for (i in digits.lastIndex downTo 0) {
            if (digits[i] < 9) {
                digits[i]++
                return digits
            }
            digits[i] = 0
        }
        // 走到這裡表示所有位都是 9
        val result = IntArray(digits.size + 1)
        result[0] = 1
        return result
    }
}

當所有位都是 9 時，新陣列只需要設 result[0] = 1，其餘位自動為 0（IntArray 預設值）。不需要額外複製。

🔑 Takeaways#

Pattern: 大數加法的簡化版，進位傳遞是核心邏輯
關鍵技巧: 針對「只加 1」的特殊性簡化邏輯——不是 9 就直接加、是 9 就變 0 繼續，比通用進位寫法更簡潔