| 1 Two Sum (E) |
Map存num和index，判断target-num∈map |
| 2 Add Two Numbers (M) |
dummy+cur, carry, while用\ |
\ |
节省代码 |
| 3 Longest Substring Without Repeating Characters (M) |
模板，while (map.get(c) > 1) 移l，abcdee->e |
|
|
|
|
| 7 Reverse Integer (E) |
rev, while, tmp, if (temp / 10 != reverse) 溢出 return 0; |
| 9. Palindrome Number (E) |
rev, while (rev < x), if (x < 0 \ |
\ |
(x != 0 && x % 10 == 0)) return false, return rev == x \ |
\ |
rev / 10 == x; |
| 10 Regular Expression Matching (H) |
|
| 14 Longest Common Prefix (E) |
// 1. start from the first one, compare prefix with next string, until end; // 2. 二分，每次猜LCP 的长度，空间复杂度可以优化为O(1) |
| 20 Valid Parentheses (E) |
stack, 遇左push, 遇右pop比较, (((()))。FU 1.很多种: map存对应关系，if (map.containsKey(c)) push, else if(c != map.get(stack.pop()) return false; |
| 21 Merge Two Sorted Lists (E) |
dummy+cur, while用\ |
\ |
节省代码 |
| 25. Reverse Nodes in k-Group (H) |
|
| 33 Search in Rotated Sorted Array (M) |
4123，mid在右 |
| 42 Trapping Rain Water (H) |
|
|
|
|
|
|
|
| 46 Permutations (M) |
|
| 54 Spiral Matrix (M) |
x, y, d, dirs, range={n, m - 1}, while (range[d % 2] != 0) |
| 56. Merge Intervals (M) |
sort, pre=null, if (pre == null \ |
\ |
cur.start > pre.end) { res.add(cur); pre = cur; } else { pre.end = Math.max(pre.end, cur.end);} |
| 57. Insert Interval (H) |
(sort) 先插入，再合并 |
| 62 Unique Paths (M) |
坐标型，if (i == 0 \ |
\ |
j == 0) { dp[i][j] = 1; } else { dp[i][j] = dp[i - 1][j] + dp[i][j - 1];} |
| 63 Unique Paths II (M) |
|
| 69. Sqrt(x) (E) x非负 |
二分range，[1,x] FU:x是double类型，while (l + 1e-(精度位数+2 ) < r) |
| 70 Climbing Stairs (E) |
dp[i] = dp[i - 1] + dp[i - 2] |
| 72 Edit Distance(H) |
|
| 75. Sort Colors (M) AllCompanies |
三指针，i, left, right |
| 80 Remove Duplicates from Sorted Array II (M) |
|
| 88 Merge Sorted Array (E) |
同向双指针，从右往左放，存大的。while (i >= 0 && j >= 0) 记得while (j >= 0) // 因为是将nums2合并到nums1，所以要考虑m一开始=0的情况 |
| 94 Binary Tree Inorder Traversal (M) |
|
| 98 Validate Binary Search Tree (M) |
分治最简洁；R: pre=null；L: stack中序 |
| 102 Binary Tree Level Order Traversal (M) |
|
| 105 Construct Binary Tree from Preorder and Inorder Traversal (M) |
|
| 116 Populating Next Right Pointers in Each Node (M) |
不需要dummy, cur, while, tmp, while。在当前层给下层connect，base: root层不需要connect。 |
| 117 Populating Next Right Pointers in Each Node II (M) |
cur, dummy, next, while, while |
| 118 Pascal's Triangle (E) |
|
| 120 Triangle (M) |
|
| 121 Best Time to Buy and Sell Stock (E) 最多一次 |
maxProfit, minPrice, update them during traverse |
| 122 Best Time to Buy and Sell Stock II (E) 任意次 |
贪心，accumulate diff，max += Math.max(0, prices[i] - prices[i - 1]); |
| 123. Best Time to Buy and Sell Stock III (H) 最多两次 |
|
| 127 Word Ladder (M) |
|
| 133 Clone Graph (M) |
<old node's val or ref, new node's ref>, copy nodes, then copy edges(复制点与点的关系，必须用HashMap) 如果节点val有重复，map的key存node，而不是val。DFS: 递归有返回值 |
| 138 Copy List with Random Pointer (M) |
copyNext, copyRandom, splitList |
| 139 Word Break (M) |
O(n^3) 序列型，list转成set，if (dp[j] && set.contains(s.substring(j, i))) { dp[i] = true; break; }，注意j，dp[j]对应s.charAt(j-1)。FU:返回一个解: boolean改成int，dp[i]=j，store the index of left string's last char，然后用list倒序存单词，然后再倒存一遍。 |
| 140 Word Break II (H) 细看 |
DFS返回值+Map |
| 146 LRU Cache (H) |
Map存<key, node>+DDL存key val，变种很多，有总结 |
| 153 Find Minimum in Rotated Sorted Array (M) |
|
| 155 Min Stack (E) |
S1:一个stack，一个min变量。push时当x<=min，先把minpush，再更新min；pop时，if (stack.pop() == min) { min = stack.pop(); }。S2: SLL, node存val和min，node反向加，if(head == null) head = new Node(x, x); else head = new Node(x, Math.min(x, head.min), head); |
| 162 Find Peak Element (M) |
|
| 173 Binary Search Tree Iterator (M) |
|
| 191 Number of 1 Bits (E) unsigned integer |
res += n & 1; n >>>= 1; |
| 200 Number of Islands (M) |
|
| 203 Remove Linked List Elements (E) |
|
| 204 Count Primes (E) |
divide each i from 2 to sqrt(i), 2=<i<n |
| 205 Isomorphic Strings (E) |
|
| 206 Reverse Linked List (E) |
pre, cur, while, next, return pre |
| 208 Implement Trie (Prefix Tree) (M) |
|
| 214 Shortest Palindrome (H) |
|
| 225 Implement Stack using Queues (E) |
1 Queue O(n - 1) push O(1) others, push时，先add到队列末，然后将前n-1个节点poll出，add到队列末尾 |
| 226 Invert Binary Tree (E) |
递归 tmp root.right root.left; BFS |
| 232 Implement Queue using Stacks (E) |
2 Stacks O(1), amortized time 因为stack只有一个出入口，所以要两个栈。push用input栈，pop和peek用output栈，pop里用peek函数。 |
| 234 Palindrome Linked List (E) |
|
| 235 Lowest Common Ancestor of a Binary Search Tree (E) |
|
| 236 Lowest Common Ancestor of a Binary Tree (M) |
递归 |
| 239 Sliding Window Maximum (H) |
|
| 242 Valid Anagram (E) |
|
| 253 Meeting Rooms II (M) |
|
| 283 Move Zeroes (E) |
|
| 301 Remove Invalid Parentheses (H) |
|
| 311 Sparse Matrix Multiplication (M) |
|
| 322 Coin Change (M) |
|
| 341 Flatten Nested List Iterator (M) |
|
| 347 Top K Frequent Elements (M) |
|
| 380 Insert Delete GetRandom O(1) (M) |
Map<val, idx>+List+Random 插:新的val加到List最后，map存idx。删：拿val的idx和list最后一个数last，将last的索引更新为idx，将list中idx上的数设为last。最后删掉map中的val和list中的最后一个数。 |
| 387 First Unique Character in a String (E) |
先扫一遍，Map计数；再扫第二遍，检查每个字符的次数 |
| 394 Decode String (M) |
|
| 412 Fizz Buzz (E) |
|
| 445 Add Two Numbers II (M) |
|
| 451 Sort Characters By Frequency (M) |
Map + bucket sort O(n) List<Character>[] bucket = new ArrayList[n + 1]; Map + sort O(n log n) |
| 460 LFU Cache (H) |
|
| 463 Island Perimeter (E) |
|
| 547 Friend Circles (M) |
|
| 554 Brick Wall (M) |
|
| 567 Permutation in String (M) |
|
| 572 Subtree of Another Tree (E) |
|
| 582 Kill Process (M) |
|
| 659. Split Array into Consecutive Subsequences (M) IQ |
freq和need Map，num被用光，做结尾，当开头，false |
| 692 Top K Frequent Words (M) |
|
| 698 Partition to K Equal Sum Subsets (M) |
|
| 724 Find Pivot Index (E) |
|
| 739 Daily Temperatures (M) |
|
| 797 All Paths From Source to Target (M) |
|
| 811 Subdomain Visit Count (E) |
每一次insert后，SB都要转为String，所以直接用String就好 |
| 815. Bus Routes (H) Google |
找图中两点之间的最短路径长度。间接存图：key存stop，value存bus列表，通过bus再得到stop。 |
| 821 Shortest Distance to a Character (E) |
|
| 836 Rectangle Overlap (E) |
|
| 852 Peak Index in a Mountain Array (E) |