【LeetCode】989. Add to Array-Form of Integer 解题报告（C++）

作者：负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/

题目描述

For a non-negative integer X, the array-form of X is an array of its digits in left to right order. For example, if X = 1231, then the array form is [1,2,3,1].

Given the array-form A of a non-negative integer X, return the array-form of the integer X+K.

Example 1:

Input: A = [1,2,0,0], K = 34

Output: [1,2,3,4]

Explanation: 1200 + 34 = 1234

Example 2:

Input: A = [2,7,4], K = 181

Output: [4,5,5]

Explanation: 274 + 181 = 455

Example 3:

Input: A = [2,1,5], K = 806

Output: [1,0,2,1]

Explanation: 215 + 806 = 1021

Example 4:

Input: A = [9,9,9,9,9,9,9,9,9,9], K = 1

Output: [1,0,0,0,0,0,0,0,0,0,0]

Explanation: 9999999999 + 1 = 10000000000

Note：

1 <= A.length <= 10000
0 <= A[i] <= 9
0 <= K <= 10000
If A.length > 1, then A[0] != 0

题目大意

数组A表示了一个整数，K表示了一个整数，把两个数字相加，要求结果也是个数组形式的整数。

解题方法

数组转整数再转数组

一个比较偷懒的方法就是把数组转成整数然后相加，再转成数组的形式。代码也很简单。

python代码如下：

class Solution(object):

    def addToArrayForm(self, A, K):

        """

        :type A: List[int]

        :type K: int

        :rtype: List[int]

        """

        ans = int("".join(map(str, A))) + K

        if ans == 0:

            return [0]

        res = []

        while ans:

            res.append(ans % 10)

            ans /= 10

        return res[::-1]

模拟加法

这个题其实很类似链表加法2. Add Two Numbers，只不过是数组和整数的加法，做起来可以用类似的方式。

我下面的做法就是模拟加法，从低位开始，使用模拟进位的方式，求对应位数字的和。

注意两个数字相加的时候可能不是等长的，所以终止的条件有三个：数组数字用完了、K等于0了、进位也是0了。这三个条件同时满足的时候，才是真正的加法结束的时候。

在做这个题的过程中，如果每次使用res.insert(res.begin(), add)的方法，每次插入的时间是O(N)的，导致最后的代码时间很长。如果使用下面的方式，每次插入到结果的后面，最后再翻转，那么时间会大幅缩短。

C++代码如下：

class Solution {

public:

    vector<int> addToArrayForm(vector<int>& A, int K) {

        const int M = A.size();

        int carry = 0;

        vector<int> res;

        int i = M - 1;

        while (i >= 0 || K != 0 || carry != 0) {

            int a = (i < 0) ? 0 : A[i];

            int add = a + K % 10 + carry;

            if (add >= 10) {

                carry = 1;

                add -= 10;

            } else

                carry = 0;

            res.push_back(add);

            K /= 10;

            --i;

        }

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

        return res;

    }

};

日期

2019 年 2 月 21 日 —— 一放假就再难抓紧了

秒客网