給定一個非負整數的陣列表示形式
num（每個元素是 0-9 的數字），和一個整數k，回傳num + k的陣列表示形式。
Example:
Input: num = [1,2,0,0], k = 34 Output: [1,2,3,4]
Intuition
TIP
核心思路：從最低位開始逐位相加，處理進位——本質上就是大數加法。
- 從陣列末尾開始，加上 k 的最低位和進位
- k 本身可以當作進位值：每次取
k % 10作為當前位加數，k / 10作為下一位 - 當陣列和 k 都處理完後，結果需要反轉
Approaches
1. Digit-by-Digit Add (k as Carry) — O(max(n, log k)) / O(max(n, log k))
- Idea: 從右到左遍歷，把 k 直接當作加數逐位消耗
- Time:
O(max(n, log k))- n 為陣列長度 - Space:
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. More Intuitive Carry Split — O(max(n, log k)) / O(max(n, log k))
- Idea: 明確分離 carry 和 k 的邏輯，逐位計算
- Time:
O(max(n, log k)) - Space:
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: 大數加法——從低位到高位逐位相加並處理進位
- Key trick: 把 k 直接當作 carry 的初始值可以簡化程式碼，不需要分別處理 k 的每一位