Skip to content

Commit 9320299

Browse files
awangdevawangdev
committed
linked list, trie, sum-carry, dfs
1 parent 2544cc1 commit 9320299

12 files changed

Lines changed: 1120 additions & 816 deletions

‎Java/Add Binary.java‎

Lines changed: 57 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,10 @@
11
E
2+
1519709164
23

34
方法一:土办法没技术，把binary换成数字，加起来，再换成binary。如果input很大，那么很可能int,long都hold不住。不保险。
45

56
方法二:一般方法，string化为charArray,然后逐位加起，最后记得处理多余的一个carry on
6-
7+
注意: 需要从末尾加起来, 所以要用一个diff来帮助 shortArray[i-diff] 指向 shortArray的相对应index.
78

89
```
910
/*
@@ -20,40 +21,43 @@ Given two binary strings, return their sum (also a binary string).
2021
2122
Tags Expand
2223
String Binary Facebook
23-
24-
25-
2624
*/
2725

2826
/*
29-
//Thougths:
30-
1. Turn string binary format into integer
31-
2. add integer
32-
3. turn integer into binary string
33-
Note: this just test if we know how to manipulate string/binary/Integer
27+
Thoughts:
28+
Can't just convert to int because of Integer.MAX_VALUE limitation.
29+
Convert to char, and add up all chars
3430
*/
35-
36-
public class Solution {
37-
/**
38-
* @param a a number
39-
* @param b a number
40-
* @return the result
41-
*/
31+
class Solution {
4232
public String addBinary(String a, String b) {
43-
if (a == null || b == null || a.length() == 0 || b.length() == 0) {
44-
return null;
33+
if (a == null || b == null) {
34+
return a == null ? b : a;
35+
}
36+
int m = a.length();
37+
int n = b.length();
38+
int size = Math.max(m, n);
39+
char[] result = new char[size];
40+
char[] longArray = m > n ? a.toCharArray() : b.toCharArray();
41+
char[] shortArray = m > n ? b.toCharArray() : a.toCharArray();
42+
int diff = longArray.length - shortArray.length; // important
43+
int carry = 0;
44+
for (int i = size - 1; i >= 0; i--) {
45+
int sum = carry + (longArray[i] - '0');
46+
if (i - diff >= 0) {
47+
sum += (shortArray[i - diff] - '0');
48+
}
49+
carry = sum / 2;
50+
result[i] = (char)(sum % 2 + '0');
4551
}
46-
int decimalA = Integer.parseInt(a, 2);
47-
int decimalB = Integer.parseInt(b, 2);
48-
49-
int sum = decimalA + decimalB;
5052

51-
return Integer.toBinaryString(sum);
53+
if (carry != 0) {
54+
return "1" + new String(result);
55+
}
56+
return new String(result);
5257
}
5358
}
5459

5560

56-
5761
/*
5862
Thought:
5963
Use binary property, add all and move carry-on
@@ -87,4 +91,33 @@ public String addBinary(String a, String b) {
8791
}
8892

8993

94+
/*
95+
//Thougths:
96+
1. Turn string binary format into integer
97+
2. add integer
98+
3. turn integer into binary string
99+
Note: this just test if we know how to manipulate string/binary/Integer
100+
*/
101+
102+
public class Solution {
103+
/**
104+
* @param a a number
105+
* @param b a number
106+
* @return the result
107+
*/
108+
public String addBinary(String a, String b) {
109+
if (a == null || b == null || a.length() == 0 || b.length() == 0) {
110+
return null;
111+
}
112+
int decimalA = Integer.parseInt(a, 2);
113+
int decimalB = Integer.parseInt(b, 2);
114+
115+
int sum = decimalA + decimalB;
116+
117+
return Integer.toBinaryString(sum);
118+
}
119+
}
120+
121+
122+
90123
```

‎Java/Add Digits.java‎

Lines changed: 25 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,9 @@
11
E
2+
1519709532
23

3-
方法1: 普通做法就是按照题意, 把每个digit加起来. O(n)
4+
方法1: 普通做法就是按照题意, double-while loop把数字加起来. 第一层循环是O(n), 然后第二层循环就少很多数位, overall O(n)
45

