每天一道公司算法真题，讲解解题思路与各种算法实现；欢迎大家点评或者说出你的解题想法，或评论想让我讲解哪道题！

题目

对于非负整数 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 = [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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-to-array-form-of-integer/

思路

因为数组A的长度可能为10000，转为数值类型是很大的一个值，而且越界现有Java的基本数据类型，所以不能将A转为数字再与K相加。

可以按我们正常算加法的思维，从右到左，依次先相加低位，再算高位。

即我们从数组A的尾部向头部遍历每一个数值，与K相加，保留低位，进位与下一高位继续相加。

算法中我们选择LinkedList来保存结果，是因为LinkedList可以从头部或者从尾部添加节点，方便输出想要顺序结果。

算法实现

package com.nobody;

import java.util.LinkedList;
import java.util.List;

/**
 * @Description 对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。 给定非负整数 X
 * 的数组形式 A，返回整数 X+K 的数组形式。
 * @Author Mr.nobody
 * @Date 2021/1/22
 * @Version 1.0
 */
public class AddToArrayForm { // 因为数组A的长度可能为10000，转为数值类型是很大的一个值，而且越界现有Java的基本数据类型，所以不能将A转为数字再与K相加。 // 可以按我们正常算加法的思维，从右到左，依次先相加低位，再算高位。 // 即我们从数组A的尾部向头部遍历每一个数值，与K相加，保留低位，进位与下一高位继续相加。 public static List<Integer> addToArrayForm(int[] A, int K) { // 向吐槽Leetcode的变量名大写，建议使用驼峰法 // 链表，存相加后的结果 LinkedList<Integer> result = new LinkedList<>(); // 从数组A的最末位开始遍历 int index = A.length - 1; while (index >= 0 || K > 0) { // 数组A的每一位都与K相加 if (index >= 0) { K += A[index]; } // 将相加后的低位保存到链表中 result.addFirst(K % 10); // 去除低位值 K /= 10; // 游标向前 index--; } return result; } public static void main(String[] args) { int[] A = new int[] {1, 2, 0, 0}; int K = 34; System.out.println(addToArrayForm(A, K)); }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
 

输出结果：

[1, 2, 3, 4]

  

 

  
1
 

Leetcode执行结果：

上下篇

上一篇：思路讲解与算法实现 LeetCode - 两数相加

下一篇：思路讲解与算法实现 LeetCode - 实现 strStr()

文章来源: javalib.blog.csdn.net，作者：陈皮的JavaLib，版权归原作者所有，如需转载，请联系作者。

原文链接：javalib.blog.csdn.net/article/details/113046765