989. 数组形式的整数加法#

题目#

1
对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。
2

3
例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。
4

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

7
示例 1：
8

9
输入：A = [1,2,0,0], K = 34
10
输出：[1,2,3,4]
11
解释：1200 + 34 = 1234
12
示例 2：
13

14
输入：A = [2,7,4], K = 181
15
输出：[4,5,5]
16
解释：274 + 181 = 455
17
示例 3：
18

19
输入：A = [2,1,5], K = 806
20
输出：[1,0,2,1]
21
解释：215 + 806 = 1021
22
示例 4：
23

24
输入：A = [9,9,9,9,9,9,9,9,9,9], K = 1
25
输出：[1,0,0,0,0,0,0,0,0,0,0]
26
解释：9999999999 + 1 = 10000000000
27

28

29
提示：
30

31
1 <= A.length <= 10000
32
0 <= A[i] <= 9
33
0 <= K <= 10000
34
如果 A.length > 1，那么 A[0] != 0

题目思路#

建立一个动态数组 res，以位数的形式存储最后的结果值；
既可以通过对 k 取 10 的模值进行加减，也可以从后往前与 k 相加，再对相加得到的值对 10 取模；
如果 k 的位数大于数组所给的位数，那么循环内 k 除以 10 后余留的值必然大于 0；
此时需要扩展数组，由于是动态数组，直接在循环内改写为类似 k = sum / 10 的形式，即 k /= 10，直到 k 为 0 为止；
最后将数组逆序输出即可。

题目代码#

代码块#

1
class Solution {
2
    public List<Integer> addToArrayForm(int[] num, int k) {
3
        List<Integer> res = new ArrayList<>();
4
        int n = num.length;
5
        for(int i = num.length - 1; i >= 0; i--) {
6
            int sum = num[i] + k % 10;
7
            k /= 10;
8
            if(sum >= 10) {
9
                k++;
10
                sum -= 10;
11
            }
12
            res.add(sum);
13
        }
14
        for(; k > 0; k /= 10) {
15
            res.add(k % 10);
16
        }
17
        // Collections.reverse 源码中会判断对存储的数据结构进行判断，如果支持随机存储的数据结构，默认使用的是 swap 交换元素，而如果是链表，那么默认使用的是头插法进行逆序
18
        Collections.reverse(res);
19
        return res;
20
    }
21
}

1
class Solution {
2
public:
3
    vector<int> addToArrayForm(vector<int>& nums, int k) {
4
        vector<int> res;
5

6
        for(int i = nums.size() - 1; i >= 0; i--)
7
        {
8
            int sum = nums[i] + k;
9
            res.push_back(sum % 10);
10
            k = sum / 10;
11
        }
12

13
        while(k > 0)
14
        {
15
            res.push_back(k % 10);
16
            k /= 10;
17
        }
18

19
        reverse(res.begin(), res.end());
20

21
        return res;
22
    }
23
};

1
func addToArrayForm(num []int, k int) []int {
2
    n := len(num)
3
    ans := make([]int, 0)
4

5
    for i := n - 1; i >= 0; i-- {
6
        v := num[i] + k;
7
        ans = append(ans, v % 10)
8
        k = v / 10
9

10
    }
11

12
    for k > 0 {
13
        ans = append(ans, k % 10)
14
        k = k / 10
15
    }
16

17
    return reverse(ans)
18
}
19

20
func reverse(num []int) []int {
21
    for i, j := 0, len(num) - 1; i <= j; {
22
        num[i], num[j] = num[j], num[i]
23
        i++
24
        j--
25
    }
26

27
    return num;
28
}

复杂度#

空间复杂度：申请了一个常数级数组，故空间为 O(1)
时间复杂度： $O(max(n, \log k))$ ，其中 n 为数组的长度。