8000 add 989 · Mars2018/Leetcode-3@81c9ec7 · GitHub
[go: up one dir, main page]
Skip to content

Commit 81c9ec7

Browse files
fishercoder1534fishercoder1534
committed
add 989
1 parent 38edb0c commit 81c9ec7

File tree

3 files changed

+123
-0
lines changed

3 files changed

+123
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,7 @@ Your ideas/fixes/algorithms are more than welcome!
2929

3030
| # | Title | Solutions | Time | Space | Video | Difficulty | Tag
3131
|-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
32+
|989|[Add to Array-Form of Integer](https://leetcode.com/problems/add-to-array-form-of-integer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_989.java) | O(max(N, logk)) | O(max(N, logk)) | |Easy| Array
3233
|985|[Sum of Even Numbers After Queries](https://leetcode.com/problems/sum-of-even-numbers-after-queries/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_985.java) | O(n) | O(n) | |Easy| Array
3334
|977|[Squares of a Sorted Array](https://leetcode.com/problems/squares-of-a-sorted-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_977.java) | O(nlogn) | O(1) | |Easy| Array
3435
|976|[Largest Perimeter Triangle](https://leetcode.com/problems/largest-perimeter-triangle/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_976.java) | O(nlogn) | O(1) | |Easy| Math Array

‎src/main/java/com/fishercoder/solutions/_989.java

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.ArrayList;
4+
import java.util.Collections;
5+
import java.util.List;
6+
7+
/**
8+
* 989. Add to Array-Form of Integer
9+
*
10+
* 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].
11+
*
12+
* Given the array-form A of a non-negative integer X, return the array-form of the integer X+K.
13+
*
14+
* Example 1:
15+
*
16+
* Input: A = [1,2,0,0], K = 34
17+
* Output: [1,2,3,4]
18+
* Explanation: 1200 + 34 = 1234
19+
* Example 2:
20+
*
21+
* Input: A = [2,7,4], K = 181
22+
* Output: [4,5,5]
23+
* Explanation: 274 + 181 = 455
24+
* Example 3:
25+
*
26+
* Input: A = [2,1,5], K = 806
27+
* Output: [1,0,2,1]
28+
* Explanation: 215 + 806 = 1021
29+
* Example 4:
30+
*
31+
* Input: A = [9,9,9,9,9,9,9,9,9,9], K = 1
32+
* Output: [1,0,0,0,0,0,0,0,0,0,0]
33+
* Explanation: 9999999999 + 1 = 10000000000
34+
*
35+
* Note：
36+
*
37+
* 1 <= A.length <= 10000
38+
* 0 <= A[i] <= 9
39+
* 0 <= K <= 10000
40+
* If A.length > 1, then A[0] != 0
41+
*/
42+
public class _989 {
43+
public static class Solution1 {
44+
public List<Integer> addToArrayForm(int[] A, int K) {
45+
List<Integer> kDigitsReversed = new ArrayList<>();
46+
int divisor = 10;
47+
while (K != 0) {
48+
kDigitsReversed.add(K % divisor);
49+
K /= 10;
50+
}
51+
List<Integer> result = new ArrayList<>();
52+
int prevFlow = 0;
53+
for (int i = A.length - 1, j = 0; i >= 0 || j < kDigitsReversed.size(); i --, j++) {
54+
int sum;
55+
if (i >= 0 && j < kDigitsReversed.size()) {
56+
sum = A[i] + kDigitsReversed.get(j);
57+
} else if (i >= 0) {
58+
sum = A[i];
59+
} else {
60+
sum = kDigitsReversed.get(j);
61+
}
62+
int flow = 0;
63+
if (prevFlow != 0) {
64+
sum += prevFlow;
65+
}
66+
if (sum > 9) {
67+
flow = 1;
68+
}
69+
sum %= 10;
70+
prevFlow = flow;
71+
result.add(sum);
72+
}
73+
if (prevFlow != 0) {
74+
result.add(prevFlow);
75+
}
76+
Collections.reverse(result);
77+
return result;
78+
}
79+
}
80+
}

‎src/test/java/com/fishercoder/_989Test.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._989;
4+
import java.util.Arrays;
5+
import org.junit.BeforeClass;
6+
import org.junit.Test;
7+
8+
import static junit.framework.Assert.assertEquals;
9+
10+
public class _989Test {
11+
private static _989.Solution1 solution1;
12+
private static int[] A;
13+
14+
@BeforeClass
15+
public static void setup() {
16+
solution1 = new _989.Solution1();
17+
}
18+
19+
@Test
20+
public void test1() {
21+
A = new int[] {1, 2, 0, 0};
22+
assertEquals(Arrays.asList(1, 2, 3, 4), solution1.addToArrayForm(A, 34));
23+
}
24+
25+
@Test
26+
public void test2() {
27+
A = new int[] {2, 7, 4};
28+
assertEquals(Arrays.asList(4, 5, 5), solution1.addToArrayForm(A, 181));
29+
}
30+
31+
@Test
32+
public void test3() {
33+
A = new int[] {2, 1, 5};
34+
assertEquals(Arrays.asList(1, 0, 2, 1), solution1.addToArrayForm(A, 806));
35+
}
36+
37+
@Test
38+
public void test4() {
39+
A = new int[] {9, 9, 9, 9, 9, 9, 9, 9, 9, 9};
40+
assertEquals(Arrays.asList(1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), solution1.addToArrayForm(A, 1));
41+
}
42+
}

0 commit comments

Comments
 (0)
0