對(duì)于非負(fù)整數(shù) X 而言瞄桨，X 的數(shù)組形式是每位數(shù)字按從左到右的順序形成的數(shù)組。例如，如果 X = 1231乌助，那么其數(shù)組形式為 [1,2,3,1]。
給定非負(fù)整數(shù) X 的數(shù)組形式 A陌知，返回整數(shù) X+K 的數(shù)組形式他托。
示例 1：
輸入：A = [1,2,0,0], K = 34
輸出：[1,2,3,4]
解釋?zhuān)?200 + 34 = 1234
解釋 2：
輸入：A = [2,7,4], K = 181
輸出：[4,5,5]
解釋?zhuān)?74 + 181 = 455
示例 3：
輸入：A = [2,1,5], K = 806
輸出：[1,0,2,1]
解釋?zhuān)?15 + 806 = 1021
示例 4：
輸入：A = [9,9,9,9,9,9,9,9,9,9], K = 1
輸出：[1,0,0,0,0,0,0,0,0,0,0]
解釋?zhuān)?999999999 + 1 = 10000000000
提示：
1 <= A.length <= 10000
0 <= A[i] <= 9
0 <= K <= 10000
如果 A.length > 1，那么 A[0] != 0
解決方案：逐位相加
class Solution {
public List<Integer> addToArrayForm(int[] A, int K) {
int N = A.length;
int cur = K;
List<Integer> ans = new ArrayList();
int i = N;
while (--i >= 0 || cur > 0) {
if (i >= 0)
cur += A[i];
ans.add(cur % 10);
cur /= 10;
}
Collections.reverse(ans);
return ans;
}
}
思路
讓我們逐位將數(shù)字加在一起仆葡。舉一個(gè)例子赏参，如果要計(jì)算 123 與 912 的和。我們順次計(jì)算 3+2沿盅、2+1把篓、1+9。任何時(shí)候腰涧，當(dāng)加法的結(jié)果大于等于 10 韧掩，我們要將進(jìn)位的 1 加入下一位的計(jì)算中去，所以最終結(jié)果等于 1035窖铡。
算法
我們可以對(duì)以上的想法做一個(gè)小變化疗锐，讓它實(shí)現(xiàn)起來(lái)更容易 —— 我們將整個(gè)加數(shù)加入數(shù)組表示的數(shù)的最低位。
繼續(xù)之前的例子 123+912费彼，我們把它表示成 [1, 2, 3+912]滑臊。然后，我們計(jì)算 3+912 = 915敌买。5 留在當(dāng)前這一位，將 910/10=91 以進(jìn)位的形式加入下一位阶界。
然后虹钮，我們?cè)僦貜?fù)這個(gè)過(guò)程，計(jì)算 [1, 2+91, 5]膘融。我們得到 93芙粱，3 留在當(dāng)前位，將 90/10=9 以進(jìn)位的形式加入下一位氧映。繼而又得到 [1+9, 3, 5]春畔，重復(fù)這個(gè)過(guò)程之后，最終得到結(jié)果 [1, 0, 3, 5]。
復(fù)雜度分析
時(shí)間復(fù)雜度： O(\max(N, \log K))O(max(N,logK))律姨，其中 NN 是數(shù)組 A 的長(zhǎng)度振峻。
空間復(fù)雜度： O(\max(N, \log K))O(max(N,logK))。
