数组形式的整数加法

发表于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

LeetCode每日一题，989. Add to Array-Form of Integer

先看题目描述

s5bFm9.png

大意就是给定一个整数 K 和一个数组形式表示的整数 A，让我们以 List 的形式返回相加结果

算法和思路

这题比较简单，只要从末位开始，逐位的将数字相加即可，若有进位，则把进位的 1 加入到下一位的计算中，最后返回结果即可

算法和思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<Integer> addToArrayForm(int[] A, int K) {
        int len = A.length;
        int carry = 0;
        List<Integer> ans = new ArrayList<>();
        int index = len - 1;
        while (index >= 0 || K > 0) {
            int cur = (index >= 0 ? A[index] : 0) + K % 10 + carry;
            ans.add(cur % 10);
            carry = cur / 10;
            K /= 10;
            index--;
        }
        if (carry > 0) {
            ans.add(1);
        }
        Collections.reverse(ans);
        return ans;
    }
}

注意：每次将数字添加到 list 的最后一位，最后翻转 list，比每次都把数字添加到 list 的第一位运行速度更快

下面是题解提供的另一种思路，将整个加数 K 加入数组表示的数的最低位。

上面的例子 123+912，我们把它表示成 [1,2,3+912]。然后，我们计算 3+912=915。5 留在当前这一位，将 910/10=91 以进位的形式加入下一位

然后，我们再重复这个过程，计算 [1,2+91,5]。我们得到 93，3 留在当前位，将 90/10=9 以进位的形式加入下一位。继而又得到 [1+9,3,5]，重复这个过程之后，最终得到结果 [1,0,3,5]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<Integer> addToArrayForm(int[] A, int K) {
        List<Integer> res = new ArrayList<Integer>();
        int n = A.length;
        for (int i = n - 1; i >= 0 || K > 0; --i, K /= 10) {
            if (i >= 0) {
                K += A[i];
            }
            res.add(K % 10);
        }
        Collections.reverse(res);
        return res;
    }
}