Skip to content

Commit 05fd580

Browse files
author
liwentian
committed
fd
1 parent 2b297b9 commit 05fd580

13 files changed

Lines changed: 556 additions & 9 deletions

File tree

README.md

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@
44
- [刷题要点总结](https://github.com/dingjikerbo/leetcode/blob/master/doc/Attention.md)
55
- [Facebook面试总结](https://github.com/dingjikerbo/leetcode/blob/master/doc/Facebook.md)
66
- [Bitset技巧](https://github.com/dingjikerbo/leetcode/blob/master/doc/BitSet.md)
7+
- [Map新接口](https://github.com/dingjikerbo/leetcode/blob/master/doc/Map.md)
78

89
<br/><br/><br/><br/>
910

@@ -122,7 +123,7 @@
122123
|130|[Surrounded Regions](https://leetcode.com/problems/surrounded-regions/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/SurroundedRegions.java)|65|
123124
|131|[Palindrome Partitioning](https://leetcode.com/problems/palindrome-partitioning/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/PalindromePartitioning.java)||
124125
|132|[Palindrome Partitioning II](https://leetcode.com/problems/palindrome-partitioning-ii/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/PalindromePartitioningII.java)||
125-
|133|[Clone Graph](https://leetcode.com/problems/clone-graph/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/CloneGraph.java)|70|
126+
|133|[Clone Graph](https://leetcode.com/problems/clone-graph/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/CloneGraph.java)|70|这题不难,多看两遍,BFS方法再做两遍|
126127
|138|[Copy List with Random Pointer](https://leetcode.com/problems/copy-list-with-random-pointer/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/CopyListWithRandomPointer.java)|95|有一个易错点|
127128
|139|[Word Break](https://leetcode.com/problems/word-break/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/WordBreak.java)|80|这个系列题多做几遍|
128129
|140|[Word Break II](https://leetcode.com/problems/word-break-ii/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/WordBreakII.java)|75|
@@ -160,10 +161,10 @@
160161
|203|[Remove Linked List Elements](https://leetcode.com/problems/remove-linked-list-elements/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/RemoveLinkedListElements.java)||
161162
|204|[Count Primes](https://leetcode.com/problems/count-primes/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/CountPrimes.java)|85|
162163
|206|[Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/ReverseLinkedList.java)|90|
163-
|207|[Course Schedule](https://leetcode.com/problems/course-schedule/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/CourseSchedule.java)||
164+
|207|[Course Schedule](https://leetcode.com/problems/course-schedule/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/CourseSchedule.java)|100|典型的拓扑排序|
164165
|208|[Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/Trie.java)|80|#211多留意,trie很典型|
165166
|209|[Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/MinimumSizeSubarraySum.java)|85|
166-
|210|[Course Schedule II](https://leetcode.com/problems/course-schedule-ii/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/CourseScheduleII.java)|
167+
|210|[Course Schedule II](https://leetcode.com/problems/course-schedule-ii/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/CourseScheduleII.java)|95||
167168
|211|[Add and Search Word - Data structure design](https://leetcode.com/problems/add-and-search-word-data-structure-design/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/WordDictionary.java)|85|
168169
|212|[Word Search II](https://leetcode.com/problems/word-search-ii/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/WordSearchII.java)||
169170
|213|[House Robber II](https://leetcode.com/problems/house-robber-ii/)| [Java](https://github.com/dingjikerbo/leetcode/blob/master/solution/src/main/java/com/inuker/solution/HouseRobberII.java)|80|

doc/Attention2.md

Whitespace-only changes.

doc/Google.md

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
Google准备计划
2+
重点刷图,拓扑排序,Union Find
3+
树,二叉树,BIT, Segment Tree,Trie
4+
递归,DFS, BFS
5+
贪心,DP
6+
7+
每天过10道题目,不用每道题都要做

doc/Map.md

Lines changed: 207 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,207 @@
1+
Java 8之Map新增方法
2+
3+
# getOrDefault
4+
5+
```
6+
map.getOrDefault("one", "s");
7+
```
8+
9+
# forEach
10+
11+
```
12+
map.forEach(new BiConsumer<String, String>() {
13+
@Override
14+
public void accept(String key, String value) {
15+
System.out.println(key + ", " + value);
16+
}
17+
});
18+
```
19+
20+
# replace(K key, V newValue)
21+
22+
类似
23+
24+
```
25+
if (map.containsKey(key)) {
26+
return map.put(key, newValue);
27+
} else {
28+
return null;
29+
}
30+
```
31+
32+
33+
# replace(K key, V oldValue, V newValue);
34+
35+
如果key和oldValue都匹配,则替换成newValue。类似:
36+
37+
```
38+
if (map.containsKey(key) && Objects.equals(map.get(key), oldValue)) {
39+
map.put(key, newValue);
40+
return true;
41+
} else {
42+
return false;
43+
}
44+
```
45+
46+
# replaceAll
47+
替换Map中所有Entry的value值,这个值由旧的key和value计算得出
48+
49+
```
50+
map.replaceAll(new BiFunction<String, String, String>() {
51+
@Override
52+
public String apply(String key, String value) {
53+
if (key.equals("two")) {
54+
return value + ".old";
55+
}
56+
return value;
57+
}
58+
});
59+
```
60+
61+
类似如下代码:
62+
63+
```
64+
for (Entry entry : map.entrySet()) {
65+
entry.setValue(function.apply(entry.getKey(), entry.getValue()));
66+
}
67+
```
68+
69+
# putIfAbsent(K key, V value)
70+
71+
如果key不存在,则put,并返回null。如果key存在,则什么也不做,返回key对应的value
72+
73+
```
74+
map.putIfAbsent("four", "charge");
75+
```
76+
77+
# remove(K key, V value)
78+
79+
```
80+
map.remove(key, value);
81+
```
82+
83+
类似:
84+
85+
```
86+
if (map.containsKey(key) && Objects.equals(map.get(key), value)) {
87+
map.remove(key);
88+
return true;
89+
} else {
90+
return false;
91+
}
92+
```
93+
94+
# computeIfAbsent(K key, Function f)
95+
96+
```
97+
String s = map.computeIfAbsent("four", new Function<String, String>() {
98+
@Override
99+
public String apply(String key) {
100+
return key + "@";
101+
}
102+
});
103+
```
104+
105+
类似
106+
107+
```
108+
if (map.get(key) == null) {
109+
V newValue = function.apply(key);
110+
if (newValue != null) {
111+
map.put(key, newValue);
112+
return newValue;
113+
}
114+
} else {
115+
return map.get(key);
116+
}
117+
```
118+
119+
# computeIfPresent(K key, BiFunction f)
120+
121+
```
122+
map.computeIfPresent("one", new BiFunction<String, String, String>() {
123+
@Override
124+
public String apply(String key, String value) {
125+
return null;
126+
}
127+
});
128+
```
129+
130+
类似:
131+
132+
```
133+
if (map.get(key) != null) {
134+
V oldValue = map.get(key);
135+
V newValue = function.apply(key, oldValue);
136+
if (newValue != null) {
137+
map.put(key, newValue);
138+
} else {
139+
map.remove(key);
140+
}
141+
return newValue;
142+
} else {
143+
return null;
144+
}
145+
```
146+
147+
# compute(K key, BiFunction f)
148+
149+
```
150+
map.compute(key, new BiFunction<String, String, String>() {
151+
@Override
152+
public String apply(String key, String value) {
153+
return key + "@" + value;
154+
}
155+
});
156+
```
157+
158+
类似:
159+
160+
```
161+
V oldValue = map.get(key);
162+
V newValue = function.apply(key, value);
163+
164+
if (oldValue != null) {
165+
if (newValue != null) {
166+
map.put(key, newValue);
167+
} else {
168+
map.remove(key);
169+
}
170+
} else {
171+
if (newValue != null) {
172+
map.put(key, newValue);
173+
}
174+
}
175+
return newValue;
176+
```
177+
178+
# merge(K key, V value, BiFunction f)
179+
180+
apply中第一个参数是oldValue,第二个参数是merge传入的第二个参数
181+
182+
```
183+
map.merge(key, value, new BiFunction<String, String, String>() {
184+
@Override
185+
public String apply(String oldValue, String value) {
186+
return oldValue + "@" + value;
187+
}
188+
});
189+
```
190+
191+
类似:
192+
193+
```
194+
if (value == null) {
195+
throw new NullPointerException();
196+
}
197+
198+
V oldValue = map.get(key);
199+
V newValue = (oldValue == null) ? value : function.apply(oldValue, value);
200+
201+
if (newValue == null) {
202+
map.remove(key);
203+
} else {
204+
map.put(key, newValue);
205+
return newValue;
206+
}
207+
```

google/RECORDS.md

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
2017-9-2
2+
329. Longest Increasing Path in a Matrix
3+
133. Clone Graph
4+
269. Alien Dictionary
5+
207. Course Schedule
6+
210. Course Schedule II
Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
package com.leetcode.google;
2+
3+
import java.util.Arrays;
4+
import java.util.HashMap;
5+
import java.util.HashSet;
6+
import java.util.LinkedList;
7+
import java.util.Queue;
8+
import java.util.Set;
9+
10+
/**
11+
* Created by liwentian on 2017/9/2.
12+
*/
13+
14+
public class AlienDictionary {
15+
16+
public String alienOrder(String[] words) {
17+
HashMap<Character, Set<Character>> map = new HashMap<>();
18+
19+
int[] indegrees = new int[26];
20+
Arrays.fill(indegrees, -1);
21+
22+
int count = 0;
23+
for (String word : words) {
24+
for (char c : word.toCharArray()) {
25+
if (indegrees[c - 'a'] != 0) {
26+
indegrees[c - 'a'] = 0;
27+
count++;
28+
}
29+
}
30+
}
31+
32+
for (int i = 0; i < words.length - 1; i++) {
33+
String prev = words[i], next = words[i + 1];
34+
35+
for (int j = 0; j < prev.length() && j < next.length(); j++) {
36+
char c1 = prev.charAt(j), c2 = next.charAt(j);
37+
38+
if (c1 != c2) {
39+
Set<Character> set = map.get(c1);
40+
if (set == null) {
41+
set = new HashSet<>();
42+
map.put(c1, set);
43+
}
44+
if (set.add(c2)) {
45+
indegrees[c2 - 'a']++;
46+
}
47+
break;
48+
} else {
49+
if (j + 1 < prev.length() && j + 1 >= next.length()) {
50+
return "";
51+
}
52+
}
53+
}
54+
}
55+
56+
Queue<Character> queue = new LinkedList<>();
57+
for (char c = 'a'; c <= 'z'; c++) {
58+
if (indegrees[c - 'a'] == 0) {
59+
queue.add(c);
60+
}
61+
}
62+
63+
StringBuilder sb = new StringBuilder();
64+
65+
while (!queue.isEmpty()) {
66+
char c = queue.poll();
67+
sb.append(c);
68+
69+
Set<Character> set = map.get(c);
70+
if (set != null) {
71+
for (char cc : set) {
72+
if (--indegrees[cc - 'a'] == 0) {
73+
queue.add(cc);
74+
}
75+
}
76+
}
77+
}
78+
79+
if (sb.length() != count) {
80+
return "";
81+
}
82+
83+
return sb.toString();
84+
}
85+
}

0 commit comments

Comments
 (0)