5-
方法2: 找数学规律, 每过9个数字, 取mod就会开始重复, 所以给所有数字取mod 就可以间接找到答案.
6+
方法2: 找数学规律, 每过9个数字, 取mod就会开始重复, 所以给所有数字取mod 就可以间接找到答案. O(1)
67

78
```
89
/*
@@ -16,6 +17,28 @@
1617
Could you do it without any loop/recursion in O(1) runtime?
1718
*/
1819

20+
/*
21+
Thoughts:
22+
Keep adding until result < 10
23+
Double-while loop: start with a num, calculate result, then num = result.
24+
*/
25+
class Solution {
26+
public int addDigits(int num) {
27+
if (num < 10) {
28+
return num;
29+
}
30+
while (num > 9) {
31+
int temp = 0;
32+
while (num != 0) {
33+
temp += num % 10;
34+
num = num / 10;
35+
}
36+
num = temp;
37+
}
38+
return num;
39+
}
40+
}
41+
1942
class Solution {
2043
public int addDigits(int num) {
2144
return (num - 1) % 9 + 1;

‎Java/Add Two Numbers II.java‎

Lines changed: 68 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,13 @@
11
M
2+
1519711895
23

3-
LinkedList并没有反过来，那么自己反：
4-
方向相反。巧用stack.
4+
Singly-linked list需要reverse, 用stack.
5+
最终结果要恢复成input list 那样的sequence方向, 用stack一个个pop()刚好就可以做到.
56

6-
做加法都一样：
7-
1. carrier
8-
2. carrier = (rst + carrier) / 10
9-
3. rst = (rst + carrier) % 10
7+
加法都一样:
8+
1. sum = carry
9+
2. carry = sum / 10
10+
3. sum = sum % 10;
1011

1112
```
1213
/*
@@ -23,6 +24,67 @@
2324
Linked List High Precision
2425
*/
2526

