Skip to content

Commit c7f3a60

Browse files
awangdevawangdev
committed
update
1 parent 19c9630 commit c7f3a60

72 files changed

Lines changed: 3560 additions & 3835 deletions

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎Java/Accounts Merge.java‎

Lines changed: 76 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,14 @@
11
M
2-
1531813218
3-
tags: DFS, Union Find, Hash Table
2+
1532588768
3+
tags: DFS, Union Find, Hash Table, Hash Table
44

55
给一串account in format `[[name, email1, email2, email3], [name2, email,..]]`.
66

77
要求把所有account merge起来 (可能多个record记录了同一个人, by common email)
88

9-
#### Union Find
10-
- TODO
119

10+
#### Union Find
11+
- 构建 Map<email, email parent>, 然后再反向整合: parent -> list of email
1212

1313
#### Hash Table solution, passed but very slow
1414
- Definitely need iterate over accounts: merge them by email.
@@ -105,4 +105,76 @@ public List<List<String>> accountsMerge(List<List<String>> accounts) {
105105
return rst;
106106
}
107107
}
108+
109+
110+
/*
111+
Union Find
112+
Approach similar to LintCode(Find the weak connected component in directed graph)
113+
UnionFind: Map<currEmail, parentEmail>
114+
1. Group account into union. ( don't forget to preserve email -> name mapping)
115+
2. Group parent -> children
116+
3. output
117+
*/
118+
class Solution {
119+
Map<String, String> accountMap = new HashMap<>();
120+
Map<String, String> parentMap = new HashMap<>();
121+
122+
public List<List<String>> accountsMerge(List<List<String>> accounts) {
123+
List<List<String>> rst = new ArrayList<>();
124+
if (validate(accounts)) return rst;
125+
126+
buildUnionFind(accounts);
127+
128+
for (List<String> account : accounts) {
129+
for (int i = 1; i < account.size() - 1; i++) {
130+
union(account.get(i), account.get(i + 1));
131+
}
132+
}
133+
134+
Map<String, List<String>> result = new HashMap<>();
135+
for (String email : parentMap.keySet()) {
136+
String parent = find(email);
137+
result.putIfAbsent(parent, new ArrayList<>());
138+
result.get(parent).add(email);
139+
}
140+
141+
for (List<String> list: result.values()) {
142+
Collections.sort(list);
143+
list.add(0, accountMap.get(list.get(0)));
144+
rst.add(list);
145+
}
146+
147+
return rst;
148+
}
149+
150+
private boolean validate(List<List<String>> accounts) {
151+
return accounts == null || accounts.size() == 0 || accounts.get(0) == null || accounts.get(0).size() == 0;
152+
}
153+
154+
private void buildUnionFind(List<List<String>> accounts) {
155+
for (List<String> account : accounts) {
156+
String name = account.get(0);
157+
for (int i = 1; i < account.size(); i++) {
158+
accountMap.put(account.get(i), name); // email -> name mapping
159+
parentMap.put(account.get(i), account.get(i)); // union parent map
160+
}
161+
}
162+
}
163+
164+
private String find(String email) {
165+
String parent = parentMap.get(email);
166+
if (parent.equals(parentMap.get(parent))) {
167+
return parent;
168+
}
169+
return find(parent);
170+
}
171+
172+
private void union(String a, String b) {
173+
String parentA = find(a);
174+
String parentB = find(b);
175+
if (!parentA.equals(parentB)) {
176+
parentMap.put(parentA, parentB);
177+
}
178+
}
179+
}
108180
```

‎Java/Binary Search Tree Iterator.java‎

Lines changed: 28 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -2,30 +2,37 @@
22
1518626557
33
tags: Stack, Tree, Design, BST
44

5-
Build iterator to print ascending elemnts of BST. Inorder traversal BST. Need to maintain O(1) time, O(h) space.
6-
75
画一下, BST in order traversal. 用stack记录最小值, 放在top. O(h) space.
86
每次消耗TreeNode, 都看看rightNode(其实就是下一个最小的candidate), 并且一条龙stack叠上rightNode所有的left子孙.
97

10-
#### Stack
11-
- 用O(h)空间的做法：
12-
- 理解binary search tree inorder traversal的规律：
13-
- 先找left.left.left ....left 到底，这里是加进stack; 然后考虑parent,然后再right.
14-
15-
#### Details 例如这题:
16-
- stack里面top，也就是tree最左下角的node先考虑,取名rst.
17-
- 其实这个rst拿出来以后, 它也同时是最底层left null的parent，算考虑过了最底层的parent。
18-
- 最后就考虑最底层的parent.right, 也就是rst.right.
19-
- 注意: next()其实有个while loop, 很可能是O(h).题目要求average O(1),所以也是okay的.
20-
21-
22-
#### 用O(1)空间的做法: 不存stack, 时刻update current为最小值。
23-
- 找下一个最小值,如果current有right child: 和用stack时的iteration类似,那么再找一遍current.right的left-most child,就是最小值了。
24-
- 如果current没有right child: 那么就要找current node的右上parent, search in BinarySearchTree from root.
25-
- 注意:
26-
- 一定要确保找到的parent满足parent.left == current.
27-
- 反而言之，如果current是parent的 right child, 那么下一轮就会重新process parent。
28-
- 但是有错:binary search tree里面parent是小于right child的，也就是在之前一步肯定visit过，如此便会死循环。
8+
Previous Notes:
9+
用O(h)空间的做法：
10+
11+
理解binary search tree inorder traversal的规律：
12+
先找left.left.left ....left 到底，这里是加进stack.
13+
然后考虑parent,然后再right.
14+
15+
例如这题：
16+
stack里面top，也就是tree最左下角的node先考虑,取名rst.
17+
其实这个rst拿出来以后, 它也同时是最底层left null的parent，算考虑过了最底层的parent。
18+
最后就考虑最底层的parent.right, 也就是rst.right.
19+
20+
注意:
21+
next()其实有个while loop, 很可能是O(h).题目要求average O(1),所以也是okay的.
22+
23+
24+
用O(1)空间的做法：不存stack, 时刻update current为最小值。
25+
26+
找下一个最小值,如果current有right child：
27+
和用stack时的iteration类似,那么再找一遍current.right的left-most child,就是最小值了。
28+
29+
如果current没有right child:
30+
那么就要找current node的右上parent, search in BinarySearchTree from root.
31+
32+
注意：
33+
一定要确保找到的parent满足parent.left == current.
34+
反而言之，如果current是parent的 right child, 那么下一轮就会重新process parent。
35+
但是有错:binary search tree里面parent是小于right child的，也就是在之前一步肯定visit过，如此便会死循环。
2936

3037

3138
```

