Leetcode-898 Add to Array-Form of Integer

Description

For a non-negative integer X, the array-form of X is an array of its digits in left to right order. For example, if X = 1231, then the array form is [1,2,3,1].

Given the array-form A of a non-negative integer X, return the array-form of the integer X+K.

Example 1:

1
2
3
Input: A = [1,2,0,0], K = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

Example 2:

1
2
3
Input: A = [2,7,4], K = 181
Output: [4,5,5]
Explanation: 274 + 181 = 455

Example 3:

1
2
3
Input: A = [2,1,5], K = 806
Output: [1,0,2,1]
Explanation: 215 + 806 = 1021

Example 4:

1
2
3
Input: A = [9,9,9,9,9,9,9,9,9,9], K = 1
Output: [1,0,0,0,0,0,0,0,0,0,0]
Explanation: 9999999999 + 1 = 10000000000

Note:

  1. 1 <= A.length <= 10000
  2. 0 <= A[i] <= 9
  3. 0 <= K <= 10000
  4. If A.length > 1, then A[0] != 0

分析

给一个数组形式的整数 X 和一个整数 K,求 X+K,其中 XK 都是五位数以内的整数,所以无需考虑溢出。

拆解 K 成 Array-Form 类型得到一个整数,然后两个数组末位对齐,逐位相加即可。

拆解 K 的过程可以取余,余数与 X 的末位相加即可

1
2
3
4
while (K != 0) {
r = K % 10;
K = K / 10;
}

程序设计

根据上述分析,代码实现如下,

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
43
44
45
class Solution {
public List<Integer> addToArrayForm(int[] A, int K) {
int carry = 0;
for(int i = A.length-1; i >= 0; i--){
if (K!=0) {
int a = K%10;
int b = A[i];
int sum = a + b + carry;
carry = sum / 10;
A[i] = sum % 10;
K /= 10;
} else {
int sum = A[i] + carry;
if( sum < 10) {
A[i] = sum;
carry = 0;
break;
} else {
A[i] = sum % 10;
carry = 1;
}
}
}

List<Integer> ans = new ArrayList<>();
if(K != 0) {
K += carry;
Stack<Integer> stack = new Stack<>();

while(K != 0) {
stack.push(K % 10);
K /= 10;
}
while(!stack.isEmpty()) {
ans.add(stack.pop());
}
} else if(carry == 1) {
ans.add(1);
}
for(int i = 0; i < A.length; i++) {
ans.add(A[i]);
}
return ans;
}
}

本文标题:Leetcode-898 Add to Array-Form of Integer

文章作者:Syncher

发布时间:2019年07月23日 - 15:07

最后更新:2019年08月02日 - 09:08

原始链接:https://0x400.com/2019-07-23-lc-989-add-to-array-form-of-integer.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。