leetcode每日一题2020.1.22

989. 数组形式的整数加法

一、题目

对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。

给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。

示例1：

输入：A = [1,2,0,0], K = 34
输出：[1,2,3,4]
解释：1200 + 34 = 1234

示例2：

输入：A = [2,7,4], K = 181
输出：[4,5,5]
解释：274 + 181 = 455

示例 3：

输入：A = [2,1,5], K = 806
输出：[1,0,2,1]
解释：215 + 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]
解释：9999999999 + 1 = 10000000000

提示：

1. 1 ≤ A.length ≤ 10000
2. 0 ≤ A[i] ≤ 9
3. 0 ≤ K ≤ 10000
4. 如果 A.length > 1，那么 A[0] ≠ 0

二、题解

倒序逐位相加

题解：

对数组 A 倒序遍历，每轮遍历的时候加上 K 对 10 取的余数，将和判断是否大于 10 后加入 ret 数组中，并对 K 进行更新。

遍历完再对 K 做一个遍历直到 K = 0 为止。

例如：A = [1, 2, 3]  K = 912
第一轮遍历： 3 + 2 = 5，此时 K = 91，ret = [5]
第二轮遍历： 2 + 1 = 3，此时 K = 9， ret = [3, 5]
第三轮遍历： 9 + 1 = 10，此时 K = 0 + 1 = 1， ret = [0, 3, 5]
K = 1，还要再向 ret 中加入 1，ret = [1, 0, 3, 5]

• 时间复杂度：O($max{m,n}$)，其中 m 是数组 A 的长度，n 是数字 K 的长度
• 空间复杂度：O($max{m,n}$)。

var addToArrayForm = function (A, K) {
    let ret = [];
    const n = A.length;
    for (let i = n - 1; i >= 0; --i) {
        let sum = A[i] + K % 10;
        K = Math.floor(K / 10);
        if (sum >= 10) {
            ret.unshift(sum % 10);
            K++;
        } else {
            ret.unshift(sum)
        }
    }
    for (; K > 0; K = Math.floor(K / 10)) {
        ret.unshift(K % 10)
    }
    return ret
};