‎Java/Clone Graph.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
M
22
1519966780
3-
tags: DFS, BFS, Graph, Hash Table
3+
tags: DFS, BFS, Graph
44

55
给一个graph node, 每个node有list of neighbors. 复制整个graph, return new head node.
66

‎Java/Contiguous Array.java‎

Lines changed: 1 addition & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -2,15 +2,7 @@
22
1531902072
33
tags: Hash Table
44

5-
find the maximum length of a contiguous subarray with `equal number of 0 and 1`
6-
7-
#### Hash Table
8-
- Trick: equal number of 0 and 1, also can be reflected as equal number of -1, 1.
9-
- 有正负数, 就可以用 `map<preSum, index>` 这一招, 来找到之前存在过的preSum 的index, 来track max length
10-
- Template:
11-
- 1. init preSum = 0, `map.put(0, -1)`
12-
- 2. maintain `max = Math.max(max, i - map.get(preSum))`
13-
- 3. keep updating map with new presum `map.put(preSum, i)`
5+
TODO: how aout without chaning the input nums?
146

157
```
168
/*

‎Java/Continuous Subarray Sum.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
M
22
1522910259
3-
tags: Math, DP, Coordinate DP, Subarray, PreSum
3+
tags: Math, DP, Coordinate DP, Subarray
44

55
给一个非负数的数列和数字k(可正负, 可为0). 找到连续子序列(长度超过2), 使得这个subarray的sum 是 k的倍数. 问: 是否可能?
66

‎Java/Decode Ways II.java‎

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -26,11 +26,9 @@
2626
'B' -> 2
2727
...
2828
'Z' -> 26
29-
Beyond that, now the encoded string can also contain the character '*',
30-
which can be treated as one of the numbers from 1 to 9.
29+
Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.
3130
32-
Given the encoded message containing digits and the character '*',
33-
return the total number of ways to decode it.
31+
Given the encoded message containing digits and the character '*', return the total number of ways to decode it.
3432
3533
Also, since the answer may be very large, you should return the output mod 109 + 7.
3634

‎Java/Encode and Decode TinyURL.java‎

Lines changed: 2 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -7,12 +7,9 @@
77

88
```
99
/*
10-
TinyURL is a URL shortening service where you enter a URL such as
11-
https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.
10+
TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.
1211
13-
Design the encode and decode methods for the TinyURL service.
14-
There is no restriction on how your encode/decode algorithm should work.
15-
You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.
12+
Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.
1613
*/
1714

1815
/*
@@ -35,22 +32,6 @@ public String decode(String shortUrl) {
3532
}
3633
}
3734

38-
// Use hashcode, and store integer key
39-
public class Codec {
40-
final String PREFIX = "http://tinyurl.com/";
41-
final Map<Integer, String> map = new HashMap<>();
42-
// Encodes a URL to a shortened URL.
43-
public String encode(String longUrl) {
44-
map.put(longUrl.hashCode(), longUrl);
45-
return PREFIX + longUrl.hashCode();
46-
}
47-
48-
// Decodes a shortened URL to its original URL.
49-
public String decode(String shortUrl) {
50-
return map.get(Integer.parseInt(shortUrl.replace(PREFIX, "")));
51-
}
52-
}
53-
5435
// Your Codec object will be instantiated and called as such:
5536
// Codec codec = new Codec();
5637
// codec.decode(codec.encode(url));

‎Java/Excel Sheet Column Title.java‎

Lines changed: 0 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -29,29 +29,6 @@
2929
Thoughts:
3030
26 bits => num / 26 = 1 => 'A' on that digit
3131
*/
32-
// insert
33-
class Solution {
34-
public String convertToTitle(int n) {
35-
if (n <= 0) {
36-
return null;
37-
}
38-
39-
StringBuilder sb = new StringBuilder();
40-
while (n > 0) {
41-
int remain = n % 26;
42-
n = n / 26;
43-
if (remain == 0) {
44-
sb.insert(0, "Z");
45-
n--;
46-
} else {
47-
sb.insert(0, (char)('A' + remain - 1));
48-
}
49-
}
50-
return sb.toString();
51-
}
52-
}
53-
54-
// append
5532
class Solution {
5633
public String convertToTitle(int n) {
5734
if (n <= 0) {

0 commit comments

Comments
 (0)