Skip to content

Commit ed4827e

Browse files
add 445
1 parent e201251 commit ed4827e

File tree

3 files changed

+49
-8
lines changed

3 files changed

+49
-8
lines changed

README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -98,7 +98,7 @@ Your ideas/fixes/algorithms are more than welcome!
9898
|449|[Serialize and Deserialize BST](https://leetcode.com/problems/serialize-and-deserialize-bst/)|[Solution](../master/src/main/java/com/stevesun/solutions/SerializeandDeserializeBST.java)| O(n)|O(h) | Medium| BFS
9999
|448|[Find All Numbers Disappeared in an Array](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/)|[Solution](../master/src/main/java/com/stevesun/solutions/FindAllNumbersDisappearedinanArray.java)| O(n)|O(1) | Easy| Array, HashMap
100100
|447|[Number of Boomerangs](https://leetcode.com/problems/number-of-boomerangs/)|[Solution](../master/src/main/java/com/stevesun/solutions/NumberofBoomerangs.java)| O(n^2)|O(n) | Easy| HashMap
101-
|445|[Add Two Numbers II](https://leetcode.com/problems/add-two-numbers-ii/)|[Solution](../master/src/main/java/com/stevesun/solutions/AddTwoNumbersII.java)| O(max(m,n)|O(max(m,n)) | Medium| Stack
101+
|445|[Add Two Numbers II](https://leetcode.com/problems/add-two-numbers-ii/)|[Solution](../master/src/main/java/com/stevesun/solutions/_445.java)| O(max(m,n)|O(max(m,n)) | Medium| Stack, LinkedList
102102
|442|[Find All Duplicates in an Array](https://leetcode.com/problems/find-all-duplicates-in-an-array/)|[Solution](../master/src/main/java/com/stevesun/solutions/FindAllDuplicatesinanArray.java)| O(n)|O(1) | Medium| Array
103103
|441|[Arranging Coins](https://leetcode.com/problems/arrange-coins/)|[Solution](../master/src/main/java/com/stevesun/solutions/ArrangingCoins.java)| O(n)|O(1) | Easy|
104104
|438|[Find All Anagrams in a String](https://leetcode.com/problems/find-all-anagrams-in-a-string/)|[Solution](../master/src/main/java/com/stevesun/solutions/FindAllAnagramsinaString.java)| O(n)|O(1) | Easy|

src/main/java/com/stevesun/solutions/AddTwoNumbersII.java renamed to src/main/java/com/stevesun/solutions/_445.java

Lines changed: 9 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,8 @@
22

33
import com.stevesun.common.classes.ListNode;
44

5+
import java.util.ArrayDeque;
6+
import java.util.Deque;
57
import java.util.Stack;
68

79
/**
@@ -17,17 +19,17 @@
1719
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
1820
Output: 7 -> 8 -> 0 -> 7
1921
*/
20-
public class AddTwoNumbersII {
22+
public class _445 {
2123

2224
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
23-
Stack<Integer> stack1 = popIntoStack(l1);
24-
Stack<Integer> stack2 = popIntoStack(l2);
25+
Deque<Integer> stack1 = popIntoStack(l1);
26+
Deque<Integer> stack2 = popIntoStack(l2);
2527

2628
int sum = 0;
2729
ListNode list = new ListNode(0);
2830
while (!stack1.isEmpty() || !stack2.isEmpty()) {
29-
if (!stack1.isEmpty()) sum += stack1.pop();
30-
if (!stack2.isEmpty()) sum += stack2.pop();
31+
if (!stack1.isEmpty()) sum += stack1.removeFirst();
32+
if (!stack2.isEmpty()) sum += stack2.removeFirst();
3133
list.val = sum % 10;
3234
ListNode head = new ListNode(sum / 10);
3335
head.next = list;
@@ -37,9 +39,9 @@ public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
3739
return list.val == 0 ? list.next : list;
3840
}
3941

40-
private Stack<Integer> popIntoStack(ListNode head) {
42+
private Deque<Integer> popIntoStack(ListNode head) {
4143
ListNode tmp = head;
42-
Stack<Integer> stack = new Stack<>();
44+
Deque<Integer> stack = new ArrayDeque<>();
4345
while (tmp != null) {
4446
stack.push(tmp.val);
4547
tmp = tmp.next;
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package com.stevesun;
2+
3+
import com.stevesun.common.classes.ListNode;
4+
import com.stevesun.solutions._171;
5+
import com.stevesun.solutions._445;
6+
import org.junit.BeforeClass;
7+
import org.junit.Test;
8+
9+
import static org.junit.Assert.assertEquals;
10+
11+
/**
12+
* Created by stevesun on 5/13/17.
13+
*/
14+
public class _445Test {
15+
private static _445 test;
16+
17+
@BeforeClass
18+
public static void setup(){
19+
test = new _445();
20+
}
21+
22+
@Test
23+
public void test1(){
24+
ListNode l1 = new ListNode(7);
25+
l1.next = new ListNode(2);
26+
l1.next.next = new ListNode(4);
27+
l1.next.next.next = new ListNode(3);
28+
29+
ListNode l2 = new ListNode(5);
30+
l2.next = new ListNode(6);
31+
l2.next.next = new ListNode(4);
32+
33+
ListNode expected = new ListNode(7);
34+
expected.next = new ListNode(8);
35+
expected.next.next = new ListNode(0);
36+
expected.next.next.next = new ListNode(7);
37+
assertEquals(expected, test.addTwoNumbers(l1, l2));
38+
}
39+
}

0 commit comments

Comments
 (0)