HelloHello
1. ZigZag conversion: 8
66. Plus one 9
67. Add Binary 11
Tag I -- -- Two Pointer 14
27. Remove Element 14
26. Remove Duplicates in Sorted array 15
283. Move Zeroes – Two pointer / Array 17
349. Intersection of Two Arrays – Two Pointer 18
350. Intersection of Two Arrays II -- -- Hash Table / Two Pointer 20
344. Reverse String -- -- Two Pointer / String 22
28. Implement strStr() -- -- Two Pointer / String 经典 23
125. Valid Palindrome -- -- Two Pointer / String 26
234. Palindrome Linked List. -- -- Two Pointer / Linked List 27
88. Merge Sorted Array -- -- Two Pointer / Array 28
141. Linked List Cycle – -- Linked List / Two Pointers 31
142. Linked List Cycle II -- -- Linked List / Two Pointers 经典题目 33
345. Reverse Vowels of a String -- -- String / Two Pointers 36
19. Remove Nth Node from End of List --- Two Pointers / Linked List 经典 39
Tag II -- -- Linked List 41
各种关系data structure很重要 42
237. Delete Node in a Linked List -- -- Linked List 43
203. Remove Linked List Elements 44
83. Remove Duplicates from Sorted List 45
82. Remove Duplicates from Sorted List II -- 【M】必背dummy node 46
206. Reverse Linked List 经典 47
92. Reverse Linked List II -- 【M】经典 48
21. Merge Two Sorted Lists -- dummy node / Amazon LinkedIn Apple Microsoft 49
86. Partition List --【M】 51
160. Intersection of Two Linked List 53
24. Swap Nodes in Pairs 54
Tag III -- -- Sort 56
242. Valid Anagram -- -- Counting Sort / Hash Table 经典但是没懂。 56
75. 【M】Sort Colors -- -- Counting Sort / Two Pointers / Array 一周之内最好每天做一遍，三指针太牛了 58
148. 【M】Sort List 经典重要 快排 不懂 60
252. Meeting Rooms --【M】FaceBook / Sort 62
147. Insertion Sort List --【M】 63
179. Largest Number -- 【M】Works Apllications 64
274. H-Index --【M】Bloomberg Google Facebook / Sort Hash Table 65
280. Wiggle Sort --【M】Google / Array / Sort 67
324. Wiggle Sort II --【M】Google 68
Tag IV. Tree 68
101. Symmetric Tree -- DFS / BFS / Tree 71
100. Same Tree – Tree / DFS 73
226. Invert Binary Tree – Tree 74
257. Binary Tree Path – Tree / DFS 77
104. Maximum of Depth of Binary Tree – Tree / DFS Depth-First Search 78
递进一个题：Lintcode 改变 root leave 79
递进 Lintcode: Binary Tree Maximum Path Sum II root any node/D&C 80
递进 124. Binary Tree Maximum Path Sum 【H】any node any node / D&C经典 80
111. Minimum of Binary Tree – Tree / DFS / BFS 83
110. Balanced Binary Tree – Tree / DFS / D&C 85
102. Binary Tree Level Order Traversal – Tree / BFS必背 86
107. Binary Tree Level Order Traversal II 88
103. Binary Tree Zigzag Level Order Traversal – 【M】 88
235. Lowest Common Ancestor of a Binary Search Tree 89
236. Lowest Common Ancestor of a Binary Tree 【M】多体会 91
404. Sum of Left Leaves -- Tree 92
112. Path Sum – 数的求和 93
113. Path Sum II -- 【M】DFS 95
144. Binary Tree Preorder Traversal – Stack / Tree/ 【M】 96
94. Binary Tree Inorder Traversal – Tree/ Stack 【M】经典 必背 97
145. Binary Tree Postorder Traversal -- 【H】 99
270. Closest Binary Search Tree Value 【E】 99
298. Binary Tree Longest Consecutive Sequence -- 【M】 101
Tag V ---- Divide and Conquer 101
169. Majority Element -- Adobe / Zenefits / DC / Array / Bit manipulation 101
74. Search a 2D Matrix -- 【M】Binary Search / Array 103
240. Search a 2D Matrix II -- 【M】Amazon Google Apple / DC / Binary Search 105
241. Different Ways to Add Parentheses --【M】DC 105
4. Median of Two Sorted Arrays --【H】Google Zenefits Microsoft Apple Yahoo Dropbox Adobe / Binary Search / Divide and Conquer不理解 108
Tag V ---- Heap 110
215. Kth Largest Element in an Array --【M】Facebook Amazon Microsoft Apple Bloomberg Pocket Gems / DC / Heap 经典不太明白 111
263. Ugly Number -- Math 113
264. Ugly Number II -- 【M】DP / Math 114
313. Super Ugly Number --【M】Google / Math / Heap 不太明白 115
23. Merge k Sorted Lists --【H】LinkedIn Google Uber Airbnb Facebook Twitter Amazon Microsoft / DC / Linked List / Heap 经典 117
373. Find K Pairs with Smallest Sums --【M】Google / Uber 经典 118
378. Kth Smallest Element in a Sorted Matrix --【M】Google Twitter / Binary Search / Heap 120
355. Design Twitter --【M】Amazon / Twitter / HashMap / Heap/ Design 121
253. Meeting Rooms II -- 【M】 Google Snapchat Facebook / Heap / Greedy / Sort 124
Tag V ---- Binary Search 125
Lintcode. First position of Target -- BS-Index 125
Lintcode. Last position of Target -- BS-Index 126
74. Search a 2D Matrix – BS-Index / Array 127
35. Search Insert Position – BS-Index / Array 128
Lintcode. Search in a Big Sorted Array – BS-Idex / O(log k) 129
153. Find Minimum in Rotated Sorted Array -- 【M】Good / BS-Index 131
33. Search in Rotated Sorted Array -- 【H】/ BS-Index 132
69. Sqrt(x) -- 【M】/ BS-Result 133
278. First Bad Version – BS/Result 134
Lintcode. Wood Cut – BS/Result 【M】经典 135
162. Find Peak Element – BS/Result / Array 【M】 136
34. Search for a Range -- 【M】 137
98. Validate Binary Search Tree – inorder延伸【M】 139
173. Binary Search Tree Iterator --【M】常见/ inorder/stack 140
285. Inorder Successor in Binary Search Tree -- 【M】 141
Lintcode 没做的 142
Tag VI. Array 142
56. Merge Intervals – 【H】/ Array/ Sort 142
200. Number of Islands -- 【M】DFS+BFS+Recursive 143
228. Summary Ranges --【M】 147
163. Missing Ranges --【M】 148
Tag VII. Dynamic Programming 150
Sub Tag -- 坐标 152
120. Triangle --【M】有问题 动规求最小值 152
64. Minimum Path Sum -- 【M】动规求最小值 153
62. Unique Paths -- 【M】动规统计方案个数 154
63. Unique Paths II -- 【M】动规统计方案个数 155
70. Climbing Stairs 156
Lintcode -- Jump Game / Greedy/ DP -【M】 158
Lintcode -- Jump Game II / Greedy/ DP -【M】 160
300. Longest Increasing Subsequence --【M】经典 LIS问题 161
221. Maximal Square -- 【M】滚动数组 坐标型DP/ Apple/Airbnb/Facebook 161
85. Maximal Rectangle --【H】Facebook / Hash table / DP / Stack /Array未完成 163
Sub Tag -- 划分类(单序列)： 163
53. Maximum Subarray -【M】DP/Devide and Conquer/Array 经典模板 163
152. Maximum Product Subarray -- 【M】DP / Linkedin 多思考 164
121. Best Time to Buy and Sell Stock -- DP 交易一次 166
122. Best Time to Buy and Sell Stock II --Greedy / Array【M】无限次 167
123. Best Time to Buy and Sell Stock III -- DP / Array 【H】交易最多两次 不是很明白 167
188. Best Time to Buy and Sell Stock IV -- DP【H】根本不明白了 169
198. House Robber -- DP/ Linkedin Airbnb/ 169
213. House Robber II -- 【M】/ Microsoft 170
276. Paint Fence -- Google / 坐标DP 171
256. Paint House --【M】坐标DP / Linkedin 172
Sub Tag -- 单序列： 173
132. Palindrome Partitioning II --【H】DP单序列 173
279. Perfect Squares --【M】/DP/ BFS 答案也没有看懂 175
139. Word Break--【M】/DP 不明白 175
303. Range Sum Query - Immutable -- DP / Palantir 176
32. Longest Valid Parentheses -- 【H】 176
91. Decode Ways --【M】Microsoft Uber Facebook / DP String 176
151. Reverse Words in a String 177
Tag VIIII. Stack 177
20. Valid Parentheses -- Google Airbnb Facebook Twitter Zenefits Amazon Microsoft Bloomberg / Stack 178
155. Min Stack -- /design 181
232. Implement Queue using Stacks -- Microsoft Bloomberg / Stack / Design 182
225. Implement Stack using Queues -- Bloomberg / Stack / Design 183
402. Remove K Digits -- 【M】Google Snapchat / Stack Greedy 184
71. Simplify Path --【M】Microsoft Facebook / Stack String 185
255. Verify Preorder Sequence in Binary Search Tree --【M】Zenefits / Tree Stack 186
331. Verify Preorder Serialization of a Binary Tree -- 【M】 188
150. Evaluate Reverse Polish Notation -- 【M】Linkedin / Stack 188
341. Flatten Nested List Iterator --【M】Google Facebood Twitter / Stack Design 经典 189
394. Decode String -- 【M】Google / Stack DFS 经典 190
385. Mini Parser -- 【M】Airbnb / Stack String 难，绕 191
Tag X. BackTracking 193
Sub Tag -- 排列类Permutation 194
46. Permutations --【M】经典 / Linkedin / Microsoft 194
47. Permutations II -- 【M】/ Linkedin / Microsoft 经典必背模板 195
31. Next Permutation --【M】/ Google / Array / Math不是backtracking 196
60. Permutation Sequence -- 【M】Backtracking / Math / Twitter 198
131. Palindrome Partitioning -- 【M】Bloomberg / Backtracking 199
267. Palindrome Permutation II -- 【M】Backtracking 经典常练习 200
Sub Tag -- 组合类Combination 202
77. Combinations --【M】Backtracking 203
39. Combination Sum -- 【M】/ Backtracking / Snapchat / Uber 204
40. Combination Sum II --【M】Backtracking / Snapchat 205
216. Combination Sum III --【M】Backtracking / Array 207
377. Combination Sum IV -- 【M】DP / Google / Snapchat / Facebook多体会 208
17. Letter Combinations of a Phone Number --【M】Amazon / Dropbox / Google / Uber / Facebook多练习 209
254. Factor Combinations --【M】Linkedin / Uber 多练习 210
Sub Tag -- Subset 全子集 211
78. Subsets –【M】必背Array / Backtracking / Bit Manipulation / Amazon / Uber / Facebook 211
90. Subsets II --【M】Backtracking / Facebook 212
Sub Tag -- 其他应用 213
22. Generate Parentheses --【M】Backtracking / Google / Uber / Zenefits 多练习 213
93. Restore IP Addresses -- 【M】Backtracking / String多练习 214
89. Gray Code -- 【M】Amazon / Backtracking 多练习 216
79. Word Search -- 【M】Microsoft Bloomberg Facebook / Backtracking / Array 217
357. Count Numbers with Unique Digits --【M】Google / DP / Math 218
401. Binary Watch -- Google / Backtracking / Bit Manipulation 219
320. Generalized Abbreviation --【M】Google / Backtracking / Bit manipulation 不太明白 多练习 220
294. Flip Game II --【M】Google / Backtracking 221
Tag VIII. Hash Table 223
1. Two Sum 223
136. Single Number -- 【E】Hash Table / Bit / Palantir / Airbnb 225
137. Single Number II -- 【M】Bit 226
217. Contains Duplicate -- Palantir Airbnb Yahoo / Array Hash Table 227
219. Contains Duplicate II -- Palantir / Airbnb 228
36. Valid Sudoku -- Snapchat / Uber / Apple 不明白 228
438. Find All Anagrams in a String -- Amazon 不明白 / Slide Window 229
202. Happy Number -- Uber Airbnb Twitter / Hash Table / Math 经典 231
409. Longest Palindrome -- Google 232
447. Number of Boomerangs -- Google 233
389. Find the Difference -- Google 235
290. Word Pattern -- Dropbox / Uber 经典 236
205. Isomorphic Strings -- LinkedIn 238
204. Count Primes -- Amazon / Microsoft 巧妙 239
463. Island Perimeter -- Google 240
170. Two Sum III - Data structure design -- LinkedIn / Hash Table / Design 242
246. Strobogrammatic Number -- Google / Math 242
249. Group Shifted Strings -- Google / Uber / String / Hash Table 多练习不明白 244
3. Longest Substring Without Repeating Characters -- 【M】Amazon Adobe Bloomberg Yelp / Hash Table / Two Pointer / String 经典 245
187. Repeated DNA Sequences -- 【M】LinkedIn / Hash Table / Bit 246
18. 4Sum -- 【M】Array / Two pointers / Hash Table 不明白 248
15. 3Sum -- 【M】Amazon Microsoft Bloomberg Facebook Adobe Works Applications / Two Pointer / Array 249
347. Top K Frequent Elements -- 【M】Pocket Gems / Yelp / Hash Table / Heap 250
311. Sparse Matrix Multiplication -- 【M】LinkedIn / Facebook 252
49. Group Anagrams -- 【M】Amazon Bloomberg Uber Facebook Yelp 253
166. Fraction to Recurring Decimal -- 【M】Google 253
451. Sort Characters By Frequency --【M】Amazon / Google / Heap / Hash Table 255
243. Shortest Word Distance -- LinkedIn / Array 257
244. Shortest Word Distance II --【M】LinkedIn / Hash Table / Design 258
325. Maximum Size Subarray Sum Equals k --【M】Palantir / Facebook 经典 259
356. Line Reflection -- 【M】Google / Hash Table / Math 260
288. Unique Word Abbreviation 261
266. Palindrome Permutation -- Google / Uber / Bloomberg / Hash Table 262
Tag XI. String 264
38. Count and Say -- Facebook / String 264
408. Valid Word Abbreviation -- Google 265
434. Number of Segments in a String 266
459. Repeated Substring Pattern -- Amazon / Google / KMP字符串匹配 267
293. Flip Game -- Google / String 269
14. Longest Common Prefix -- Yelp / 字符串匹配 270
157. Read N Characters Given Read4 -- Facebook 不明白 271
58. Length of Last Word 272
13. Roman to Integer -- Microsoft Bloomberg Uber Facebook Yahoo 272
12. Integer to Roman -- 【M】Twitter / 罗马数字 274
383. Ransom Note -- Apple 274
151. Reverse Words in a String -- Microsoft Snapchat Apple Bloomberg Yelp 276
186. Reverse Words in a String II -- 【M】Amazon Uber Microsoft 经典 276
8. String to Integer (atoi) -- 【M】 Amazon Microsoft Bloomberg Uber 经典 277
227. Basic Calculator II -- 【M】Airbnb 经典多练习 278
5. Longest Palindromic Substring -- 【M】Amazon Bloomberg Microsoft 面经必考经典多练习 280
6. ZigZag Conversion -- 【M】 281
271. Encode and Decode Strings -- 【M】 Google 281
Tag. Union Find 282
305. Number of Islands II -- 【H】 Google 不太明白 283
130. Surrounded Regions -- 【M】 285
323. Number of Connected Components in an Undirected Graph -- 【M】Google / Twitter 287
261. Graph Valid Tree --【M】Google / Facebook / Zenefits / DFS / BFS / Gragh / Union Find 289
128. Longest Consecutive Sequence --【H】Google / FaceBook 291
Tag XII. Java / Algorithm foundation 292
Linked List 292
Stack 292
Queue 293
StringBuilder 293
Character 293
String 294
Priority Queue 295
switch in java 295
Iterate a map 296
HashSet methods 296
HashMap methods 296
ArrayList Methods 297
位操作 297
i++ ++i difference 298
关于java 8 lambda 以及Method references 298
正则表达式 298
普通字符 298
非打印字符 298
特殊字符 299
限定符 300
各种排序以及复杂度Java 300
Bubble Sort：O(n ^ 2) 301
Quick Sort : O(n log n): 301
Insertion Sort: O(N ^ 2): 301
Selection Sort: O(N ^ 2) 302
Merge Sort: O(N log N) 302
Heap Sort: O(N log N) 303
代码： 303
Leetcode -- Easy：
有几个同主题总结：
回文：
缩写：
买股票：
括号：
1. ZigZag conversion:
博客答案：
http://www.cnblogs.com/grandyang/p/4128268.html
九章算法：
http://www.jiuzhang.com/solutions/zigzag-conversion/
（1）特殊情况：不形成之字形直接输出；
（2）首先：需要一个新的数组来存储新的之字形字符串。其中count算是计数器，作为新数组的index；
然后找规律：
- 输出第一行中间相差2n-2(step)，如果不考虑中间插入的之字形字符，第二行两黑色字符也相差2n-2，由此，输出的新数组中没有中间之字形的字符对应原来的index就是j+step, 此时输出就是s.charAt(j) .
- 再考虑中间有之字形(Z)的情况：Z 和之前的同行的黑色字中间有interval个数字，所以最后返回的Z的位置就是前一个字的位置j 加上interval。
- 逻辑条件：什么情况才有Z的出现呢？也就是中间的interval小于step，也就是往下走了一个之字形的时候。这个条件要加在第二个for循环里面，因为如果没有之字形的话，直接输出相差step的黑色数了。
#### 这个不是Leetcode的
Find first duplicate character in a string in Java
http://www.java-fries.com/2015/01/find-first-duplicate-character-in-a-string/
#
2. Roman to Integer:
讲解 C++代码：http://www.cnblogs.com/grandyang/p/4120857.html
66. Plus one
https://leetcode.com/problems/plus-one/
public class PlusOne {
public static int[] plusOne(int[] digits) {
int len = digits.length;
for (int i = len -1; i > 0; i--) {
if (digits[i] < 9) {
digits[i] += 1;
return digits;
}
digits[i] = 0;
}
int[] newDigits = new int[len + 1];
newDigits[0] = 1;
return newDigits;
}
public static void main(String[] args) {
int[] digits = {9,9,9,9};
int[] res = plusOne(digits);
System.out.println(Arrays.toString(res));
// To print String there are two ways. For loop and Arrays.toString.
}
}
// 九章算法里的答案，把 +1 的情况普遍出来。
public class PlusOne {
public static int[] plusOne(int[] digits) {
int add = 1;
int len = digits.length;
int sum = 0;
for (int i = len - 1; i >= 0 && add > 0; i--) {
sum = digits[i] + add;
digits[i] = sum % 10;
add = sum / 10;
}
if (add == 0)
return digits;
int[] newDigits = new int[len + 1];
newDigits[0] = 1;
//?????? there is no difference use or not use.
// for (int i = 1; i < newDigits.length; i++) {
// newDigits[i] = digits[i-1];
// }
return newDigits;
}
public static void main(String[] args) {
int[] digits = {6,9,9,9};
int[] res = plusOne(digits);
System.out.println(Arrays.toString(res));
}
}
第二遍复习时：Correct when it runs the first time.
public class Solution {
public int[] plusOne(int[] digits) {
int add = 1;
int sum = 0;
int len = digits.length;
for (int i = len -1; i >= 0 && add > 0; i--) {
sum = digits[i] + add;
digits[i] = sum % 10;
add = sum / 10;
if (add == 0) {
return digits;
}
}
int[] newDigits = new int[len + 1];
newDigits[0] = add;
for (int i = 1; i < len + 1; i++) {
newDigits[i] = digits[i-1];
}
return newDigits;
}
}
第四遍复习时：0ms 40% 没有用sum / 10 sum% 10 但是用了更好。
public class Solution {
public int[] plusOne(int[] digits) {
int plus = 1;
int last = digits.length - 1;
for (int i = last; i >= 0; i--) {
if (digits[i] == 9 && plus == 1) {
digits[i] = 0;
plus = 1;
continue;
}
digits[i] = digits[i] + plus;
plus = 0;
}
if (digits[0] == 0) {
int[] newOne = new int[digits.length + 1];
newOne[0] = 1;
for (int i = 1; i < digits.length + 1; i++) {
newOne[i] = digits[i-1];
}
return newOne;
}
else
return digits;
}
}
67. Add Binary
Solution： http://codeganker.blogspot.com/2014/02/add-binary-leetcode.html
http://www.jiuzhang.com/solutions/add-binary/
My first version: -- Wrong
public class Solution {
public String addBinary(String a, String b) {
String[] aArray = new String[] {a};
String[] bArray = new String[] {b};
int add = 1;
int sum = 0;
int aLen = aArray.length;
int bLen = bArray.length;
String[] resArray = new String[aLen + 2];
String newString = null;
for (int i = aLen - 1; i >= 0 && add > 0; i--) {
for (int j = bLen - 1; j >= 0; j--) {
sum = Integer.parseInt(aArray[i]) + Integer.parseInt(bArray[j]);
resArray[i + 2] = Integer.toString(sum % 2);
add = sum / 2;
}
}
if (add == 0) {
StringBuilder strBuilder = new StringBuilder();
for (int i = 0; i < resArray.length; i++) {
strBuilder.append(resArray[i]);
}
newString = strBuilder.toString();
return newString;
}
return newString;
}
}
九章：
public class Solution {
public String addBinary(String a, String b) {
if (a == null || a.length() == 0) // 首先空值判断
return b;
if (b == null || b.length() == 0)
return a;
if (a.length() < b.length()) { // 对于长度不相等的解决办法之一就是交换
String tmp = a;
a = b;
b = tmp;
}
int carrier = 0; // 刚开始的进位是0
int pa = a.length() - 1;
int pb = b.length() - 1;
String res = ""; // 存结果的String初始是空
while (pb >= 0) {
// 这里不明白
int sum = (int)(a.charAt(pa) - '0') + (int)(b.charAt(pb) - '0') + carrier;
res = String.valueOf(sum % 2) + res;
carrier = sum / 2;
pa--;
pb--;
}
while (pa >= 0) {
int sum = (int)(a.charAt(pa) - '0') + carrier;
res = String.valueOf(sum % 2) + res;
carrier = sum / 2;
pa--;
}
if (carrier == 1) {
res = "1" + res;
}
return res;
}
}
**总结：
核心有： 开始一定要空值的判断。如果某一String 是空的话，一定要直接返回另一个
考虑 a b 长短的问题 ====》》交换
String转换成int的问题。=====》》 String.charAt(int index) 为什么 - ‘0’
Int 再转换成Strign =====》》》 String.valueOf() 本身有非空判断
最后比较容易忘：如果进位是1的话，判断一下，加到String的第一位。