这是悦乐书的第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+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论