算法题复盘
以前做leetcode时积累了不少比较经典的问题，但是很少总结，经常做一道是一道，效率颇低，而且应付面试经常会碰到挺熟但还是被“卡住”的情况，遂做一总结。
- 只摘出Medium和Hard问题。
- 有的题可以有多个分类，我只将其归入最合适解法的那类中。
- 题目有大类、有子类，大类是链表、数组、动态规划，子类指的是单独的一种“套路”，比如树中的深度优先搜索是一种套路，动态规划中的背包也属于一种套路。
数组、字符串、序列、链表
难以被归类
(medium)https://leetcode.com/problems/longest-palindromic-substring/
这一题乍一看似乎用DP好解，先找出所有长度为2的回文，再找长度为3的，以此类推，但是DP是O(n2)的。
这题有非DP的更优解法，即遍历然后”从中间往外扩的方式”，比如122213，设置l、r两个指针，当遍历到位置i=1时先将r推进到i=3，然后再判断i=0和i=4是否相等，得到回文长度5，之后再从i=5开始找下一个回文串。(medium)https://leetcode.com/problems/remove-nth-node-from-end-of-list/
删除倒数第n个元素。
递归返回链表长度，判断下next链表长度是n则删除之。
注意边界条件n是链表头部的情况。(medium)https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
搜索回溯。(medium)https://leetcode.cn/problems/swap-nodes-in-pairs/description/?envType=study-plan-v2&envId=top-100-liked
两两交换链表节点，递归做很简单(hard)https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-100-liked
k个一组反转链表，考验细节(medium)https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked
我用的最简单的枚举方式，O(n^2)，但是如果第一次遍历记录hash[n]为前n个数字的和，可以对每个nums[i]找j使得hash[i] - hash[j] = k，这样可以得到一个O(n)的解法。(easy)https://leetcode.cn/problems/symmetric-tree/description/?envType=study-plan-v2&envId=top-100-liked
对称二叉树，用了两个栈来保存左和右子树，每次从栈弹出两个左右子树root节点，比较左子树的右节点和右子树的左节点。(medium)https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-100-liked
轮转数组
简单方法可以直接new一个数组来保存轮转后的位置或者时间换空间来一个个轮转
复杂方法涉及到将前最大公约数个数字进行轮转操作，轮转指的是将nums[i]放到nums[i + k]，再把nums[i + k]放到nums[i + 2k]，以此类推直到初始位置，为什么是最大公约数涉及一个推导，我是直接看的官方的题解。
另外求最大公约数是使用的辗转相除法。
Two Pointers
在链表、数组里找出一个满足条件的子串、子序列，暴力搜索会导致O(n2)的复杂度，而让两个指针同时滑动可以更快地找到目标结果。
- 目标链表、数组一般是有序的；
- (medium)https://leetcode.com/problems/longest-substring-without-repeating-characters/
用hash保存已出现的元素，当然直接用一个bool[26]记录也没问题 - (medium)https://leetcode.com/problems/container-with-most-water/
确定桶的两个端点，最多能装多少水。
一种最简单的想法是O(n2)的，即算出所有区间(i, j)内能装的水量，比较所有这些区间，得到最大值。
但用双指针能得到更简单的解法初始化l=0, r=数组长度，如果l位置的高度较低则l++，反之r–。为什么不是反过来？可以用反证法证明，如果l较低我们却令r–，这时不管r的下一个值是多少，面积始终是height[l] * (r - l)，面积只能是越来越小，也就是短板效应。 - (medium)https://leetcode.com/problems/3sum/
找出数组中的所有三元组(a, b, c)，令a+b+c=0。
一种简单的想法是将所有数据保存到Map中，然后找二元组(a, b)令a+b=-c。
还有一种twoPointer的解法，复杂度也是O(n2)。 - (medium)https://leetcode.cn/problems/next-permutation/submissions/
找下一个排列，比如12543，要把3和2交换，然后把最后3个数字倒序排列成13245。
Binary Search
二分搜索每次将查询范围缩小一半，以期找到目标结果。
- 输入数组是有序的；
- 如何找到结果的上确界、下确界？
- (medium)https://leetcode.com/problems/search-in-rotated-sorted-array/
就是二分查找，只是折半后需要比较一下中间位置元素和lmax、rmax之间的大小。 - (hard)https://leetcode.com/problems/median-of-two-sorted-arrays/
思路还是二分查找的思路，只不过这题需要对两个数组同时缩小范围。
大数
大数不能用基本类型保存，主要思路是用链表、数组等结构来实现数学运算。
- (medium)https://leetcode.com/problems/add-two-numbers/
链表保存数字，相加时注意进位。
引申：可以用数组存、可以是别的进制。
DFS、BFS、backtracking
比如给出多个数组，找出他们元素的组合这种问题。
- (medium)https://leetcode.com/problems/letter-combinations-of-a-phone-number/
电话按键组合。
深度优先搜索求多个按键元素的笛卡尔积。 - (medium)https://leetcode.com/problems/generate-parentheses/
括号组合。
每次选左括号或右括号，当右括号选得比左括号多时就直接返回（剪枝）。
hash
给出一个数组，求2-sum、3-sum、4-sum，这种问题都可以使用hash来保存中间结果
(medium)https://leetcode.com/problems/4sum/
4sum问题的基础是2sum和3sum，即对a[x]找3sum(x+1, -a[x])。
3sum就是对a[x]找2sum(x+1, -a[x])。
2sum问题可以通过twoPointers方法解决，即a[l]+a[r]<sum则l++，a[l]+a[r]>sum则r–，若a[l]+a[r]==sum则l++、r–，且如果a[l]==a[l+1]也要忽略掉，因为要避免重复。需要优化(medium)https://leetcode.cn/problems/longest-consecutive-sequence/description/
hash+并查集
关键是使用hash来存储并查集的集合：
- 数据范围是-10^9~10^9，因此不能使用数组来存储；我刚开始想在并查集的根用负数存储集合的大小，但是看到数据范围包含了负数所以行不通，只能新开了一个hash集合用于存储大小
- 并查集压缩路径可以减少耗时
树
搜索（DFS、BFS）
- (hard)https://leetcode.com/problems/sum-of-distances-in-tree/
求每个节点到其他所有节点的路径和。
最开始想到这题可以用Floyd求所有节点之间的最短路径，然后再算结果就好算了，复杂度是O(n3)，。
前序、中序、后序遍历
- (hard)https://leetcode.com/problems/recover-binary-search-tree/
交换树中两个节点，使得树恢复成二叉搜索树。
如果一棵树左边（包括root）有个节点比右边（包括root）大，则将这两个节点换一下即可。
解法描述起来简单，前序中序似乎都有解法，我采用的是后序遍历：先找到两个子节点的<最小值, 最大值>，然后在root处判断是否要进行交换。注意不要在遍历过程中交换，而是在整棵树遍历完毕后再交换一次。
二叉树
（miduem）https://leetcode.cn/problems/validate-binary-search-tree/submissions/
按二叉搜索树定义编写遍历代码，考验递归理解。(medium)https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
按二叉树的前序和中序遍历还原二叉树
思路是用hash保存每个节点值的位置（节点值不重复），前序的第一个数就是root，使用hash就可以快速找到在中序遍历中的root的位置，据此可以得到左右子树的范围。
算法设计 - 分治
分治法的思路是将大问题每次分成多个对等的子问题，并且将子问题的结果合并后能得到原问题的解。
- (hard)https://leetcode.com/problems/merge-k-sorted-lists/
这题初看似乎挺简单，每次从n个链表中找出最小的那个添加到result即可，但是这样时间复杂度是非常高的，达到了O(nnm)。
其实可以使用分治法来简化问题，每次将一半的链表先合并，然后再将两个合并后的链表合并，这样时间复杂度只有O(n*m)
算法设计 - 贪心
(medium)https://leetcode.cn/problems/jump-game/description/
刚看到以为是要做搜索，但实际上只需要从左向右扫描一次，只要每个节点向右跳的范围里有能跳更远的节点，就能一直往右跳到最后。(medium)https://leetcode.cn/problems/container-with-most-water/description/
这里的贪心策略是：从最左和最右两条线为起点，宽度更小的容器如果要装水量更大，必然高度要比最左或最右更高，每次都从左或右的低者收缩宽度找到更高的一条线。(medium)https://leetcode.cn/problems/maximum-swap/
贪心策略，比较复杂，见注释
算法设计 - 回溯
- (hard)https://leetcode.cn/problems/n-queens/description/?envType=study-plan-v2&envId=top-100-liked
N皇后问题，我的解法是写扩散的，定义int[][] visited来记录能被之前放的皇后吃到的位置，这些位置不能再放皇后，然后一行一行地遍历整个棋盘。
算法设计 - 动态规划
最子串、最子序列问题
(medium)https://leetcode.cn/problems/palindromic-substrings/description/
找所有回文子串，动态规划存储的状态表达式是d[x][y] = (s[x] == s[y]) && d[x+1][y-1](hard)https://leetcode.com/problems/longest-valid-parentheses/
找子串，其中括号必须是成对的。
最简单的办法是先找长度为2的，然后再在2的基础上找长度为4的，以此类推，复杂度会高一些。
还有一种办法是用一个栈来保存括号，遇到左括号时直接压入，而当遇到右括号时则将栈中的左括号弹出，统计连续能成对的数量（如果压入一个右括号不能与之前的左括号成对，说明接下来的括号和之前的括号都不能成对了）。(medium)https://leetcode.cn/problems/longest-increasing-subsequence/submissions/
n^2是动态规划的方案，dp[i]存储以nums[i]作为结尾的序列长度，对每个i，需要遍历所有j < i，更新dp[i] = max(dp[j]{nums[j] < nums[i]}) + 1
nlogn的方案很难想，存储牌堆顶数组top[n], 其中top[i] = 长度为i的序列的最大值，每抽一张牌k，搜索top[i]中第一个比nums[k]大的替换，如果找不到则插入到末尾，题解：https://www.kancloud.cn/digest/pieces-algorithm/163625(medium)https://leetcode.cn/problems/longest-common-subsequence/description/?envType=study-plan-v2&envId=top-100-liked
最长公共子序列问题
dp[i][j] = dp[i - 1][j - 1] + 1, t1[i] == t2[j]
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]), t1[i] != t2[j](medium)https://leetcode.cn/problems/maximum-product-subarray/description/
乘积最大子数组，因为最大成绩可能是偶数个负数相乘，因此需要定义两个数组，一个mindp[i]存储以第i个数为末尾的子数组的最小乘积
如果当前数nums[i] < 0，则
maxdp[i] = max(mindp[i] * nums[i], nums[i])
mindp[i] = min(maxdp[i] * nums[i], nums[i])
如果当前数nums[i] > 0，则
maxdp[i] = max(maxdp[i] * nums[i], nums[i])
mindp[i] = min(mindp[i] * nums[i], nums[i])
背包问题
(medium)https://leetcode.cn/problems/partition-equal-subset-sum/description/?envType=study-plan-v2&envId=top-100-liked
抽象为01背包问题，定义dp[j]的价值为数值，如果最终dp[j]==j，说明存在和为j的数，状态转移函数：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
01背包问题，需要先遍历物品，因为每个物品只能使用一次，然后容量上从大到小遍历。(medium)https://leetcode.cn/problems/coin-change/description/
01背包的升级问题，完全背包问题，定义时dp[amount]表示每个容量可以使用的最少硬币数量，从容量1开始遍历，求dp[amount]的最小值，有状态表达式：dp[n] = min(dp[n], dp[n - x] + 1), x为遍历所有硬币的价值
01背包问题因为物品用不用是有状态的，所以会增加一个维度dp[amount][coin](medium)https://leetcode.cn/problems/perfect-squares/description/?envType=study-plan-v2&envId=top-100-liked
将目标数分解为完全平方数的和，我理解成完全背包问题，不过刚开始goods需要自己算出来。
其他
(medium)https://leetcode.cn/problems/house-robber/submissions/
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])
dp[i][1] = nums[i] + dp[i - 1][0](medium)https://leetcode.cn/problems/maximal-square/description/
dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
[i][j]代表以该位置作为右下角形成的最大的正方形的边长待优化(medium)https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
买卖股票
定义多个状态：因为包含冷冻期，因此增加一个冷冻状态，注意买股票后不一定要后一天马上卖出，因此增加一个持有状态。(medium)https://leetcode.cn/problems/word-break/description/?envType=study-plan-v2&envId=top-100-liked
单词拆分，思路有点像完全背包。(medium)https://leetcode.cn/problems/edit-distance/description/?envType=study-plan-v2&envId=top-100-liked
编辑距离，定义dp[i][j]为word1的前i个字符转换为word2的前j个字符的最少需要操作次数
如果两个字符相等，则dp[i][j]=dp[i-1][j-1]，即不需要任何操作
删除字符、新增字符可以表示成dp[i-1][j], dp[i][j-1]，因此两个字符不等时的表达式为dp[i][j]=min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
数学题
余数
- (medium)https://leetcode.com/problems/divide-two-integers/
这题有两种思路，比如要得到a除以b的商的话：
一种可以是每次加一个b，直到超过a再停下来；
或者利用位操作每次给b=b<<1，直到b超过a再停下来，然后每次a减去b，并累计减了多少个b。