27+
/**
28+
* Definition for singly-linked list.
29+
* public class ListNode {
30+
* int val;
31+
* ListNode next;
32+
* ListNode(int x) { val = x; }
33+
* }
34+
*/
35+
/*
36+
Thoughts:
37+
Reverse the items in stack.
38+
Add two stacks and save the result in stack as well.
39+
Use top of the result stack as header of the result ListNode
40+
Time, Space: O(n)
41+
*/
42+
class Solution {
43+
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
44+
if (l1 == null || l2 == null) {
45+
return l1 == null ? l2 : l1;
46+
}
47+
Stack<ListNode> s1 = new Stack<ListNode>();
48+
Stack<ListNode> s2 = new Stack<ListNode>();
49+
Stack<ListNode> result = new Stack<ListNode>();
50+
while (l1 != null) {
51+
s1.push(l1);
52+
l1 = l1.next;
53+
}
54+
while (l2 != null) {
55+
s2.push(l2);
56+
l2 = l2.next;
57+
}
58+
59+
// sum up
60+
int carry = 0;
61+
while (!s1.isEmpty() || !s2.isEmpty()) {
62+
int sum = carry;
63+
if (!s1.isEmpty()) {
64+
sum += s1.pop().val;
65+
}
66+
if (!s2.isEmpty()) {
67+
sum += s2.pop().val;
68+
}
69+
carry = sum / 10;
70+
sum = sum % 10;
71+
result.push(new ListNode(sum));
72+
}
73+
if (carry != 0) {
74+
result.push(new ListNode(carry));
75+
}
76+
77+
// Convert to list
78+
ListNode node = new ListNode(-1);
79+
ListNode dummy = node;
80+
while (!result.isEmpty()) {
81+
node.next = result.pop();
82+
node = node.next;
83+
}
84+
return dummy.next;
85+
}
86+
}
87+
2688
/*
2789
Thoughts: Different from Add Two Numbers I, which is in reverse order.
2890
6 1 7

‎Java/Add Two Numbers.java‎

Lines changed: 49 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,14 @@
1-
E
1+
M
2+
1519711343
23

3-
LinkedList都已经反转好了，直接做。
4+
LinkedList都已经反转好了，直接做.
5+
遍历两个l1,l2把carry-on处理好，每次生成一个新node，最后检查carry-on.
46

5-
遍历两个l1,l2把carry-on处理好，每次生成一个新node，最后检查carry-on。
7+
跟Add Binary的理解方式一模一样.
68

7-
跟Add Binary的理解方式一模一样。
9+
注意:
10+
Linked List 没有天然size.
11+
用DummyNode(-1).next来hold住结果.
812

913

1014
```
@@ -38,6 +42,47 @@
3842
* }
3943
* }
4044
*/
45+
46+
/*
47+
Thoughts:
48+
The list has been reversed, just add them up.
49+
Append one more ListNode if there is an carry.
50+
*/
51+
class Solution {
52+
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
53+
if (l1 == null || l2 == null) {
54+
return l1 == null ? l2 : l1;
55+
}
56+
int carry = 0;
57+
ListNode node = new ListNode(-1);
58+
ListNode head = node;
59+
// Add l1 and l2
60+
while (l1 != null || l2 != null) {
61+
int sum = carry;
62+
if (l1 != null) {
63+
sum += l1.val;
64+
l1 = l1.next;
65+
}
66+
if (l2 != null) {
67+
sum += l2.val;
68+
l2 = l2.next;
69+
}
70+
carry = sum / 10;
71+
sum = sum % 10;
72+
node.next = new ListNode(sum);
73+
node = node.next;
74+
}
75+
76+
// Finish adding carry
77+
if (carry != 0) {
78+
node.next = new ListNode(carry);
79+
}
80+
81+
return head.next;
82+
}
83+
}
84+
85+
// Previous solution
4186
public class Solution {
4287
/**
4388
* @param l1: the first list

‎Java/Add and Search Word.java‎

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
11
M
2+
1519707037
23

34
Trie结构, prefix tree的变形： '.'可以代替任何字符，那么就要iterate这个node所有的children.
45

@@ -32,6 +33,77 @@
3233
Trie
3334
*/
3435

36+
/*
37+
Thougths:
38+
Use Trie to store the letters and mark end letter with end = true
39+
Trie structure:
40+
class TrieNode {
41+
HashMap<Character, TrieNode> map;
42+
boolean isEnd;
43+
}
44+
During search, when facing '.', try all possible characters with the given TrieNode.map
45+
*/
46+
class WordDictionary {
47+
class TrieNode {
48+
HashMap<Character, TrieNode> map;
49+
boolean end;
50+
TrieNode() {
51+
this.map = new HashMap<>();
52+
this.end = false;
53+
}
54+
public HashMap<Character, TrieNode> getMap() {
55+
return map;
56+
}
57+
public boolean isEnd() {
58+
return this.end;
59+
}
60+
}
61+
62+
TrieNode root;
63+
/** Initialize your data structure here. */
64+
public WordDictionary() {
65+
root = new TrieNode();
66+
}
67+
68+
/** Adds a word into the data structure. */
69+
public void addWord(String word) {
70+
char[] arr = word.toCharArray();
71+
TrieNode node = root;
72+
for (char c : arr) {
73+
HashMap<Character, TrieNode> map = node.getMap();
74+
if (!map.containsKey(c)) {
75+
map.put(c, new TrieNode());
76+
}
77+
node = map.get(c);
78+
}
79+
node.end = true;
80+
}
81+
82+
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
83+
public boolean search(String word) {
84+
return searchHelper(root, word, 0);
85+
}
86+
87+
public boolean searchHelper(TrieNode root, String word, int index) {
88+
if (index == word.length()) {
89+
return root.isEnd();
90+
}
91+
TrieNode node = root;
92+
char c = word.charAt(index);
93+
HashMap<Character, TrieNode> map = node.getMap();
94+
if (map.containsKey(c)) {
95+
return searchHelper(map.get(c), word, index + 1);
96+
} else if (c == '.') {
97+
for (Map.Entry<Character, TrieNode> entry : map.entrySet()) {
98+
if (searchHelper(entry.getValue(), word, index + 1)) {
99+
return true;
100+
}
101+
}
102+
return false;
103+
}
104+
return false;
105+
}
106+
}
35107

36108
/*
37109
Build the WordDictionary like a TrieTree.

‎Java/Balanced Binary Tree.java‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
11
M
2+
1519713672
23

34
1. DFS using depth marker: 每个depth都存一下。然后如果有不符合条件的，存为-1.
45
一旦有 <0 或者差值大于1， 就全部返回Integer.MIN_VALUE. Integer.MIN_VALUE比较极端, 确保结果的正确性。

0 commit comments

Comments
 (0)