LeetCode刷题指南 - 算法必读篇
以下内容学习labuladong 的算法笔记时，所做的笔记记录，仅供学习使用感谢。
一、算法必读篇
一、框架
数组遍历框架，典型的线性迭代结构：
void traverse(int[] arr) {
for (int i = 0; i < arr.length; i++) {
// 迭代访问 arr[i]
}
}
链表遍历框架，兼具迭代和递归结构：
/* 基本的单链表节点 */
class ListNode {
int val;
ListNode next;
}
void traverse(ListNode head) {
for (ListNode p = head; p != null; p = p.next) {
// 迭代访问 p.val
}
}
void traverse(ListNode head) {
// 递归访问 head.val
traverse(head.next)
}
二叉树遍历框架，典型的非线性递归遍历结构：
/* 基本的二叉树节点 */
class TreeNode {
int val;
TreeNode left, right;
}
void traverse(TreeNode root) {
traverse(root.left)
traverse(root.right)
}
你看二叉树的递归遍历方式和链表的递归遍历方式，相似不？再看看二叉树结构和单链表结构，相似不？如果再多几条叉，N 叉树你会不会遍历？
二叉树框架可以扩展为 N 叉树的遍历框架：
/* 基本的 N 叉树节点 */
class TreeNode {
int val;
TreeNode[] children;
}
void traverse(TreeNode root) {
for (TreeNode child : root.children)
traverse(child)
}
N 叉树的遍历又可以扩展为图的遍历，因为图就是好几 N 叉棵树的结合体。你说图是可能出现环的？这个很好办，用个布尔数组 visited 做标记就行了，这里就不写代码了。
比如 N 皇后问题吧，主要代码如下：
void backtrack(int[] nums, LinkedList<Integer> track) {
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
if (track.contains(nums[i]))
continue;
track.add(nums[i]);
// 进入下一层决策树
backtrack(nums, track);
track.removeLast();
}
/* 提取出 N 叉树遍历框架 */
void backtrack(int[] nums, LinkedList<Integer> track) {
for (int i = 0; i < nums.length; i++) {
backtrack(nums, track);
}
二、动态规划
求解动态规划的核心问题是穷举。重叠子问题、最优子结构、状态转移方程就是动态规划三要素。
状态转移方程：明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。
斐波那契数列
1、暴力递归（重叠子问题）
斐波那契数列的数学形式就是递归的，写成代码就是这样：
int fib(int N) {
if (N == 1 || N == 2) return 1;
return fib(N - 1) + fib(N - 2);
}
这个不用多说了，学校老师讲递归的时候似乎都是拿这个举例。我们也知道这样写代码虽然简洁易懂，但是十分低效，低效在哪里？假设 n = 20，请画出递归树。
PS：但凡遇到需要递归的问题，最好都画出递归树，这对你分析算法的复杂度，寻找算法低效的原因都有巨大帮助。
这个递归树怎么理解？就是说想要计算原问题f(20)，我就得先计算出子问题f(19)和f(18)，然后要计算f(19)，我就要先算出子问题f(18)和f(17)，以此类推。最后遇到f(1)或者f(2)的时候，结果已知，就能直接返回结果，递归树不再向下生长了。
递归算法的时间复杂度怎么计算？子问题个数乘以解决一个子问题需要的时间。
子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)。
解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)。
所以，这个算法的时间复杂度为 O(2^n)，指数级别，爆炸。
观察递归树，很明显发现了算法低效的原因：存在大量重复计算，比如f(18)被计算了两次，而且你可以看到，以f(18)为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间。更何况，还不止f(18)这一个节点被重复计算，所以这个算法及其低效。
这就是动态规划问题的第一个性质：重叠子问题。下面，我们想办法解决这个问题。
2、带备忘录的递归解法
明确了问题，其实就已经把问题解决了一半。即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。
一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。
int fib(int N) {
if (N < 1) return 0;
// 备忘录全初始化为 0
int memo[] = new int[n + 1];
// 初始化最简情况
return helper(memo, N);
}
int helper(int[] memo, int n) {
// base case
if (n < 2) return n;
// 已经计算过
if (memo[n] != 0) return memo[n];
memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
return memo[n];
}
class Solution {
int store[]=new int[31];
public int fib(int N) {
if(N==0||N==1) return N;
if(store[N]!=0) return store[N];
return store[N]=fib(N-1)+fib(N-2);
}
}
现在，画出递归树，你就知道「备忘录」到底做了什么：
实际上，带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。
**递归算法的时间复杂度怎么算？**子问题个数乘以解决一个子问题需要的时间。
子问题个数，即图中节点的总数，由于本算法不存在冗余计算，子问题就是f(1),f(2),f(3)…f(20)，数量和输入规模 n = 20 成正比，所以子问题个数为 O(n)。
解决一个子问题的时间，同上，没有什么循环，时间为 O(1)。
所以，本算法的时间复杂度是 O(n)。比起暴力算法，是降维打击。
至此，带备忘录的递归解法的效率已经和迭代的动态规划一样了。实际上，这种解法和迭代的动态规划思想已经差不多，只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」。
**啥叫「自顶向下」？**注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说f(20)，向下逐渐分解规模，直到f(1)和f(2)触底，然后逐层返回答案，这就叫「自顶向下」。
**啥叫「自底向上」？**反过来，我们直接从最底下，最简单，问题规模最小的f(1)和f(2)开始往上推，直到推到我们想要的答案f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。
3、dp 数组的迭代解法
有了上一步「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一张表，就叫做 DP table 吧，在这张表上完成「自底向上」的推算岂不美哉！
int fib(int N) {
vector<int> dp(N + 1, 0);
// base case
dp[1] = dp[2] = 1;
for (int i = 3; i <= N; i++)
dp[i] = dp[i - 1] + dp[i - 2];
return dp[N];
}
class Solution {
public int fib(int n) {
int dp[] = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++)
dp[i] = dp[i - 1] + dp[i - 2];
return dp[n];
}
}
画个图就很好理解了，而且你发现这个 DP table 特别像之前那个「剪枝」后的结果，只是反过来算而已。实际上，带备忘录的递归解法中的「备忘录」，最终完成后就是这个 DP table，所以说这两种解法其实是差不多的，大部分情况下，效率也基本相同。
这里，引出「状态转移方程」这个名词，实际上就是描述问题结构的数学形式：
为啥叫「状态转移方程」？为了听起来高端。你把 f(n) 想做一个状态 n，这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来，这就叫状态转移，仅此而已。
你会发现，上面的几种解法中的所有操作，例如 return f(n - 1) + f(n - 2)，dp[i] = dp[i - 1] + dp[i - 2]，以及对备忘录或 DP table 的初始化操作，都是围绕这个方程式的不同表现形式。可见列出「状态转移方程」的重要性，它是解决问题的核心。很容易发现，其实状态转移方程直接代表着暴力解法。
千万不要看不起暴力解，动态规划问题最困难的就是写出状态转移方程，即这个暴力解。优化方法无非是用备忘录或者 DP table，再无奥妙可言。
这个例子的最后，讲一个细节优化。细心的读者会发现，根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：
int fib(int n) {
if (n == 2 || n == 1)
return 1;
int prev = 1, curr = 1;
for (int i = 3; i <= n; i++) {
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}
有人会问，动态规划的另一个重要特性「最优子结构」，怎么没有涉及？下面会涉及。斐波那契数列的例子严格来说不算动态规划，因为没有涉及求最值，以上旨在演示算法设计螺旋上升的过程。
凑零钱问题
先看下题目：给你k种面值的硬币，面值分别为c1, c2 ... ck，每种硬币的数量无限，再给一个总金额amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。算法的函数签名如下：
// coins 中是可选硬币面值，amount 是目标金额
int coinChange(int[] coins, int amount);
比如说k = 3，面值分别为 1，2，5，总金额amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。
你认为计算机应该如何解决这个问题？显然，就是把所有肯能的凑硬币方法都穷举出来，然后找找看最少需要多少枚硬币。
1、暴力递归
首先，这个问题是动态规划问题，因为它具有「最优子结构」。要符合「最优子结构」，子问题间必须互相独立。啥叫相互独立？你肯定不想看数学证明，我用一个直观的例子来讲解。
比如说，你的原问题是考出最高的总成绩，那么你的子问题就是要把语文考到最高，数学考到最高…… 为了每门课考到最高，你要把每门课相应的选择题分数拿到最高，填空题分数拿到最高…… 当然，最终就是你每门课都是满分，这就是最高的总成绩。
得到了正确的结果：最高的总成绩就是总分。因为这个过程符合最优子结构，“每门科目考到最高”这些子问题是互相独立，互不干扰的。
但是，如果加一个条件：你的语文成绩和数学成绩会互相制约，此消彼长。这样的话，显然你能考到的最高总成绩就达不到总分了，按刚才那个思路就会得到错误的结果。因为子问题并不独立，语文数学成绩无法同时最优，所以最优子结构被破坏。
回到凑零钱问题，为什么说它符合最优子结构呢？比如你想求amount = 11时的最少硬币数（原问题），如果你知道凑出amount = 10的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1 的硬币）就是原问题的答案，因为硬币的数量是没有限制的，子问题之间没有相互制，是互相独立的。
那么，既然知道了这是个动态规划问题，就要思考如何列出正确的状态转移方程。
先确定「状态」，也就是原问题和子问题中变化的变量。由于硬币数量无限，所以唯一的状态就是目标金额amount。
然后确定dp函数的定义：函数 dp(n)表示，当前的目标金额是n，至少需要dp(n)个硬币凑出该金额。
然后确定「选择」并择优，也就是对于每个状态，可以做出什么选择改变当前状态。具体到这个问题，无论当的目标金额是多少，选择就是从面额列表coins中选择一个硬币，然后目标金额就会减少：
# 伪码框架
def coinChange(coins: List[int], amount: int):
# 定义：要凑出金额 n，至少要 dp(n) 个硬币
def dp(n):
# 做选择，需要硬币最少的那个结果就是答案
for coin in coins:
res = min(res, 1 + dp(n - coin))
return res
# 我们要求目标金额是 amount
return dp(amount)
最后明确 base case，显然目标金额为 0 时，所需硬币数量为 0；当目标金额小于 0 时，无解，返回 -1：
class Solution {
//纯递归，超时
public int coinChange(int[] coins, int amount) {
return result(coins,amount,0);
}
//减少数组下标为i的硬币值后，子问题的最优解，最终答案为子问题最优解+1
public int result(int[] coins,int amount,int index){
if(amount==0) return 0;
if(amount<0) return -1;
int min = Integer.MAX_VALUE; //amount减少一个硬币后，硬币个数最少（最优解为min+1）
for(int i = 0;i<coins.length;i++){
int cur = result(coins, amount-coins[i],i);//递归求依次减少值为coin[i]的硬币后，每个子问题的最优解
//如果值为-1，暂时先不考虑
if(cur==-1){
continue;
}
//求当前所有子问题最优解中，需要硬币个数最少的
if(cur < min ){
min = cur;
}
}
//如果此时，最小值仍为初始值，证明当前问题无最优解，返回-1
if(min == Integer.MAX_VALUE){
return -1;
}
else //否则，返回子问题中，硬币最少的最优解
return min+1;
}
}
至此，状态转移方程其实已经完成了，以上算法已经是暴力解法了，以上代码的数学形式就是状态转移方程：
至此，这个问题其实就解决了，只不过需要消除一下重叠子问题，比如amount = 11, coins = {1,2,5}时画出递归树看看：
时间复杂度分析：子问题总数 x 解决每个子问题的时间。
子问题总数为递归树节点个数，这个比较难看出来，是 O(n^k)，总之是指数级别的。每个子问题中含有一个 for 循环，复杂度为 O(k)。所以总时间复杂度为 O(k * n^k)，指数级别。
2、带备忘录的递归
只需要稍加修改，就可以通过备忘录消除子问题：
class Solution {
public int coinChange(int[] coins, int amount) {
//面值<1时，需要0个硬币
if(amount<1)
return 0;
return result(coins,amount, new int[amount+1]);
}
public int result(int[] coins,int amount,int[] array){ //array[]备忘录
//总数为0，返回0个硬币
if(amount==0) return 0;
if(amount<0) return -1;
if(array[amount]!=0) return array[amount];//如果备忘录中有当前值，找到它
int min = Integer.MAX_VALUE; //amount减少一个硬币后，硬币个数最少（最优解）
for(int i = 0;i<coins.length;i++){
int cur = result(coins, amount-coins[i],array);//子问题
if(cur==-1){
continue;
}
if(cur < min&&cur>=0){
min = cur;
}
}
if(min == Integer.MAX_VALUE)
array[amount]=-1;
else
array[amount]=min+1;
return array[amount];
}
}
不画图了，很显然「备忘录」大大减小了子问题数目，完全消除了子问题的冗余，所以子问题总数不会超过金额数 n，即子问题数目为 O(n)。处理一个子问题的时间不变，仍是 O(k)，所以总的时间复杂度是 O(kn)。
3、dp 数组的迭代解法
当然，我们也可以自底向上使用 dp table 来消除重叠子问题，dp数组的定义和刚才dp函数类似，定义也是一样的：
dp[i] = x表示，当目标金额为i时，至少需要x枚硬币。
class Solution {
public int coinChange(int[] coins, int amount) {
//dp[i]表示，当目标金额为i时，至少需要dp[i]枚硬币凑出
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);//dp[]={amount+1,amount+1,amount+1,amount+1...}
//base case
dp[0] = 0;
//遍历所有状态amount
for(int i = 1; i <= amount; ++ i) {
//遍历所有面额的硬币
for(int coin : coins) {
if(i - coin < 0) continue;
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return (dp[amount] == amount + 1) ? -1 : dp[amount];
//dp[0]==0+1,就取值-1
}
}
PS：为啥dp数组初始化为amount + 1呢，因为凑成amount金额的硬币数最多只可能等于amount（全用 1 元面值的硬币），所以初始化为amount + 1就相当于初始化为正无穷，便于后续取最小值。
总结：备忘录、DP table 就是在追求“如何聪明地穷举”。用空间换时间的思路，是降低时间复杂度的不二法门，除此之外，试问，还能玩出啥花活？
三、回溯算法
解决一个回溯问题，实际上就是一个决策树的遍历过程。— DFS算法就是一种回溯算法
你只需要思考 3 个问题：
1、 路径 ：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
如果你不理解这三个词语的解释，没关系，我们后面会用「全排列」和「N 皇后问题」这两个经典的回溯算法问题来帮你理解这些词语是什么意思，现在你先留着印象。
代码方面，回溯算法的框架：
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
# 做选择
将该选择从选择列表移除
路径.add(选择)
backtrack(路径, 选择列表)
# 撤销选择
路径.remove(选择)
将该选择再加入选择列表
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」.
全排列问题
代码：
List<List<Integer>> res = new LinkedList<>();
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
// 记录「路径」
LinkedList<Integer> track = new LinkedList<>();
backtrack(nums, track);
return res;
}
// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList<Integer> track) {
// 触发结束条件
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
// 排除不合法的选择
if (track.contains(nums[i]))
continue;
// 做选择
track.add(nums[i]);
// 进入下一层决策树
backtrack(nums, track);
// 取消选择
track.removeLast();
}
}
我们这里稍微做了些变通，没有显式记录「选择列表」，而是通过nums和track推导出当前的选择列表：
N 皇后问题
这个问题很经典了，简单解释一下：给你一个 N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击。
PS：皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。
这是 N = 8 的一种放置方法：
图片来自 LeetCode
这个问题本质上跟全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。
直接套用框架:
//vector<string> 类似char[][]
vector<vector<string>> res;
/* 输入棋盘边长 n，返回所有合法的放置 */
vector<vector<string>> solveNQueens(int n) {
// '.' 表示空，'Q' 表示皇后，初始化空棋盘。
vector<string> board(n, string(n, '.'));
backtrack(board, 0);
return res;
}
// 路径：board 中小于 row 的那些行都已经成功放置了皇后
// 选择列表：第 row 行的所有列都是放置皇后的选择
// 结束条件：row 超过 board 的最后一行
void backtrack(vector<string>& board, int row) {
// 触发结束条件
if (row == board.size()) {
res.push_back(board);
return;
}
int n = board[row].size();
for (int col = 0; col < n; col++) {
// 排除不合法选择
if (!isValid(board, row, col))
continue;
// 做选择
board[row][col] = 'Q';
// 进入下一行决策
backtrack(board, row + 1);
// 撤销选择
board[row][col] = '.';
}
}
这部分主要代码，跟全排列问题差不多。isValid函数的实现也很简单：
/* 是否可以在 board[row][col] 放置皇后？ */
bool isValid(vector<string>& board, int row, int col) {
int n = board.size();
// 检查列是否有皇后互相冲突
for (int i = 0; i < n; i++) {
if (board[i][col] == 'Q')
return false;
}
// 检查右上方是否有皇后互相冲突
for (int i = row - 1, j = col + 1;
i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q')
return false;
}
// 检查左上方是否有皇后互相冲突
for (int i = row - 1, j = col - 1;
i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q')
return false;
}
return true;
}
函数backtrack依然像个在决策树上游走的指针，每个节点就表示在board[row][col]上放置皇后，通过isValid函数可以将不符合条件的情况剪枝：
如果直接给你这么一大段解法代码，可能是懵逼的。但是现在明白了回溯算法的框架套路，还有啥难理解的呢？无非是改改做选择的方式，排除不合法选择的方式而已，只要框架存于心，你面对的只剩下小问题了。
当N = 8时，就是八皇后问题，数学大佬高斯穷尽一生都没有数清楚八皇后问题到底有几种可能的放置方法，但是我们的算法只需要一秒就可以算出来所有可能的结果。
不过真的不怪高斯。这个问题的复杂度确实非常高，看看我们的决策树，虽然有isValid函数剪枝，但是最坏时间复杂度仍然是 O(N^(N+1))，而且无法优化。如果N = 10的时候，计算就已经很耗时了。
有的时候，我们并不想得到所有合法的答案，只想要一个答案，怎么办呢？比如解数独的算法，找所有解法复杂度太高，只要找到一种解法就可以。
其实特别简单，只要稍微修改一下回溯算法的代码即可：
// 函数找到一个答案后就返回 true
bool backtrack(vector<string>& board, int row) {
// 触发结束条件
if (row == board.size()) {
res.push_back(board);
return true;
}
...
for (int col = 0; col < n; col++) {
...
board[row][col] = 'Q';
if (backtrack(board, row + 1))
return true;
board[row][col] = '.';
}
return false;
}
这样修改后，只要找到一个答案，for 循环的后续递归穷举都会被阻断。也许你可以在 N 皇后问题的代码框架上，稍加修改，写一个解数独的算法？
java代码：
class Solution {
List<List<String>> res = new ArrayList<>();
List<List<String>> solveNQueens(int n) {
char[][] board = new char[n][n];
for(char[] c : board){
Arrays.fill(c, '.');
}
backtrack(board, 0);
return res;
}
void backtrack(char[][] board, int row) {
if (row == board.length) {
res.add(Array2List(board));
return;
}
int n = board.length;
for (int col = 0; col < n; col++) {
if (!isValid(board, row, col)) {
continue;
}
board[row][col] = 'Q';
backtrack(board, row + 1);
board[row][col] = '.';
}
}
public List Array2List(char[][] board) {
List<String> list = new ArrayList<>();
for (char[] c : board) {
list.add(String.copyValueOf(c));
}
return list;
}
boolean isValid(char[][] board, int row, int col) {
int n = board.length;
// 左右上下
for (int i = 0; i < n; i++) {
if (board[i][col] == 'Q' || board[row][i] == 'Q')
return false;
}
// 右上
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q')
return false;
}
// 右下
for (int i = row + 1, j = col + 1; i < n && j < n; i++, j++) {
if (board[i][j] == 'Q')
return false;
}
// 左上
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q')
return false;
}
// 左下
for (int i = row + 1, j = col - 1; i < n && j >= 0; i++, j--) {
if (board[i][j] == 'Q')
return false;
}
return true;
}
}
四、BFS算法
-
我们写 BFS 算法都是用「队列」这种数据结构，每次将一个节点周围的所有节点加入队列。
-
BFS 相对 DFS 的最主要的区别是：BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多。本质上就是一幅「图」，让你从一个起点，走到终点，问最短路径。这就是 BFS 的本质
-
DFS 实际上是靠递归的堆栈记录走过的路径，你要找到最短路径，肯定得把二叉树中所有树杈都探索完才能对比出最短的路径有多长对不对？而 BFS 借助队列做到一次一步「齐头并进」，是可以在不遍历完整棵树的条件下找到最短距离的。形象点说，DFS 是线，BFS 是面；DFS 是单打独斗，BFS 是集体行动。这个应该比较容易理解吧。
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
Queue<Node> q; // 核心数据结构
Set<Node> visited; // 避免走回头路
q.offer(start); // 将起点加入队列
visited.add(start);
int step = 0; // 记录扩散的步数
while (q not empty) {
int sz = q.size();
/* 将当前队列中的所有节点向四周扩散 */
for (int i = 0; i < sz; i++) {
Node cur = q.poll();
/* 划重点：这里判断是否到达终点 */
if (cur is target)
return step;
/* 将 cur 的相邻节点加入队列 */
for (Node x : cur.adj())
if (x not in visited) {
q.offer(x);
visited.add(x);
}
}
/* 划重点：更新步数在这里 */
step++;
}
}
队列q就不说了，BFS 的核心数据结构；cur.adj()泛指cur相邻的节点，比如说二维数组中，cur上下左右四面的位置就是相邻节点；visited的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要visited。
BFS加强版就是Dijkstra,都是二叉树的层序遍历衍生的。
求二叉树的高度：
int minDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
// root 本身就是一层，depth 初始化为 1
int depth = 1;
while (!q.isEmpty()) {
int sz = q.size();
/* 将当前队列中的所有节点向四周扩散 */
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
/* 判断是否到达终点 */
if (cur.left == null && cur.right == null)
return depth;
/* 将 cur 的相邻节点加入队列 */
if (cur.left != null)
q.offer(cur.left);
if (cur.right != null)
q.offer(cur.right);
}
/* 这里增加步数 */
depth++;
}
return depth;
}
五、单链表的6大套路
利用快慢指针
1.合并两个有序链表
对应力扣21题
我们的 while 循环每次比较p1和p2的大小，把较小的节点接到结果链表上：
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 虚拟头结点
ListNode dummy = new ListNode(-1), p = dummy;
ListNode p1 = l1, p2 = l2;
while (p1 != null && p2 != null) {
// 比较 p1 和 p2 两个指针
// 将值较小的的节点接到 p 指针
if (p1.val > p2.val) {
p.next = p2;
p2 = p2.next;
} else {
p.next = p1;
p1 = p1.next;
}
// p 指针不断前进
p = p.next;
}
if (p1 != null) {
p.next = p1;
}
if (p2 != null) {
p.next = p2;
}
return dummy.next;
}
2.合并K个升序链表
对应力扣23题
这里我们就要用到 优先级队列（二叉堆） 这种数据结构，把链表节点放入一个最小堆，就可以每次获得k个节点中的最小节点：
ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
// 虚拟头结点
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
// 优先级队列，最小堆
PriorityQueue<ListNode> pq = new PriorityQueue<>(
lists.length, (a, b)->(a.val - b.val));
// 将 k 个链表的头结点加入最小堆
for (ListNode head : lists) {
if (head != null)
pq.add(head);
}
while (!pq.isEmpty()) {
// 获取最小节点，接到结果链表中
ListNode node = pq.poll();
p.next = node;
if (node.next != null) {
pq.add(node.next);
}
// p 指针不断前进
p = p.next;
}
return dummy.next;
}
优先队列pq中的元素个数最多是k，所以一次poll或者add方法的时间复杂度是O(logk)；所有的链表节点都会被加入和弹出pq，所以算法整体的时间复杂度是O(Nlogk)，其中k是链表的条数，N是这些链表的节点总数。
3.单链表的倒数第 k 个节点
对应力扣19题
// 主函数
public ListNode removeNthFromEnd(ListNode head, int n) {
// 虚拟头节点
ListNode dummy = new ListNode(-1);
dummy.next = head;
// 删除倒数第 n 个，要先找倒数第 n + 1 个节点
ListNode x = findFromEnd(dummy, n + 1);
// 删掉倒数第 n 个节点
x.next = x.next.next;
return dummy.next;
}
// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
ListNode p1 = head;
// p1 先走 k 步
for (int i = 0; i < k; i++) {
p1 = p1.next;
}
ListNode p2 = head;
// p1 和 p2 同时走 n - k 步
while (p1 != null) {
p2 = p2.next;
p1 = p1.next;
}
// p2 现在指向第 n - k 个节点
return p2;
}
4.寻找单链表的中点
对应力扣876题，使用「快慢指针」,想一次遍历就得到中间节点
我们让两个指针slow和fast分别指向链表头结点head。
每当慢指针slow前进一步，快指针fast就前进两步，这样，当fast走到链表末尾时，slow就指向了链表中点。
ListNode middleNode(ListNode head) {
// 快慢指针初始化指向 head
ListNode slow = head, fast = head;
// 快指针走到末尾时停止
while (fast != null && fast.next != null) {
// 慢指针走一步，快指针走两步
slow = slow.next;
fast = fast.next.next;
}
// 慢指针指向中点
return slow;
}
5.判断单链表是否包含环并找出环起点
对应力扣141,142题
判断单链表是否包含环属于经典问题了，解决方案也是用快慢指针：
每当慢指针slow前进一步，快指针fast就前进两步。
如果fast最终遇到空指针，说明链表中没有环；如果fast最终和slow相遇，那肯定是fast超过了slow一圈，说明链表中含有环。
boolean hasCycle(ListNode head) {
// 快慢指针初始化指向 head
ListNode slow = head, fast = head;
// 快指针走到末尾时停止
while (fast != null && fast.next != null) {
// 慢指针走一步，快指针走两步
slow = slow.next;
fast = fast.next.next;
// 快慢指针相遇，说明含有环
if (slow == fast) {
return true;
}
}
// 不包含环
return false;
}
当然，这个问题还有进阶版：如果链表中含有环，如何计算这个环的起点？
ListNode detectCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
// 上面的代码类似 hasCycle 函数
if (fast == null || fast.next == null) {
// fast 遇到空指针说明没有环
return null;
}
// 重新指向头结点
slow = head;
// 快慢指针同步前进，相交点就是环起点
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
6.判断两个单链表是否相交并找出交点
对应力扣160题
所以，解决这个问题的关键是，通过某些方式，让p1和p2能够同时到达相交节点c1。
所以，我们可以让p1遍历完链表A之后开始遍历链表B，让p2遍历完链表B之后开始遍历链表A，这样相当于「逻辑上」两条链表接在了一起。
如果这样进行拼接，就可以让p1和p2同时进入公共部分，也就是同时到达相交节点c1：
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// p1 指向 A 链表头结点，p2 指向 B 链表头结点
ListNode p1 = headA, p2 = headB;
while (p1 != p2) {
// p1 走一步，如果走到 A 链表末尾，转到 B 链表
if (p1 == null) p1 = headB;
else p1 = p1.next;
// p2 走一步，如果走到 B 链表末尾，转到 A 链表
if (p2 == null) p2 = headA;
else p2 = p2.next;
}
return p1;
}
六、二分查找
利用左右指针
1.查找一个数
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}
2.查找左侧边界
写法1：
int left_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length; // 注意
while (left < right) { // 注意
int mid = (left + right) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // 注意
}
}
return left;
}
写法2：
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 搜索区间为 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
// 搜索区间变为 [mid+1, right]
left = mid + 1;
} else if (nums[mid] > target) {
// 搜索区间变为 [left, mid-1]
right = mid - 1;
} else if (nums[mid] == target) {
// 收缩右侧边界
right = mid - 1;
}
}
// 检查出界情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
3.查找右侧边界
写法1：
int right_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0, right = nums.length;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left - 1; // 注意
}
写法2：
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 这里改成收缩左侧边界即可
left = mid + 1;
}
}
// 这里改为检查 right 越界的情况，见下图
if (right < 0 || nums[right] != target)
return -1;
return right;
}
4.总结
我们还根据逻辑将「搜索区间」全都统一成了两端都闭，便于记忆，只要修改两处即可变化出三种写法：
int binary_search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if(nums[mid] == target) {
// 直接返回
return mid;
}
}
// 直接返回
return -1;
}
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回，锁定左侧边界
right = mid - 1;
}
}
// 最后要检查 left 越界的情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回，锁定右侧边界
left = mid + 1;
}
}
// 最后要检查 right 越界的情况
if (right < 0 || nums[right] != target)
return -1;
return right;
}
七、滑动窗口
滑动窗口算法框架 (左右指针)
/* 滑动窗口算法框架 (左右指针)*/
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
76 .最小覆盖子串问题
就是说要在S(source) 中找到包含T(target) 中全部字母的一个子串，且这个子串一定是所有可能子串中最短的。
如果我们使用暴力解法，代码大概是这样的：
for (int i = 0; i < s.size(); i++)
for (int j = i + 1; j < s.size(); j++)
if s[i:j] 包含 t 的所有字母:
更新答案
思路很直接，但是显然，这个算法的复杂度肯定大于 O(N^2) 了，不好。
滑动窗口算法的思路是这样：
***1、***我们在字符串S中使用双指针中的左右指针技巧，初始化left = right = 0，把索引左闭右开区间[left, right)称为一个「窗口」。
***2、***我们先不断地增加right指针扩大窗口[left, right)，直到窗口中的字符串符合要求（包含了T中的所有字符）。
***3、***此时，我们停止增加right，转而不断增加left指针缩小窗口[left, right)，直到窗口中的字符串不再符合要求（不包含T中的所有字符了）。同时，每次增加left，我们都要更新一轮结果。
***4、***重复第 2 和第 3 步，直到right到达字符串S的尽头。
这个思路其实也不难，**第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，**也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。
下面画图理解一下，needs和window相当于计数器，分别记录T中字符出现次数和「窗口」中的相应字符的出现次数。
初始状态：
增加right，直到窗口[left, right)包含了T中所有字符：
现在开始增加left，缩小窗口[left, right)。
直到窗口中的字符串不再符合要求，left不再继续移动。
之后重复上述过程，先移动right，再移动left…… 直到right指针到达字符串S的末端，算法结束。
现在开始套模板，只需要思考以下四个问题：
**1、**当移动right扩大窗口，即加入字符时，应该更新哪些数据？
**2、**什么条件下，窗口应该暂停扩大，开始移动left缩小窗口？
**3、**当移动left缩小窗口，即移出字符时，应该更新哪些数据？
**4、**我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
如果一个字符进入窗口，应该增加window计数器；如果一个字符将移出窗口的时候，应该减少window计数器；当valid满足need时应该收缩窗口；应该在收缩窗口的时候更新最终结果。
public static String minWindow(String s, String t) { //从s中找t
HashMap<Character,Integer> need = new HashMap<>();
HashMap<Character,Integer> window = new HashMap<>();
for (char ch : t.toCharArray()){
need.put(ch,need.getOrDefault(ch,0)+1);//need所有的赋值为1，window所有值为0
}
int left=0,right=0,valid=0;
int start=0,len=Integer.MAX_VALUE;
while(right < s.length()){
//将c移入窗口
char c=s.charAt(right);
right++;
// 进行窗口内数据的一系列更新
if(need.containsKey(c)){
window.put(c,window.getOrDefault(c,0)+1); //将窗口的值+1
if(need.get(c).equals(window.get(c))){
valid++;
}
}
//是否收缩,当有效值达到t的长度，就开始收缩
while(valid == t.length()){
if(right - left <len){
start=left;
len=right-left;
}
char d=s.charAt(left);
left++;
//将d从窗口移除
//更新数据
if(need.containsKey(d)){
if(need.get(d).equals(window.get(d))){
valid--;
}
window.put(d,window.getOrDefault(d,0)-1); //将窗口的值-1
}
}
}
// 返回最小覆盖子串
return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len);
}
567.字符串排列
对于这道题的解法代码，基本上和最小覆盖子串一模一样，只需要改变两个地方：
**1、**本题移动left缩小窗口的时机是窗口大小大于t.size()时，因为排列嘛，显然长度应该是一样的。
**2、**当发现valid == need.size()时，就说明窗口中就是一个合法的排列，所以立即返回true。
Map.getOrDefault(key，默认值)；
Map中会存储一一对应的key和value。
如果 在Map中存在key，则返回key所对应的的value。
如果 在Map中不存在key，则返回默认值。
java代码
public boolean checkInclusion(String s1, String s2) {
HashMap<Character,Integer> need = new HashMap<>();
HashMap<Character,Integer> window = new HashMap<>();
for(char ch:s1.toCharArray()){
need.put(ch,need.getOrDefault(ch,0)+1); //key: A value:1, 代表字符出现次数1
}
int left = 0,right = 0,valid = 0;
//滑动窗口主体
while (right < s2.length()){
char c = s2.charAt(right);
right++;
// 进行窗口内数据的一系列更新
if(need.containsKey(c)){
window.put(c,window.getOrDefault(c,0)+1);
if(window.get(c).equals(need.get(c))){
valid++;
}
}
// 判断左侧窗口是否要收缩
while (right - left >= s1.length()){
char d = s2.charAt(left);
left++;
// 在这里判断是否找到了合法的子串
if(valid == need.size()){
return true;
}
// 进行窗口内数据的一系列更新
if(need.containsKey(d)){
if(window.get(d).equals(need.get(d))){
valid--;
}
window.put(d,window.getOrDefault(d,0)-1);
}
}
}
// 未找到符合条件的子串
return false;
}
八、股票问题
动态规划
把上面的状态转移方程总结一下：
九、nSum函数问题
无序数组
**考虑使用HashMap 或者 HashSet 也可以帮助我们处理。**比如力扣第1题，返回索引。
Two Sum 系列问题就是想教我们如何使用哈希表处理问题
class TwoSum {
// 向数据结构中添加一个数 number
public void add(int number);
// 寻找当前数据结构中是否存在两个数的和为 value
public boolean find(int value);
}
进行find的时候有两种情况，举个例子：
情况一：如果连续 add 了 [3,2,3,5]，那么freq是{3:2,2:1,5:1}，执行find(6)，由于 3 出现了两次，3 + 3 = 6，所以返回 true。
情况二：freq是{3:2,2:1,5:1}，执行find(7)，那么key为 2，other为 5 时算法可以返回 true。
除了上述两种情况外，find只能返回 false 了。
对于这个解法的时间复杂度呢，add方法是 O(1)，find方法是 O(N)，空间复杂度为 O(N)，和上一道题目比较类似。
但是对于 API 的设计，是需要考虑现实情况的。比如说，我们设计的这个类，使用find方法非常频繁，那么每次都要 O(N) 的时间，岂不是很浪费费时间吗？对于这种情况，我们是否可以做些优化呢？
是的，对于频繁使用find方法的场景，我们可以进行优化。我们可以参考上一道题目的暴力解法，借助哈希集合来针对性优化find方法：
这样sum中就储存了所有加入数字可能组成的和，每次find只要花费 O(1) 的时间在集合中判断一下是否存在就行了，显然非常适合频繁使用find的场景。
有序数组
考虑使用左右指针技巧
如果假设输入一个数组 nums 和一个目标和 target，请你返回 nums 中能够凑出 target 的两个元素的值，比如输入 nums = [5,3,1,6], target = 9，那么算法返回两个元素 [3,6]。可以假设只有且仅有一对儿元素可以凑出 target。
vector<int> twoSum(vector<int>& nums, int target) {
// 先对数组排序
sort(nums.begin(), nums.end());
// 左右指针
int lo = 0, hi = nums.size() - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
// 根据 sum 和 target 的比较，移动左右指针
if (sum < target) {
lo++;
} else if (sum > target) {
hi--;
} else if (sum == target) {
return {nums[lo], nums[hi]};
}
}
return {};
}
比如说 nums = [1,1,1,2,2,3,3], target = 4，得到的结果中 [1,3] 肯定会重复。
出问题的地方在于 sum == target 条件的 if 分支，当给 res 加入一次结果后，lo 和 hi 不应该改变 1 的同时，还应该跳过所有重复的元素：
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int target) {
ArrayList<Integer> list=new ArrayList<>();
if(array==null|| array.length==0)
return list;
int lo=0,hi=array.length-1;
while(lo<hi){
int sum = array[lo]+array[hi];
if(sum<target){
lo++;
}else if(sum>target){
hi--;
}else if(sum==target){
list.add(array[lo]);
list.add(array[hi]);
return list;
}
}
return list;
}
}
现在我们想找和为 target 的三个数字，那么对于第一个数字，可能是什么？nums 中的每一个元素 nums[i] 都有可能！
那么，确定了第一个数字之后，剩下的两个数字可以是什么呢？其实就是和为 target - nums[i] 的两个数字呗，那不就是 twoSum 函数解决的问题么🤔
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
return nSumTarget(nums, 3, 0, 0);
}
public List<List<Integer>> nSumTarget( int[] nums, int n, int start, int target) {
int sz = nums.length;
List<List<Integer>> res=new ArrayList<List<Integer>>();
// 至少是 2Sum，且数组大小不应该小于 n
if (n < 2 || sz < n) return res;
// 2Sum 是 base case
if (n == 2) {
// 双指针那一套操作
int lo = start, hi = sz - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
int left = nums[lo], right = nums[hi];
if (sum < target) {
while (lo < hi && nums[lo] == left) lo++;
} else if (sum > target) {
while (lo < hi && nums[hi] == right) hi--;
} else {
res.add(Arrays.asList(nums[lo], nums[hi]));//该方法是将数组转化为list
while (lo < hi && nums[lo] == left) lo++;
while (lo < hi && nums[hi] == right) hi--;
}
}
} else {
// n > 2 时，递归计算 (n-1)Sum 的结果
for (int i = start; i < sz; i++) {
List<List<Integer>>
sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
for (List<Integer> arr : sub) {
// (n-1)Sum 加上 nums[i] 就是 nSum
List arr1 = new ArrayList(arr);
arr1.add(nums[i]);
res.add(arr1);
}
//第一个数不能重复
while (i < sz - 1 && nums[i] == nums[i + 1]) i++;
}
}
return res;
}
}
至此，3Sum 问题就解决了，时间复杂度不难算，排序的复杂度为 O(NlogN)，twoSumTarget 函数中的双指针操作为 O(N)，threeSumTarget 函数在 for 循环中调用 twoSumTarget 所以总的时间复杂度就是 O(NlogN + N^2) = O(N^2)。
总结：nSum框架（回溯法）
/* 注意：调用这个函数之前一定要先给 nums 排序 ，多少元组，直接修改n的数值就可以*/
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
return nSumTarget(nums, 4, 0, target);
}
public List<List<Integer>> nSumTarget( int[] nums, int n, int start, int target) {
int sz = nums.length;
List<List<Integer>> res=new ArrayList<List<Integer>>();
// 至少是 2Sum，且数组大小不应该小于 n
if (n < 2 || sz < n) return res;
// 2Sum 是 base case
if (n == 2) {
// 双指针那一套操作
int lo = start, hi = sz - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
int left = nums[lo], right = nums[hi];
if (sum < target) {
while (lo < hi && nums[lo] == left) lo++;
} else if (sum > target) {
while (lo < hi && nums[hi] == right) hi--;
} else {
res.add(Arrays.asList(nums[lo], nums[hi]));
while (lo < hi && nums[lo] == left) lo++;
while (lo < hi && nums[hi] == right) hi--;
}
}
} else {
// n > 2 时，递归计算 (n-1)Sum 的结果
for (int i = start; i < sz; i++) {
List<List<Integer>>
sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
for (List<Integer> arr : sub) {
// (n-1)Sum 加上 nums[i] 就是 nSum
List arr1 = new ArrayList(arr);
arr1.add(nums[i]);
res.add(arr1);
}
//第一个数不能重复
while (i < sz - 1 && nums[i] == nums[i + 1]) i++;
}
}
return res;
}
}
十、二叉树问题
/* 二叉树遍历框架 */
void traverse(TreeNode root) {
// 前序遍历
traverse(root.left)
// 中序遍历
traverse(root.right)
// 后序遍历
}
比如说我们的经典算法「快速排序」和「归并排序」，对于这两个算法，你有什么理解？如果你告诉我，快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后续遍历.
快速排序的代码框架如下：
void sort(int[] nums, int lo, int hi) {
/****** 前序遍历位置 ******/
// 通过交换元素构建分界点 p
int p = partition(nums, lo, hi);
/************************/
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}
归并排序的代码框架如下：
void sort(int[] nums, int lo, int hi) {
int mid = (lo + hi) / 2;
sort(nums, lo, mid);
sort(nums, mid + 1, hi);
/****** 后序遍历位置 ******/
// 合并两个排好序的子数组
merge(nums, lo, mid, hi);
/************************/
}
1.翻转二叉树
力扣第 226 题「翻转二叉树」
// 将整棵树的节点翻转
TreeNode invertTree(TreeNode root) {
// base case
if (root == null) {
return null;
}
/**** 前序遍历位置 ****/
// root 节点需要交换它的左右子节点
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
// 让左右子节点继续翻转它们的子节点
invertTree(root.left);
invertTree(root.right);
return root;
}
2.填充二叉树节点的右侧指针
力扣第 116 题
// 主函数
Node connect(Node root) {
if (root == null) return null;
connectTwoNode(root.left, root.right);
return root;
}
// 定义：输入两个节点，将它俩连接起来
void connectTwoNode(Node node1, Node node2) {
if (node1 == null || node2 == null) {
return;
}
/**** 前序遍历位置 ****/
// 将传入的两个节点连接
node1.next = node2;
// 连接相同父节点的两个子节点
connectTwoNode(node1.left, node1.right);
connectTwoNode(node2.left, node2.right);
// 连接跨越父节点的两个子节点
connectTwoNode(node1.right, node2.left);
}
3.将二叉树展开为链表
这是力扣第 114 题
给flatten函数输入一个节点root，那么以root为根的二叉树就会被拉平为一条链表。
我们再梳理一下，如何按题目要求把一棵树拉平成一条链表？很简单，以下流程：
1、将root的左子树和右子树拉平。
2、将root的右子树接到左子树下方，然后将整个左子树作为右子树。
// 定义：将以 root 为根的树拉平为链表
void flatten(TreeNode root) {
// base case
if (root == null) return;
flatten(root.left);
flatten(root.right);
/**** 后序遍历位置 ****/
// 1、左右子树已经被拉平成一条链表
TreeNode left = root.left;
TreeNode right = root.right;
// 2、将左子树作为右子树
root.left = null;
root.right = left;
// 3、将原先的右子树接到当前右子树的末端
TreeNode p = root;
while (p.right != null) {
p = p.right;
}
p.right = right;
}
十一、01背包问题
动态规划：状态+选择
框架如下，同股票问题
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 择优(选择1，选择2...)
第一步：要明确两点，「状态」和「选择」。 所以状态有两个，就是「背包的容量」和「可选择的物品」。选择就是「装进背包」或者「不装进背包」嘛。
第二步：要明确dp数组的定义。dp[i][w]的定义如下：对于前i个物品，当前背包的容量为w，这种情况下可以装的最大价值是dp[i][w]。如果 dp [3][5] = 6，其含义为：对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包容量为 5 时，最多可以装下的价值为 6。**根据这个定义，我们想求的最终答案就是dp[N][W]。base case 就是dp[0][..] = dp[..][0] = 0，因为没有物品或者背包没有空间的时候，能装的最大价值就是 0。
框架如下：
int dp[N+1][W+1]
dp[0][..] = 0
dp[..][0] = 0
for i in [1..N]:
for w in [1..W]:
dp[i][w] = max(
把物品 i 装进背包,
不把物品 i 装进背包
)
return dp[N][W]
第三步：根据「选择」，思考状态转移的逻辑。
dp[i][w]表示：对于前i个物品，当前背包的容量为w时，这种情况下可以装下的最大价值是dp[i][w]。
如果你没有把这第i个物品装入背包，那么很显然，最大价值dp[i][w]应该等于dp[i-1][w]。你不装嘛，那就继承之前的结果。
如果你把这第i个物品装入了背包，那么dp[i][w]应该等于dp[i-1][w-wt[i-1]] + val[i-1]。
首先，由于i是从 1 开始的，所以对val和wt的取值是i-1。
而dp[i-1][w-wt[i-1]]+ val[i-1]也很好理解：你如果想装第i个物品，你怎么计算这时候的最大价值？换句话说，在装第i个物品的前提下，背包能装的最大价值是多少？
显然，你应该寻求剩余重量w-wt[i-1]限制下能装的最大价值，加上第i个物品的价值val[i-1]，这就是装第i个物品的前提下，背包可以装的最大价值。
//伪代码：
for i in [1..N]:
for w in [1..W]:
dp[i][w] = max(
dp[i-1][w],
dp[i-1][w - wt[i-1]] + val[i-1]
)
return dp[N][W]
public int knapsack(int W, int N, int[] wt, int[] val) {
// vector 全填入 0，base case 已初始化
int dp[][]=new int[N+1][W+1];
// 背包重量为0的 dp[i][0]价值为0
for (int i = 0; i < wt.length; i++) {
dp[i][0] = 0;
}
for (int i = 1; i <= N; i++) {
for (int w = 1; w <= W; w++) {
if (w - wt[i-1] < 0) {
// 当前背包容量装不下，只能选择不装入背包
dp[i][w] = dp[i - 1][w];
} else {
/*1、拿：dp[i - 1][w - wt[i-1]]+value[i-1]，
寻求剩余重量w-wt[i-1]限制下能装的最大价值，加上第i个物品的价值val[i-1]*/
//2、不拿： dp[i - 1][w],还是和上个状态一样
dp[i][w] = Math.max(dp[i - 1][w - wt[i-1]] + val[i-1], dp[i - 1][w]);
}
}
}
return dp[N][W];
}
可以看看力扣416、1049、494、474、518、377、322、279、139