# 常考算法 ## 1 二叉树 ```cpp void traverse(TreeNode root){ //前序遍历 traverse(root.left); //中序遍历 traverse(root.rigth); //后序遍历 } ``` 1. 判断两棵二叉树是否相同 2. 判断 BST 的合法性注意不仅仅是比较左右节点，而是比较左右子树，这时候可以使用辅助函数，增加函数参数列表 3. 在 BST 中找一个数 ```cpp void BST(TreeNode root , int target){ if(root.val == target) //找到目标，做点什么 if(root.valtarget){ BST(root.left,target); } } } ``` 4. 在 BST 插入一个数 5. 在 BST 删除一个数去右子树找到一个最小的节点来接替自己的位置 6. 完全二叉树总节点数 = 倒数第二成以上的节点数+最后一层的节点数满二叉树和普通二叉树的结合题 ```cpp public int countNodes(TreeNode){ TreeNode l = root,r=root; int hl = 0,hr=0; while(l!=null){ l=l.left; hl++; } while(r!=null){ r = r.left; hr++; } if(hl == hr) //左右子树高度相等，证明是一棵满二叉树 { return (int)Math.pow(2,hl) - 1; } //如果左右高度不同，那就按普通二叉树计算 //只有一棵子树会递归下去，因为必定有一棵是满的 return 1+ countNodes(root.left)+countNodes(root.right); } ``` 7. 最近公共祖先二叉树的后序遍历，然后第一次相交就是这个 root ## 2 动态规划动态规划的一般形式就是求最值，比如最长递增子序列，最小编辑距离等。动态规划的核心就是`穷举`,因为要求最值，肯定要把所有可行的答案例举出来，然后就在其中找最值。递归算法的时间复杂度怎么算：子问题的个数 X 解决一个子问题所需的时间。记住，以后遇到求最值的问题，就要思考如何列举所有可能的结果。优化：因为动态规划问题存在重叠子问题，如果暴力穷举会造成效率极其低下，所以要用`备忘录`或者`DPtable`来优化穷举。动态规划三要素 - 重叠子问题 - 最优子结构 - 状态转移方程状态转移方程思考过程： 1. 这个问题的 base case 是什么？（最简单的情况） 2. 这个问题有什么状态？ 3. 对于每个状态可以做出什么样的选择来使状态发生改变。 4. 如果定义 dp 数组/函数的含义来表现`状态`和`选择`。框架： ```cpp //初始化base case dp[0][0][...] = base case; //进行状态转移 for 状态1 in 状态1所有的值 for 状态2 in 状态2所有的值 for... dp[状态1][状态2][...] = 求最值(选择1，选择2,...) ``` ### 解决重叠子问题经典例子：斐波那契数列严格来说，斐波那契数列不算动态规划问题，因为没有设计求最值的问题。 #### 暴力解法 ```cpp int fib(int N){ if(N==0) return 0; if(N==1||N==2) return 1; return fib(N-1)+fib(N-2); } ``` #### 带备忘录的递归解法(`自顶向下`) 递归时间长的原因使因为大量的重复计算，则这些计算很多是不必要的，所以我们可以建一个备忘录，每一次算出某个子问题的答案的时候别着急返回，先记录到备忘录中再返回。然后每次遇到一个子问题的时候，先别着急计算，而是先去备忘录那里找找，看之前有没有算过这个子问题，如果有那就直接拿出来用，而不要取耗时间计算了。一般用一个数组充当备忘录，当然也可以用哈希表或者字典，思想都是一样的。 ```cpp int fib(int N){ if(N==0) return 0; //将备忘录全部置0 vector memo(N+1,0); //进行带备忘录的递归 helper(memo,N); } int helper(vector& memo,int n){ //base case if(N==0) return 0; //已经计算过了，这几返回 if(memo[n]!=0) return memo[n]; //计算,然后存备忘录里 memo[n]=helper(memo,n-1) + helper(memo,n-2); return memo[n]; } ``` #### DP 数组的迭代解法（自底向上）自底向上，从问题规模最小的子问题开始往上推。 ```CPP int fib(int N){ if(N==0) return 0; if(N==1||N==2) return 1; vector 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] } ``` #### 状态压缩因为当前的状态只与前两个状态有关，不需要那么长的一个 DP table 来存储所有的状态，那么只需要想办法存储之前的状态即可，把空间复杂度降为 O(1) ```cpp int fib(int N){ if(N==0) return 0; if(N==1||N==2) return 1; int prev = 1,curr = 1; for(int i = 3;i<=N;i++){ int sum = prev + curr; prev = curr; curr = sum; } return curr; } ``` ### 最优子结构问题最优子结构问题，各子问题必须独立，没有相互制衡，此消彼长例题：凑零钱问题 [322. 零钱兑换](https://leetcode-cn.com/problems/coin-change/) 这道题就符合最优子结构的的性质，因为如果我想要求出`amount = 11`时最少的硬币数，那么我只需要直到 `amount = 10`时的最少硬币数，然后再将子问题加 1（再选 1 枚面值为 1 的硬币。因为硬币的数量是没有限制的，所以子问题之间是相互独立的，没有制约。现在确定了最优子结构的性质，可以用动态规划来解决，接下来思考如何写出状态转移方程 1. 确定 base case。这道题中，很明显，当`amount = 0`时，返回 0，因为不需要任何硬币就可以凑出目标金额了。所以 base case 就是 `amount = 0` 2. 确定状态，也就是原问题和子问题中的变量。由于硬币的数量是无限的，所以硬币的数量不是状态，而目标金额是固定的，只有目标金额不断向 base case 中靠近，所以唯一的状态就是目标金额`amount` 3. 确定选择，也就是会导致状态发生改变的行为。目标金额为什么会变少呢，因为你选择了硬币。每选择一枚硬币，就相当于减少了目标金额，所以说所有的硬币面值就是你的选择。 4. 明确 dp 数组/函数的含义。 - dp 函数：在使用自顶向下的递归写法时，一般来说函数的`参数`就是状态转移方程中的`变量`，也就是我们上面所说的`状态`。函数的返回值就是我们要计算的量。对于本题来说，状态只有一个，也就是`目标金额amount`，题目要求我们求出凑出目标金额所需的最少硬币数量，所以我们可以这样定义 dp 函数 dp(n)：`输入`一个目标金额`n`，`返回`凑出目标金额 n 的`最少硬币数量` - dp 数组：在使用自顶向上的解法时，我们用 DP table 来消除重叠子问题，dp 数组的定义和 dp 函数的定义类似，也就是把`状态`，也就是把状态，即目标金额作为变量，不同的是，dp 函数的状态体现在`函数参数`上，而 dp 数组的状态体现在`数组索引`上。 dp 数组的定义：当目标金额为 i 时，至少需要 dp[i]枚硬币能凑出来 dp 数组的遍历五花八门，有的正着遍历，有的倒着遍历，有的斜着遍历，要注意遍历的方法至于选择哪种方法，要注意两点 - 遍历过程中，所需的状态必须是已经算出来的 - 遍历的终点必须是存储结果的位置主要是要看 base case 和最终结果的存储位置，`保证遍历过程中使用的数据都是计算完毕的` 常见问题： 1. 最长递增子序列（`注意子串一定是连续的，子序列不一定是连续的`） LIS 问题 300 base case dp[1] = 1 dp[i] 表示以 nums[i]结尾的最长递增子序列的长度。 2. 信封嵌套问题 354 先对宽度 w 进行排序，然后如果遇到 w 相同的情况，按照高度 h 进行降序排序，只有把所有的 h 作为一个数组，在这个数组的基础上计算出的 LIS 的长度就是答案 3. 最大子数组问题 53 dp[i] 表示以 nums[i]结尾的最大子数组之和，这种情况下，就不能返回 dp[n-1]了，而是要遍历整个 dp 数组，找到最大的哪一个 dp[i]有两种选择，一种是与前面的相邻子数组连接，组成一个更大的子数组，一种是不与前面的子数组连接，自成一派，自己作为一个子数组。 dp[i] = Math.max(nums[i],nums[i]+dp(n-1)) 4. 最长公共子序列 LCS 二维动态规划 1143 `dp[i][j]`的含义是，对于 s1[0…i]和 s2[0…j-1]，它们的 LCS 长度是`dp[i][j]` 一般这种情况，通常定义索引为 0 的行和列表示空串，`dp[…][0]`he 和`dp[0][…]`都初始化为 0，这就是 base case；然后分两种情况，在和不在，谁大听谁的 5. 编辑距离 72 6. 最长回文子序列 516 `dp[i][j]`的含义是，在子串 s[i…j]中，最长回文子序列为`dp[i][j]` 7. 以最小插入次数构造回文串 1312 8. 正则表达式 9. 高楼扔鸡蛋 10. 戳气球 312 11. 0 - 1 背包问题状态：背包的容量和可以选择的物品选择：装和不装 `dp[i][w]`的含义是，对于前 i 个物品，当前背包容量为 w 时，这种情况下能装下的最大价值为`dp[i][w]` - 子集划分问题 12. 完全背包问题状态：背包的容量和可以选择的物品选择：装和不装 - 凑零钱 2 13. 打家劫舍 ## 3 回溯法解决回溯法实际上就是一个决策树的遍历过程，一般只需要思考三个过程 1. 路径：也就是已经做出的选择 2. 选择列表，也就是你当前可以做的选择 3. 结束条件：也就是到达决策树底层，无法再做选择的条件。代码框架： ```python result = []; def backtrack(路径，选择列表)： if 满足条件 result.add(路径) return for 选择 in 选择列表 #做选择将该选择从选择列表中移除路径.add(选择) backtrack(路径，选择列表) #撤销选择路径.remove(选择) 将该选择恢复到选择列表 ``` 核心：for 循环里面的递归，在递归调用之前“做选择”，在递归调用之后“撤销选择回溯算法本质上就是一个多叉树的遍历问题，只是在前序遍历（做选择）和后序遍历的位置（撤销选择）做了一些操作。常见问题： 1. 全排列 2. N 皇后 3. 解决子集，组合，排列问题 4. 解数独 5. 括号生成 ## 4 DFS ### 1 DFS 和回溯算法区别 DFS 是一个劲的往某一个方向搜索，而回溯算法建立在 DFS 基础之上的，但不同的是在搜索过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索。因此回溯算法与 DFS 的区别就是有无状态重置. ## 3 2 何时使用回溯算法当问题需要 "回头"，以此来查找出所有的解的时候，使用回溯算法。即满足结束条件或者发现不是正确路径的时候(走不通)，要撤销选择，回退到上一个状态，继续尝试，直到找出所有解为止 ### 3 怎么样写回溯算法(从上而下，※代表难点，根据题目而变化) - ① 画出递归树，找到状态变量(回溯函数的参数)，这一步非常重要※ - ② 根据题意，确立结束条件 - ③ 找准选择列表(与函数参数相关),与第一步紧密关联※ - ④ 判断是否需要剪枝 - ⑤ 作出选择，递归调用，进入下一层 ⑥ 撤销选择 ### 参考 [C++ 总结了回溯问题类型带你搞懂回溯算法(大量例题)](https://leetcode-cn.com/problems/subsets/solution/c-zong-jie-liao-hui-su-wen-ti-lei-xing-dai-ni-gao-/) ## 5 BFS BFS 广度优先搜索 DFS 深度优先搜索（可以认为是回溯算法）核心思想：就是把一些问题抽象成图，从一个点开始，向四周扩散，一般来说，我们写 BFS 算法都是用队列这种数据结构，每次将一个节点周围的所有节点加入到队列中 BFS 相对于 DFS 的最主要区别就是：`BFS找到的路径一定是最短的`，但代价是空间复杂度比 DFS 大得多。 BFS 的应用场景是：在一幅`图`中找到从起点 start 到终点 target 的最近距离。算法框架： ```java int BFS(Node start,Node target){ Queue q;//核心数据结构 Set visited; //哈希集合，避免走回头路 q.offer(start);//将起点加入队列 visited.add(start); int step = 0;//记录扩散的步数 while( q not empty){ int sz = q.size(); /*将当前队列中的所有节点向四周扩散*/ for(int i = 0;itarget) right=... } return ...; } ``` … 标记的地方是很可能出现细节的错误的地方，尤其要注意注意搜索区间：是左闭右开`[left,right)`，还是两端都闭`[left,right]` 另外，为了防止 mid 计算溢出，代码中`(left+（right-left）/2)`和`(left+right)/2`是相同，但如果 left 和 right 太大，直接相加会导致整型溢出，而改写成`(left+（right-left）/2)`则不会溢出了； 1. 寻找一个数（基本的二分搜索） 2. 寻找左侧边界的二分搜索当`nums[mid] == target`，不要立即返回，而是要收缩右边界以锁定左边界当 target 比所有元素都大的时候，left 会超过数组的长度，所以最后还要检查 left 是否越界 3. 寻找右侧边界的二分搜索当`nums[mid] == target`，不要立即返回，而是要收缩左边界以锁定右边界而收缩左侧边界必须`left=mid+1`，所以最后无论返回 left 还是 right，都要减一当 target 比所有元素都小的时候，right 会被减到-1，所以最后还是要检查 right 是否越界 ## 8 滑动窗口算法本质上是双指针，经常解决字符串问题，特别时给出两个字符串的那种算法框架： ```cpp int left = 0,right = 0; while(right need,window; for(char c : t) need[c]++; int left = 0,right=0; int valid = 0; while(right