持续更新! ଘ(੭ˊ꒳ˋ)੭✧
0 双指针 Two Pointers
15. 3Sum
先排序
外层循环枚举i，内层循环使用双指针找到target组合，枚举左边界l，缩小右边界r
80. Remove Duplicates from Sorted Array II
438. Find All Anagrams in a String
567. Permutation in String
1 二分查找 Binary Search
33. Search in Rotated Sorted Array
数组中无重复元素
先确定target所在区间，再缩小范围
81. Search in Rotated Sorted Array II
数组中有重复元素
34. Find First and Last Position of Element in Sorted Array
寻找上下边界
69. Sqrt(x)
寻找上边界
74. Search a 2D Matrix
二分查找row和col，注意找到row以后要判断是否越界
查找row的时候寻找上边界
153. Find Minimum in Rotated Sorted Array
数组中无重复元素
比较mid与right
154. Find Minimum in Roatated Sorted Array II
数组中有重复元素
mid与right相同时，right递减
2 单调栈 Monotonic Stack
739. Daily Temperatures
递减单调栈
496. Next Greater Element I
与Daily Temperatures相同
503. Next Greater Element II
同上
84. Largest Rectangle in Histogram
递增单调栈
402. Remove K Digits
贪心+递增单调栈
316. Remove Duplicates Letters
与402.类似
需要记录一下字母的频率和是否已出现
3 二叉树 Binary Tree
大部分问题都可以用递归解决
对于是二叉搜索树的题，利用好二叉搜索树节点的特性!
226. Invert Binary Tree
ac这道我是不是就可以去Google了 (x
98. Validate Binary Search Tree
中序遍历，记录prev
99. Recover Binary Search Tree
中序遍历，找到顺序不同的两个点并交换
103. Binary Tree Zigzag Level Order Traversal
用一个vector来分别倒序/正序存放每一层的节点
105. Construct Binary Tree from Preorder and Inorder Traversal
挺简单的! 注意下标
662. Maximum Width of Binary Tree
同时记录节点的索引
对于索引为i的节点，其左孩子索引为(2i + 1)，右孩子索引为(2i + 2)
为了防止索引溢出，以每层的leftmost节点的索引作为offset
4 前缀和 Prefix Sum
560. Subarray Sum Equals K
525. Contiguous Array
5 回溯 Backtracking
回溯本质上就是DFS，比较套路，有一些实现上的细节，具体将在下面例题中提到.
17. Letter Combinations of a Phone Number
非常朴素的回溯. 很简单.
22. Generate Parentheses
注意括号匹配问题，可以根据当前左右括号数量来判断接下来增加左括号或右括号.
39. Combination Sum
候选数字无重复，可被重复使用.
很简单，注意记录位置防止重复访问.
40. Combination Sum II
候选数字有重复，不可被重复使用.
可以先排序，然后遇到与上一个候选数字相同的数字就跳过.
46. Permutations
同39. 如果不使用额外的空间，可以利用swap
47. Permutations II
同40. 但要注意前一个数字需要未访问
6 排序 Sorting
215. Kth Largest Element in an Array
经典快排题，每次确定kth element所在的区间，然后在该区间中寻找pivot，判断是否为kth element
347. Top K Frequent Elements
桶排序
75. Sort Colors
荷兰国旗问题 (适用于只有三个类别时)，也可以当双指针理解
7 动态规划 Dynamic Programming
5. Longest Palindromic Substring
dp[i][j]表示s[i, j)是否为palindrome
dp[i][j] = dp[i+1][j-1] && (s[i] == s[j])
外层循环枚举右端点，内层循环枚举左端点
197. House Robber
分别用两个变量记录到house[i - 1]的最大抢劫金额和到house[i - 2]天的最大抢劫金额
213. House Robber II
house[0]与house[n - 1]相邻
取抢劫house[n - 1]和不抢劫house[n - 2]的最大值
847. Shortest Path Visiting All Nodes
状态定义为 (经过的节点，当前的节点)，记录此时的距离
经过的节点可以用位操作来定义
使用BFS搜索，当所有节点都遍历完以后，返回当前状态的距离
740. Delete and Earn
可以将问题转化为House Robber
1143. Longest Common Subsequence
Hint1: dp[i][j] represents the longest common subsequence of text1[0 … i] & text2[0 … j]
Hint2: dp[i][j] = dp[i - 1][j - 1] + 1 , if text1[i] == text2[j]; dp[i][j] = max(dp[i - 1][j], DP[i][j - 1]) , otherwise