Leetcode
1. ZigZag conversion: 4
66. Plus one 5
67. Add Binary 7
1. Two Sum 9
Tag I -- -- Two Pointer 12
27. Remove Element 12
26. Remove Duplicates in Sorted array 13
283. Move Zeroes – Two pointer / Array 15
349. Intersection of Two Arrays – Two Pointer 16
350. Intersection of Two Arrays II -- -- Hash Table / Two Pointer 18
344. Reverse String -- -- Two Pointer / String 20
28. Implement strStr() -- -- Two Pointer / String 21
125. Valid Palindrome -- -- Two Pointer / String 24
234. Palindrome Linked List. -- -- Two Pointer / Linked List 25
88. Merge Sorted Array -- -- Two Pointer / Array 26
141. Linked List Cycle – -- Linked List / Two Pointers 30
142. Linked List Cycle II -- -- Linked List / Two Pointers 经典题目 31
345. Reverse Vowels of a String -- -- String / Two Pointers 34
19. Remove Nth Node from End of List --- Two Pointers / Linked List 经典 38
Tag II -- -- Linked List 40
各种关系data structure很重要 40
237. Delete Node in a Linked List -- -- Linked List 42
203. Remove Linked List Elements 42
83. Remove Duplicates from Sorted List 43
82. Remove Duplicates from Sorted List II -- 【M】必背dummy node 45
206. Reverse Linked List 经典 45
92. Reverse Linked List II -- 【M】经典 47
21. Merge Two Sorted Lists -- dummy node 48
86. Partition List --【M】 49
160. Intersection of Two Linked List 50
24. Swap Nodes in Pairs 52
Tag III -- -- Sort 53
242. Valid Anagram -- -- Counting Sort / Hash Table 经典但是没懂。 54
75. 【M】Sort Colors -- -- Counting Sort / Two Pointers / Array 一周之内最好每天做一遍，三指针太牛了 56
148. 【M】Sort List 经典重要 快排 不懂 58
Tag IV. Tree 60
101. Symmetric Tree -- DFS / BFS / Tree 62
100. Same Tree – Tree / DFS 64
226. Invert Binary Tree – Tree 65
257. Binary Tree Path – Tree / DFS 68
104. Maximum of Depth of Binary Tree – Tree / DFS Depth-First Search 69
递进一个题：Lintcode 改变 root leave 71
递进 Lintcode: Binary Tree Maximum Path Sum II root any node/D&C 71
递进 124. Binary Tree Maximum Path Sum 【H】any node any node / D&C经典 72
111. Minimum of Binary Tree – Tree / DFS / BFS 74
110. Balanced Binary Tree – Tree / DFS / D&C 76
102. Binary Tree Level Order Traversal – Tree / BFS必背 77
107. Binary Tree Level Order Traversal II 79
103. Binary Tree Zigzag Level Order Traversal – 【M】 80
235. Lowest Common Ancestor of a Binary Search Tree 81
236. Lowest Common Ancestor of a Binary Tree 【M】多体会 82
404. Sum of Left Leaves -- Tree 83
112. Path Sum – 数的求和 84
113. Path Sum II -- 【M】DFS 86
144. Binary Tree Preorder Traversal – Stack / Tree/ 【M】 87
94. Binary Tree Inorder Traversal – Tree/ Stack 【M】经典 必背 89
145. Binary Tree Postorder Traversal -- 【H】 90
270. Closest Binary Search Tree Value 【E】 90
298. Binary Tree Longest Consecutive Sequence -- 【M】 92
Tag V ---- Binary Search BS-Index/BS-Result 92
Lintcode. First position of Target -- BS-Index 92
Lintcode. Last position of Target -- BS-Index 93
74. Search a 2D Matrix – BS-Index / Array 94
35. Search Insert Position – BS-Index / Array 95
Lintcode. Search in a Big Sorted Array – BS-Idex / O(log k) 96
153. Find Minimum in Rotated Sorted Array -- 【M】Good / BS-Index 98
33. Search in Rotated Sorted Array -- 【H】/ BS-Index 99
69. Sqrt(x) -- 【M】/ BS-Result 100
278. First Bad Version – BS/Result 101
Lintcode. Wood Cut – BS/Result 【M】经典 102
162. Find Peak Element – BS/Result / Array 【M】 103
34. Search for a Range -- 【M】 104
98. Validate Binary Search Tree – inorder延伸【M】 106
173. Binary Search Tree Iterator --【M】常见/ inorder/stack 107
285. Inorder Successor in Binary Search Tree -- 【M】 108
Lintcode 没做的 109
Tag VI. Array 109
78. Subsets – Array / Backtracking / Bit Manipulation 【M】必背非递归 109
56. Merge Intervals – 【H】/ Array/ Sort 111
200. Number of Islands -- 【M】DFS+BFS+Recursive 112
228. Summary Ranges --【M】 113
163. Missing Ranges --【M】 114
Tag VII. Dynamic Programming 116
120. Triangle --【M】有问题 动规求最小值 117
64. Minimum Path Sum -- 【M】动规求最小值 118
62. Unique Paths -- 【M】动规统计方案个数 119
63. Unique Paths II -- 【M】动规统计方案个数 120
70. Climbing Stairs 121
Lintcode -- Jump Game / Greedy/ DP -【M】 123
Lintcode -- Jump Game II / Greedy/ DP -【M】 124
300. Longest Increasing Subsequence --【M】经典 LIS问题 124
279. Perfect Squares --【M】/DP/ BFS 答案也没有看懂 125
139. Word Break--【M】/DP 不明白 125
Tag VIII. Hash Table 126
288. Unique Word Abbreviation 126
Tag VIIII. Stack 127
20. Valid Parentheses 127
155. Min Stack -- /design 129
Tag X. BackTracking 130
Tag XI. String 131
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的第一位。
1. Two Sum
https://leetcode.com/problems/two-sum/
http://www.cnblogs.com/springfor/p/3859618.html
http://www.jiuzhang.com/solutions/two-sum/
https://discuss.leetcode.com/topic/44938/o-n-solution-with-explaination
审题需要注意：
1. 要求return zero-based index 数组第一个元素是0 index
My First Version Solution: Correct. But the run time is T(n) = O(n平方)
public class Solution {
public int[] twoSum(int[] nums, int target) {
int len = nums.length;
int[] res = new int[2];
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (nums[i] + nums[j] == target) {
res[0] = i;
res[1] = j;
}
}
}
return res;
}
}
九章答案：----- 把target – nums 存入map ，遍历nums
public class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.get(nums[i]) != null) {
int[] res = {map.get(nums[i]), i};
return res;
}
map.put(target - nums[i], i);
}
int[] res = {};
return res;
}
}
// 这个自己改了下不对。
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.get(nums[i]) != null) {
res[0] = map.get(nums[i]);
res[1] = i;
return res;
}
map.put(target - nums[i], i);
}
return res;
}
}
// discussion 的答案。。。
思路正好与九章答案逆向思维。把已知数组存入map。遍历target - nums
public class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int anotherNum = target - nums[i];
if (map.containsKey(anotherNum)) {
int[] res = {map.get(anotherNum), i};
return res;
}
map.put(nums[i], i);
}
return null;
}
}
**总结： 1. 需要从已知数组中找两个数加起来等于target. 我刚开始第一个意识就是要遍历两边数组，但是效率太低。好的思路就是，找到两者之间的联系，把数组放到HashMap里，再用他们之间的联系，遍历数组，在Map中找到对应的Index。。