LeetCode.989-数组形式的整数做加法(Add to Array-Form of Integer)

这是悦乐书的第371次更新，第399篇原创

01 看题和准备

今天介绍的是

LeetCode

算法题中

Easy

级别的第

233

题（顺位题号是

989

）。对于非负整数

X

，

X

的数组形式是从左到右顺序的数字数组。例如，如果

X = 1231

，则数组形式为

[1,2,3,1]

。

给定非负整数

X

的数组形式

A

，返回整数

X + K

的数组形式。例如：

输入：A = [1,2,0,0]，K = 34

输出：[1,2,3,4]

说明：1200 + 34 = 1234

输入：A = [2,7,4]，K = 181

输出：[4,5,5]

说明：274 + 181 = 455

输入：A = [2,1,5]，K = 806

输出：[1,0,2,1]

说明：215 + 806 = 1021

输入：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。

02 第一种解法

题目的意思是要我们把

K

（低位到高位）每一位数加到

A

（从后往前）中对应位上，最后输出一个

List

思路：先处理

K

，每次拿

A

的个位数，使用对

10

取余得到，再从

A

中取一位数出来（从后往前），两数相加，需要判断是否有进位产生，将和添加进

List

中，

K

再除以10，切换到新的个位数，直到

K

等于0。处理完

K

后，如果

A

中还有数没处理完，需要再处理下，在前面处理

K

时遗留的进位依旧需要参与运算，直到处理完

A

中所有元素。最后，如果存进位的变量还有值，则需要将其添加进

List

中。因为处理数据是从后往前的顺序，所以需要将

List

反转，借助

Collections

的

reverse

方法完成。

public List<Integer> addToArrayForm(int[] A, int K) {
    List<Integer> result = new ArrayList<Integer>(); 
    int i = A.length-1, tem = 0;
    while (K > 0) {
        // i需要判断一次，因为A的长度可能比K的位数小
        int current = K%10 + (i >=0 ? A[i--] : 0) + tem;
        // 大于10会产生进位
        if (current >= 10) {
            current -= 10;
            tem = 1;
        } else {
            tem = 0;
        }
        result.add(current);
        K /= 10;
    }
    // 如果K已经处理完了，但是A中还有数没有处理
    while (i >= 0) {
        // 依旧需要判断进位
        if (A[i]+tem >= 10) {
            result.add(A[i]+tem-10);
            tem = 1;
        } else {
            result.add(A[i]+tem);
            tem = 0;
        }
        i--;
    }
    // 判断最高位是否存在进位
    if (tem != 0) {
        result.add(tem);
    }
    // 反转result
    Collections.reverse(result);
    return result;
}
           

03 第二种解法

我们还可以对第一种解法再简化下。

思路：将A中每次从后往前取的数，加到

K

上面（

K

最大为10000，不存在越界问题），然后每次取

K

的最后一位数（借助取余），计算完后将

K

除以10，直到

K

等于0。

public List<Integer> addToArrayForm2(int[] A, int K) {
    List<Integer> result = new ArrayList<Integer>(); 
    int i = A.length-1, tem = K;
    while (i >= 0 || tem > 0) {
        if (i >= 0) {
            tem += A[i--];
        }
        result.add(tem%10);
        tem /= 10;
    }
    // 反转result
    Collections.reverse(result);
    return result;
}
           

04 小结

算法专题目前已连续日更超过七个月，算法题文章239+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！