989. Add to Array-Form of Integer

Easy

Description

給定一個非負整數的陣列表示形式 num（每個元素是 0-9 的數字），和一個整數 k，回傳 num + k 的陣列表示形式。

Example:

Input: num = [1,2,0,0], k = 34 Output: [1,2,3,4]

Intuition#

核心思路：從最低位開始逐位相加，處理進位——本質上就是大數加法。

從陣列末尾開始，加上 k 的最低位和進位
k 本身可以當作進位值：每次取 k % 10 作為當前位加數，k / 10 作為下一位
當陣列和 k 都處理完後，結果需要反轉

Approaches#

1: 逐位相加（k 當進位）#

概念: 從右到左遍歷，把 k 直接當作加數逐位消耗
時間複雜度: O(max(n, log k)) - n 為陣列長度
空間複雜度: O(max(n, log k)) - 結果可能多一位

class Solution {
    fun addToArrayForm(num: IntArray, k: Int): List<Int> {
        val result = mutableListOf<Int>()
        var carry = k
        var i = num.size - 1

        while (i >= 0 || carry > 0) {
            if (i >= 0) {
                carry += num[i]
                i--
            }
            result.add(carry % 10)
            carry /= 10
        }

        result.reverse()
        return result
    }
}

⭐2: 更直覺的進位分離#

概念: 明確分離 carry 和 k 的邏輯，逐位計算
時間複雜度: O(max(n, log k))
空間複雜度: O(max(n, log k))

class Solution {
    fun addToArrayForm(num: IntArray, k: Int): List<Int> {
        val result = LinkedList<Int>()
        var carry = 0
        var remaining = k
        var i = num.size - 1

        while (i >= 0 || remaining > 0 || carry > 0) {
            var sum = carry
            if (i >= 0) {
                sum += num[i]
                i--
            }
            if (remaining > 0) {
                sum += remaining % 10
                remaining /= 10
            }
            result.addFirst(sum % 10)
            carry = sum / 10
        }

        return result
    }
}

🔑 Takeaways#

Pattern: 大數加法——從低位到高位逐位相加並處理進位
關鍵技巧: 把 k 直接當作 carry 的初始值可以簡化程式碼，不需要分別處理 k 的每一位