这是Leetcode Top 100 Liked Problems中大部分题目（83道）的题解。
按照题号排序。
每道题及部分一题多解的代码可以在这个GitHub仓库中的leetcode子目录中找到。
推荐一做的题目会标上*。这里直接给出列表：
- 二分；[4,33]
- DP；[10,32,64,72,312,416]
- 双指针；[11,15]
- 模拟；[46,146]
- 链表；[19,142,148]
- 队列；[239]
- 树；[105,337,538]
- 堆；[23]
- 栈：[42,85]
- 搜索：[301]
感受：
- 很多边界甚至不合法的输入都需要考虑。
- 常数非常重要。
- 写得优雅比写得快更重要。
- 短只是优雅的一部分。
- 整体来说还是比较简单的。
拓展阅读：
- 链表专题：http://wuchong.me/blog/2014/03/25/interview-link-questions/
- Leetcode另一份题解：https://zhuanlan.zhihu.com/p/25697275 ； 有567题，但更简略
1. Two Sum
给一个数组，找出两个数和为\(k\)，输出这两个数的下标。
用一个unordered_set记录之前的数即可，时间复杂度是\(O(n)\)。
2. Add Two Numbers
大整数加法，数据结构是链表。
3. Longest Substring Without Repeating Characters
找一个最长的字串，要求不含有相同的字符。
双指针\(i,j\)，每次固定\(i\)，找到最优的\(j\)，时间复杂度是\(O(n)\)。
*4. Median of Two Sorted Arrays
找两个有序数组的中位数。
记两个数组大小分别为\(n,m\)。
| 算法 | 时间复杂度 | 空间复杂度 | 时间 | 空间 | 时间排名 | 空间排名 |
|---|---|---|---|---|---|---|
| 归并 | \(O(n+m)\) | \(T(n+m)\) | 40ms | 21.7MB | 97% | 30% |
| 二分答案 | \(O(\log n+\log m)\) | \(T(1)\) | 56ms | 21.2MB | 14% | 97% |
二分答案，即每次枚举最终的答案\(X\)，显然可以用两次二分来找出\(X\)在两个数组的次序和，以及显然次序和与\(X\)的关系满足二分性质；那么最终的复杂度即为\(O(\log n+\log m)\)。这个做法可以解决找多个有序数组内的第k大问题，复杂度是\(O(\sum(\log n_i))\)，记第i个数组的大小为\(n_i\)。
5. Longest Palindromic Substring
最长回文子串。
记字符串长度为\(n\)。
| 算法 | 时间复杂度 | 空间复杂度 | 时间 | 空间 | 时间排名 | 空间排名 |
|---|---|---|---|---|---|---|
| 暴力 | \(O(n^3)\) | \(T(1)\) | - | - | - | - |
| 枚举中点 | \(O(n^2)\) | \(T(1)\) | - | - | - | - |
| DP | \(O(n^2)\) | \(T(n^2)\) | 316ms | 194.1MB | 17% | 8% |
| Manacher | TODO | - | - | - | - | - |
*10. Regular Expression Matching
只有.*的正则表达式匹配。
记字符串\(s\)长度为\(n\)，目标串\(p\)长度为\(m\)。
| 算法 | 时间复杂度 | 空间复杂度 | 时间 | 空间 | 时间排名 | 空间排名 |
|---|---|---|---|---|---|---|
| DP | \(O(mn)\) | \(T(mn)\) | 8ms | 11.7MB | 99% | 45% |
记\(dp_{i,j}\)为\(s_{i..}\)与\(p_{j..}\)匹配与否。
对于当前位置，显然有 \(match\_here = (s_i = p_j) \lor (p_j = \text{.})\) 。
\[ dp_{i,j} = \begin{cases} match\_here \land dp_{i+1, j} \lor dp_{i, j+2} \quad, & p_{j+1}=\text{*} \\ match\_here \land dp_{i+1,j+1} \quad, & \text{else} \\ \end{cases} \]
*11. Container With Most Water
给定一个数组\(h_i\)，表示在\(i\)的位置有一个长度为\(h_i\)的薄板，求任意选取两块薄板所能装下的最大水量。
贪心即可；时间复杂度\(O(n)\)。
*15. 3 Sum
给一个数组，输出所有和为\(k\)的三元组。
记数组长度为\(n\)。
| 算法 | 时间复杂度 | 空间复杂度 | 时间 | 空间 | 时间排名 | 空间排名 |
|---|---|---|---|---|---|---|
| 暴力 | \(O(n^3)\) | \(T(1)\) | - | - | - | - |
| 排序A | \(O(n^2\log n)\) | \(T(n^2)\) | 1104ms | 17.9MB | 15% | 39% |
| 排序B | \(O(n^2)\) | \(T(1)\) | 108ms | 16.4MB | 82% | 78% |
暴力很简单；枚举位置\(i,j,k\)即可。
排序A，即排序后枚举\(i,j\)，然后二分\(k\)的位置，需要一个集合来对答案去重；由排序B算法的复杂度可知这个集合的最大大小为\(T(n^2)\)，那么用平衡树维护这个集合的时间复杂度和枚举\(i,j\)并二分\(k\)相同。
排序B，即排序后枚举\(i\)，然后双指针移动\(j, k\)。
17. Letter Combinations of a Phone Number
九宫格输入法，给一个输入的数字顺序，求所有可能的结果。
模拟一下。
*19. Remove Nth Node From End of List
删除单向链表的倒数第\(n\)个节点。
用两个指针即可，保持前一个指针和后一个指针间隔为\(n\)。
20. Valid Parentheses
一个含有{,[,(,),],}的括号序列，询问是否合法。
用一个栈模拟一下即可。
21. Merge Two Sorted Lists
合并两个有序链表，归并一下即可。
22. Generate Parentheses
生成所有长度为\(2l\)的合法括号串，仅使用()。
DFS一下即可。
这个题的时间复杂度是合法括号串的数目，即是第\(l\)个卡特兰数。
*23. Merge k Sorted Lists
\(k\)路归并链表。
记有\(k\)个链表，共有\(n\)个元素。
| 算法 | 时间复杂度 | 空间复杂度 | 时间 | 空间 | 时间排名 | 空间排名 |
|---|---|---|---|---|---|---|
| 堆 | \(O(n\log k)\) | \(O(k)\) | 40ms | 12.5MB | 47% | 22% |
| 分治 | \(O(n\log k)\) | \(O(1)\) | 24ms | 12.3MB | 99% | 98% |
分治的做法即为每次两两合并，显然需要\(\log k\)次，而合并两个有序链表复杂度是\(O(n)\)。
31. Next Permutation
给定一个排列\(p_i\)，求下一个字典序排列。
分为三步：
- 找到最大的i，使 \(p_i>p_{i-1}\) ；如果不存在，则跳到4
- 从i开始，找到最大的j，使 \(p_j>p_{i-1}\)
- 交换 \(p_{i-1}, p_j\)
- 翻转 \(p_{i..}\)
思考：如何将这个题的代码给第46题使用？
*32. Longest Valid Parentheses
给一个仅含有()的括号序列，求最长合法子串。
| 算法 | 时间复杂度 | 空间复杂度 | 时间 | 空间 | 时间排名 | 空间排名 |
|---|---|---|---|---|---|---|
| DP | \(O(n)\) | \(T(n)\) | 12ms | 11.3MB | 63% | 11% |
记原串为\(s\)。
记\(dp_i\)为以\(s_i\)为结尾的最长串的长度。
那么有转移：
\[ dp_{i} = \begin{cases} 0 \quad , & s_i=\text{(} \\ dp_{i-2} + 2\quad , & s_{i-1}=\text{(} \land s_i=\text{)} \\ f \quad, & s_{i-1}=\text{)} \land s_i=\text{)} \land s_{i-dp_{i-1}-1} = \text{(} \\ 0 \quad , & \text{else} \end{cases} \\ f = \begin{cases} dp_{i-1} + 2 \quad , & i-dp_{i-1}-1 = 0 \\ dp_{i-1} + dp_{i-dp_{i-1}-2} + 2 \quad , & i-dp_{i-1}-1 > 0 \\ \end{cases} \]
*33. Search in Rotated Sorted Array
给出一个旋转意义下有序的数组，要求在\(O(\log n)\)的时间复杂度内判断是否包含一个元素。
旋转意义下有序的例子如：5 6 7 1 2 3 4。
在二分的时候，显然至少有一侧是有序的；并且能直接知道要找的元素是否在这一侧。
34. Find First and Last Position of Element in Sorted Array
二分即可。
39. Combination Sum
给出若干数，输出使用这些数凑齐\(k\)的方案数，每个数可以使用多次；DFS即可。
*42. Trapping Rain Water
| 算法 | 时间复杂度 | 空间复杂度 | 时间 | 空间 | 时间排名 | 空间排名 |
|---|---|---|---|---|---|---|
| DP | \(O(n)\) | \(T(n)\) | TODO | - | - | - |
| 单调栈 | \(O(n)\) | \(T(n)\) | 8ms | 9.3MB | 99% | 98% |
给出一个数组\(p_i\)，表示在数轴\(i\)的位置上有一个高为\(p_i\)的薄板，问最多能装多少水（可以使用任意多的薄板）。
比较简单的做法就是从左往右和从右往左两次DP，分别维护到\(i\)位置薄板的最大值；记为\(l_i, r_i\)；显然最后的答案是\(\sum_i \min(l_i, r_i)-p_i\)；时间复杂度和空间复杂度都是\(O(n)\)。
另一种做法是使用单调栈，栈内维护到\(i\)位置的一个\(p_i\)的不增子序列，即当前状态的一侧薄板们；只需要迭代一次。
*46. Permutations
给出若干个不同的数，求其生成的所有排列。
拓展：如果有相同的数呢？
48. Rotate Image
先上下翻转，后沿对角线翻转。
49. Group Anagrams
模拟一下即可。
53. Maximum Subarray
找出一个数组的最大区间和。
可以DP，可以使用前缀和；时间复杂度都是\(O(n)\)。
55. Jump Game
给定一个数组\(p\)，对于\(p\_i\)表示\(p\_{i..i+p_i}\)可达，给定起点，问\(p\_j\)是否可达？
维护当前最远可以到达的点；时间复杂度\(O(n)\)。
56. Merge Intervals
给出若干段区间，要求将其覆盖的部分合并。
排序后扫一遍即可；时间复杂度\(O(n\log n)\)。
62. Unique Paths
给出一个\(n\times m\)的网格，求左上角走到右下角的方案数，只可以往右或往下走。
显然最后的答案是\(C_{n+m-2}^{n-1}\)。
*64. Minimum Path Sum
给一个\(n\times m\)的矩阵\(M\)，每个元素是一个整数，给出从左上角到右下角的路径，使其经过的数字和最小。
记\(dp_{i,j}\)为走到\(i,j\)这个位置时的最小和。那么有：
\[ dp_{i,j} = \begin{cases} M_{i,j} \quad , & i = 0 \land j = 0 \\ M_{i,j} + dp_{i-1, j} \quad , & i > 0 \land j = 0 \\ M_{i,j} + dp_{i, j - 1} \quad , & i = 0 \land j > 0 \\ M_{i,j} + \min(dp_{i-1,j}, dp_{i, j-1}) \quad, & \text{else} \end{cases} \]
70. Climbing Stairs
爬\(n\)级台阶，每次爬一步或者两步，问有多少种爬的方案。
显然最后的答案是斐波那契数列的第\(n\)项。
*72. Edit Distance
给定两个串\(p, s\)，求最少经过多少步操作，\(p\)可以变到\(s\)？操作可以包括：
- 删去一个字母
- 增加一个字母
- 替换一个字母
记 \(dp_{i,j}\) 表示 \(p_{..i}\) 到 \(s_{..j}\) 的最少操作数，那么有转移：
\[ dp_{i,j} = \begin{cases} |i-j| \quad , & i = -1 \lor j = -1 \\ dp_{i-1, j-1} \quad , & s_i = p_j \\ \min(dp_{i-1, j-1}, dp_{i-1, j}, dp_{i, j-1}) + 1 \quad , & \text{else} \end{cases} \]
显然最后的答案是\(dp_{|s|,|p|}\)。
75. Sort Colors
给定一个数组仅包含0,1,2；要求使用\(O(n)\)时间、\(T(1)\)空间排序。
计数排序可以做到，有一个更优的做法可以做到只扫一遍，见Dutch National Flag Problem。
76. Minimum Window Substring
给定串\(s, t\)，求\(s\)的最短字串\(s'\)，\(s'\)中包含\(t\)的所有字母。
扫一遍即可。
78. Subsets
求幂集，DFS/二进制枚举均可。
79. Word Search
给定一个\(n\times m\)的矩阵，每个元素是一个字符，求是否存在一条路径组成某个单词。
DFS即可。
84. Largest Rectangle in Histogram
给出一个数组\(p_i\)，表示在数轴\(i\)的位置上有一个高为\(p_i\)的薄板，问薄板覆盖的面积中最大子矩形有多大。
单调栈可以解决这个问题。
单调栈内维护对于\(i\)的左边最低；时间复杂度\(O(n)\)。
*85. Maximal Rectangle
对于一个\(n \times m\)的0/1矩阵，找出最大全1子矩阵。
对于每行，找出每个元素往上连续的'1'的数目；那么对于这一行，可以使用84题的做法；时间复杂度\(O(nm)\)。
94. Binary Tree Inorder Traversal
DFS或者用栈即可。
96. Unique Binary Search Trees
显然，一个节点数为\(n\)的BST的方案数为第\(n\)个卡特兰数。
98. Validate Binary Search Tree
判断一棵二叉树是不是二叉搜索树，记二叉树有\(n\)个节点。
DFS即可。
101. Symmetric Tree
判断一颗二叉树是不是对称的。
DFS即可；时间复杂度\(O(n)\)
102. Binary Tree Level Order Traversal
给出一棵二叉树的层序遍历，BFS即可。
104. Maximum Depth of Binary Tree
计算一棵二叉树的高度，DFS即可。
*105. Construct Binary Tree from Preorder and Inorder Traversal
已知一棵二叉树结点无相同的值，给出一棵二叉树前序和中序遍历，求这个二叉树。
显然前序遍历的第一个值可以将中序遍历分为左子树和右子树，那么DFS即可。
114. Flatten Binary Tree to Linked List
DFS一次即可。
121. Best Time to Buy and Sell Stock
给出一个股票的时间序列，问最好的买入、卖出区间（只能交易一次）。
扫一遍即可，维护最小持有成本。
124. Binary Tree Maximum Path Sum
求二叉树的最大路径和，DFS即可。
128. Longest Consecutive Sequence
给定一个数组，求最长能组成连续自然数序列的子序列。
任意从数组中取出一个数，贪心地从数组中取出数再更新答案即可；时间复杂度\(O(n)\)。
136. Single Number
给定一个数组，数组中仅一个一个数出现了1次，其他数都保证出现了2次。
最好的做法是全部异或一遍。
139. Word Break
给出一个串\(s\)，和若干个串\(p\_i\)，问\(s\)能否由若干个\(p\_i\)组成（可以使用多次）。
记 \(dp\_i\) 为 \(s[0:i)\) 能否由若干个 \(p\_i\) 组成，那么显然答案是 \(dp_{|s|}\) 。并且有DP方程：
\[ dp_{i} = (dp_{i-|p_j|..i-1} = p_j) \land dp_{i-|p_j|} , \forall j \in [1, n], j \in \mathbb{Z} \]
141. Linked List Cycle
给出一个单项链表，询问其是否存在环。
快慢两个指针，快指针每次前进两步，慢指针每次前进一步，如果有环那么快慢指针一定相遇。
*142. Linked List Cycle II
给出一个单项链表，询问其是否存在环；如果有环，求环的第一个结点。
快慢两个指针，快指针每次前进两步，慢指针每次前进一步，如果有环那么快慢指针一定相遇，此时另有一个慢指针从头开始移动，同时移动慢指针，它们一定相遇于环的第一个结点。
*146. LRU Cache
实现一个LRU Cache。
记有\(k\)次操作，容量为\(n\)。
| 算法 | 时间复杂度 | 空间复杂度 | 时间 | 空间 | 时间排名 | 空间排名 |
|---|---|---|---|---|---|---|
| 模拟 | \(O(k\log n)\) | \(T(n)\) | 164ms | 41.9MB | 15% | 0% |
| 链表 | \(O(k)\) | \(T(n)\) | 136ms | 40.1MB | 43% | 34% |
*148. Sort List
给一个单向链表排序，要求时间复杂度不超过\(O(n\log n)\)。
归并排序即可。
152. Maximum Product Subarray
给出一个数组，求最大区间积。
扫一遍即可，维护当前遇到的最大值和最小值。
155. Min Stack
用两个栈，另一个记录当前遇到的最小值。
160. Intersection of Two Linked Lists
求两个单向链表的交点。
将较长链表的头往后移动两个链表的长度差次，后一起移动直到两个指针相遇，相遇点显然是交点。
169. Majority Element
已知一个数组\(s\)内一个元素出现了多于\(\frac{|s|}{2}\)次，求这个元素。
摩尔投票算法可以解决这个问题。
198. House Robber
给定一个数组\(s\)，随机选取一些元素，要求选取的元素中不能有在原数组中相邻的，求一个方案使选取的元素和最大。
维护到（包括）当前点的最大值，分为当前点取、不取两种情况。
200. Number of Islands
求一个\(m \times n\)网格图上的连通块数目。
DFS/BFS即可。
206. Reverse Linked List
反转一个单向链表。
207. Course Schedule
询问一个有向图是否有环，使用BFS/DFS/拓扑排序/并查集等等算法均可；时间复杂度\(O(V+E)\)。
208. Implement Trie (Prefix Tree)
实现一棵前缀树。
226. Invert Binary Tree
翻转二叉树，DFS即可。
234. Palindrome Linked List
判断一个单向链表是不是回文的。
记链表长度为\(l\)先找到第\([\frac l2]\)结点，后将这个结点的后继（子链表）反向；问题转化为两个链表是否一个为另一个的前缀。
*239. Sliding Window Maximum
给出一个数组\(p_i\)，滑动窗口内的最值问题。
单调队列可以解决这个问题。
一个简单的引理：如果\(p_j > p_i, j > i\)那么对于\(j..n\)，\(j\)一定比\(i\)优。
283. Move Zeroes
将一个数组中的0原地地移动到数组尾部。
300. Longest Increasing Subsequence
求最长上升子序列的长度。
301. Remove Invalid Parentheses
这个题目神奇的地方在于，它真的是\(O(n^2)\)的。
*312. Burst Balloons
给出若干个气球，\(b_i\)，戳破\(b_i\)可以得到\(\prod_{i-1}^{i+1}b_i\)的金币，求一个戳破顺序使获得的金币最多。可以假设最前面和最后面分别由一个价值为1且不可戳破的气球。
记\(dp_{i, j}\)为区间\((i,j)\)内可以获得的最大价值。显然有：
\[ dp_{i,j} = \begin{cases} 0 \quad , & i + 1 >= j \\ \max b_ib_kb_j + dp_{i, k} + dp_{k, j}, \forall k \in (i, j), k \in \mathbb{Z} \quad , & \text{else} \\ \end{cases} \]
*337. House Robber III
在一棵有\(n\)个结点的二叉树上随机选取一些结点，要求不能有任意两个相连结点被同时选取，求一个方案使选取的结点和最大；输出这个最大值。
记忆化DFS一下即可，时间复杂度\(O(n)\)。
338 Counting Bits
询问\(0-n\)内每个数的二进制表示中有多少个1。
*416. Partition Equal Subset Sum
给出一个集合\(s\)，问是否存在一个划分使两部分的和相等。
记\(S=\sum s\)，显然如果\(S\)为奇数，那么划分不存在。
问题等价于原集合\(s\)中是否存在一个子集的和为\(\frac S2\)，显然0/1背包可以解决；时间复杂度\(O(|s|S)\)，空间复杂度\(T(S)\)。
437. Path Sum III
问树上有多少个路径的和为\(k\)。
DFS即可。
448. Find All Numbers Disappeared in an Array
给出一个数组，长度为\(n\)，其中仅包含范围在\([1,n]\)的数，有的数可能出现了多次，要求找出没有出现过的数。
扫一遍即可，时间复杂度\(O(n)\)，空间复杂度\(O(1)\)。
461. Hamming Distance
求两个数的二级制位不同的数目。
__builtin_popcount(x ^ y)即是答案。
494. Target Sum
给出若干个数，在每个数前添加加号或减号使表达式的值等于\(k\)，问有多少种方案。
DFS即可。
*538. Convert BST to Greater Tree
给定一棵二叉搜索树，要求对于树上所有的结点，其值加上所有值大于它的值的结点的和。
DFS即可，利用二叉搜索树的性质；时间复杂度\(O(n)\)。
543. Diameter of Binary Tree
求一棵二叉树的最长路径。
DFS即可，时间复杂度\(O(n)\)。
560. Subarray Sum Equals K
给出一个数组，求其所有连续子数组和为K的数目。
前缀和+哈希，时间复杂度\(O(n)\)。
572. Subtree of Another Tree
给出两棵树，询问一棵树是否为另一个树的子树。
DFS即可。
581. Shortest Unsorted Continuous Subarray
给定一个数组，求一个长度最小的区间：如果将这个区间排序，那么整个数组有序。
可以用栈扫一遍，时间复杂度\(O(n)\)；也可以排序，时间复杂度\(O(n\log n)\)。
617. Merge Two Binary Trees
合并两棵二叉树，要求新树的结点的值是原树对应位置的和（没有则视为0）。 模拟即可。
771. Jewels and Stones
给出两个串\(s,p\)，问\(p\)中有多少个字符在\(s\)中也有。