题目
对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。
例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。
给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。
题干
数组 + 整数
思路
一定不要想着将数组化为整数相机 因为数组的位数是不限的 临时变量即使是long也无法存储 而且要考虑两边长度不齐的问题 可以先遍历一边 等遍历完 将另一边的剩余位数补齐
位数相加
让数组的个位和整数的个位相加 进位将1 加到剩余的整数中
只加个位
将整数直接加到个位的地方 通过进位的形式 加到数组前面
解答
位数相加
public class Solution {
public static List<Integer> addToArrayForm(int[] num, int k) {
List<Integer> results = new ArrayList<>();
//按位相加
for(int i=num.length-1;i>=0;i--){
int add = num[i]+k%10;
k=k/10;
if(add>=10){
k++; //如果发生进位 就把进位的1 放到后续的数 91/10 = 9 如果有进位 9+1 =10
add-=10;
}
results.add(add);
}
//数组遍历完 k还有值
for(; k > 0; k /= 10){
results.add(k % 10);
}
Collections.reverse(results);
System.out.println("");
printList(results);
return results;
}
}
只加个位
class Solution {
public List<Integer> addToArrayForm(int[] num, int k) {
List<Integer> res = new ArrayList<Integer>();
int n = num.length;
for (int i = n - 1; i >= 0 || k > 0; --i, k /= 10) { //循环到n结束或者K位数整除完
if (i >= 0) {
k += num[i];
}
res.add(k % 10);
}
Collections.reverse(res);
return res;
}
}
时空复杂度分析
如果采用位数相加解法 时间复杂度为O(n+logK) 空间复杂度为O(1) 除了返回值使用到的为常数
如果采用只加个位解法 时间复杂度为O(Max(n,logK) 空间复杂度为O(1) 虽然是一个量级 个位解法更快
解题技巧 总结形成套路
当前位 = (A 的当前位 + B 的当前位 + 进位carry) % 10
注意，AB两数都加完后，最后判断一下进位 carry, 进位不为 0 的话加在前面。
while ( A 没完 || B 没完)
A 的当前位
B 的当前位
和 = A 的当前位 + B 的当前位 + 进位carry
当前位 = 和 % 10;
进位 = 和 / 10;
判断还有进位吗
结语
此题涉及到数的位数 /10 和%10 分别有什么作用 进位如何实现 一定要清楚 还要考虑边界补位
