算法-数组形式的整数加法

版权声明： https://blog.csdn.net/li_xunhuan/article/details/90200722

题目描述：

对于非负整数 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 <= A.length <= 10000
0 <= A[i] <= 9
0 <= K <= 10000
如果 A.length > 1，那么 A[0] != 0

代码1：

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;
}
}

分析：

实际上要表示这个过程，思路上是比较简单的，我们将K直接与数组形式保存的整数的最低位，也就是A[A.length-1]相加，其求和结果取余%10保存，为了得到个位数，即不需进位的部分；其求和部分 整型除法：/10进位到和A[A.length-2]相加；这整个过程以此类推，直到得到最终结果。

第二点要分析的是cur这个操作变量，类似于数字逻辑中的全加器，虽然cur=K作为一个用户输入的数据，但是完全可以把其看作其他任意逻辑器件传来的进位数，所以我们无需再新建一个变量来储存进位数；

思路简单，往往伴随着小问题；比如说数组最终是要进位的，比如[9,9,9]+11;或者是[0]+1000那么得到的数组长度是大于原来数组长度的；但是我们对于数组的遍历，普遍使用循环使用int i =A.length来控制的，这样一来循环结束，进位没法操作； 我的第一个想法是我们根据进位是否为0，再写一个循环语句；但是实际上超出数组长度进位的操作和不超出数组长度的进位操作是相当类似的，我们完全可以合并到一个语句块：

 while (--i >= 0 || cur > 0) {
        if (i >= 0)
            cur += A[i];
        ans.add(cur % 10);
        cur /= 10;
    }

这是我们不常见的数组遍历控制语句