989. 数组形式的整数加法

题目描述

思路

两个方法

1. 模拟竖式计算，逐位相加，注意进位。
   • 如果K加完了而A还没加完
     若有进位则执行去掉K的逐位加法，直到无进位或A也加完，若无进位，则直接将A添加到结果数组中。
   • 如果A加完了而K还没加完
     将进位加到K的剩余位上，然后将K添加到结果数组中。
   • 如果同时加完
     若有进位直接在结果数组中添加一位1
2. 将A中的每个数加到K上

竖式计算

创建一个结果List，将每一步的结果添加到该List的最末尾，最终将List翻转（最终再翻转相比较直接添加到末尾的方法更快）
代码如下：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public List<Integer> addToArrayForm(int[] A, int K) {
        int length = A.length;
        int last = 0;
        int overflow = 0;
        List<Integer> res = new ArrayList<>();
        for (int i = length - 1; i >= 0; i--) {
            last = K % 10;
            K = K / 10;

            int temp = A[i] + last + overflow;
            res.add(temp % 10);
            overflow = temp >= 10 ? 1 : 0;

            if (K == 0) {
                if (i == 0) {
                    if (overflow == 1) {
                        res.add(1);
                        overflow = 0;
                    }
                } else {
                    for (int j = i - 1; j >= 0; j--) {
                        if (overflow == 0) {
                            List<Integer> listA = Arrays.stream(A).boxed().collect(Collectors.toList());
                            List<Integer> subListA = listA.subList(0, j + 1);
                            Collections.reverse(subListA);
                            res.addAll(subListA);
                            break;
                        }
                        temp = A[j] + overflow;
                        res.add(temp % 10);
                        overflow = temp >= 10 ? 1 : 0;
                    }
                    if (overflow == 1) {
                        res.add(1);
                        overflow = 0;
                    }
                }
                break;
            }
        }

        while (K != 0) {
            last = K % 10;
            K = K / 10;

            int temp = last + overflow;
            res.add(temp % 10);

            overflow = temp >= 10 ? 1 : 0;
        }

        if (overflow == 1) {
            res.add(1);
        }
        Collections.reverse(res);
        return res;
    }
}

执行用时：14 ms, 在所有 Java 提交中击败了13.72%的用户
内存消耗：40.3 MB, 在所有 Java 提交中击败了28.82%的用户

加到K上

代码如下：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public List<Integer> addToArrayForm(int[] A, int K) {
        int length = A.length;
        List<Integer> res = new ArrayList<>();
        for (int i = length - 1; i >= 0 || K > 0; i--) {
            if (i >= 0) {
                K = K + A[i];
            }
            res.add(K % 10);
            K = K / 10;
        }
        Collections.reverse(res);
        return res;
    }
}

执行用时：5 ms, 在所有 Java 提交中击败了56.68%的用户
内存消耗：39.9 MB, 在所有 Java 提交中击败了46.10%的用户