> For the complete documentation index, see [llms.txt](https://shimin-huang.gitbook.io/doc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shimin-huang.gitbook.io/doc/base/algorithm/suan-fa-ti-jie.md). # 算法题解 ## DP核心思想 * 重叠子问题 * 可以使用"备忘录"和"DPTable"来记录中间结果 * 最优子结构 ``` 可以从子问题的最优结果推出更大规模问题的最优结果。让你算每个班的最优成绩就是子问题，你知道所有子问题的答案后，就可以借此推出全校学生的最优成绩这个规模更大的问题的答案。 ``` * 状态转移方程 ### 三要素框架 * **明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义**。 ```python # 初始化 base case dp[0][0][...] = base # 进行状态转移 for 状态1 in 状态1的所有取值： for 状态2 in 状态2的所有取值： for ... dp[状态1][状态2][...] = 求最值(选择1，选择2...) ``` #### Demo * 比如计算最长递增子序列，需要定义好dp数组，然后只要知道dp\[i]=x这个含义是什么，在最长递增子序列里:**dp\[i] 表示以 nums\[i] 这个数结尾的最长递增子序列的长度。** ### 股票最佳买卖时机问题 * 根据状态去做穷举，每天分为三种选择：买入、卖出、无操作，其余就是三种状态的组合并且根据交易次数限制 ```python dp[i][k][0 or 1] 0 <= i <= n-1, 1 <= k <= K n 为天数，大 K 为最多交易数 此问题共 n × K × 2 种状态，全部穷举就能搞定。 for 0 <= i < n: for 1 <= k <= K: for s in {0, 1}: dp[i][k][s] = max(buy, sell, rest) ``` * 而且我们可以用自然语言描述出每一个状态的含义，比如说 `dp[3][2][1]` 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。再比如 `dp[2][3][0]` 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易。很容易理解，对吧？ * 我们想求的最终答案是dp\[n-1] \[k] \[0]，即最后一天，最多允许 K 次交易，最多获得多少利润。读者可能问为什么不是 dp\[n - 1] \[K] \[1]？因为 \[1] 代表手上还持有股票，\[0] 表示手上的股票已经卖出去了，很显然后者得到的利润一定大于前者。 #### 状态转移方程 ```python dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) max( 选择 rest , 选择 sell ) 解释：今天我没有持有股票，有两种可能： 要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有； 要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。 dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) max( 选择 rest , 选择 buy ) 解释：今天我持有着股票，有两种可能： 要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票； 要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。 ``` #### base case ```python dp[-1][k][0] = 0 解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。 dp[-1][k][1] = -infinity 解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。 dp[i][0][0] = 0 解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。 dp[i][0][1] = -infinity 解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。 ``` #### 总结 ```python base case： dp[-1][k][0] = dp[i][0][0] = 0 dp[-1][k][1] = dp[i][0][1] = -infinity 状态转移方程： dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) ``` ### 0-1背包问题 #### 题目 * 给你一个可装载重量为`W`的背包和`N`个物品，每个物品有重量和价值两个属性。其中第`i`个物品的重量为`wt[i]`，价值为`val[i]`，现在让你用这个背包装物品，最多能装的价值是多少？ ``` N = 3, W = 4 wt = [2, 1, 3] val = [4, 2, 3] ``` #### 确定""状态和"选择" * 先说状态，如何才能描述一个问题局面？只要给定几个可选物品和一个背包的容量限制，就形成了一个背包问题，对不对？**所以状态有两个，就是「背包的容量」和「可选择的物品」**。 * 再说选择，也很容易想到啊，对于每件物品，你能选择什么？**选择就是「装进背包」或者「不装进背包」嘛**。 #### 明确dp数组的定义 * `dp`数组是什么？其实就是描述问题局面的一个数组。换句话说，我们刚才明确问题有什么「状态」，现在需要用`dp`数组把状态表示出来。 * 状态有两个所以可以用一个二维数组来表示，`dp[i][w]`定义如下:前`i`个物品，当前背包的容量为`w`，这种情况可以装的最大价值就是`dp[i][w]`。 * 比如说，如果 dp\[3] \[5] = 6，其含义为：对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包容量为 5 时，最多可以装下的价值为 6。 #### base case * `dp[0][..]`=`dp[...][0]`=0 * 最终得到的0-1背包问题框架 ```java 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]]`也很好理解：你如果想装第`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] ``` ### 完全背包问题 * 有一个背包，最大容量为`amount`，有一系列物品`coins`，每个物品的重量为`coins[i]`，**每个物品的数量无限**。请问有多少种方法，能够把背包恰好装满？ ```java int [][] dp=new int[n+1][amount+1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= amount; j++) // 还有容量 if (j - coins[i - 1] >= 0) dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]; // 没有容量保持不变 else dp[i][j] = dp[i - 1][j]; } ``` ### 编辑距离问题 #### 题目 * [**72. 编辑距离**](https://leetcode-cn.com/problems/edit-distance/) #### 解题思路 * 使用双指针方式，从`s1`和`s2`两字符串尾部开始移动，然后对字符串的内容做比较，如果相同则跳过，不同则添加或者删除操作，如果`s1`指针走完后，`s2`指针还没走完的话，将`s2`剩余的字符串全部放入`s1`头部。 **base case** * 指针`i`走完`s1`或者指针`j`走完`s2` ```scala dp[i][0]=i; dp[0][j]=j; ``` **核心框架** ```java // 伪代码 if s1[i] == s2[j]: 啥都别做（skip） i, j 同时向前移动 else: 三选一： 插入（insert） 删除（delete） 替换（replace） // 核心逻辑 if (word1.charAt(i - 1) == word2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1]; // 跳过 } else { dp[i][j] = Math.min(Math.min( dp[i - 1][j] + 1, // 删除 dp[i][j - 1] + 1), // 插入 dp[i - 1][j - 1] + 1); //替换 } ``` ### 打家劫舍系列问题 #### 题目 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 #### 状态和选择 * 偷的钱 偷或者不偷 #### base case * int \[] dp=new int\[N+2]; #### 状态转移方程 ```java public class LeetCode198 { private int[] memo; public int rob(int[] nums) { // 初始化备忘录 memo = new int[nums.length]; Arrays.fill(memo, -1); return dp(nums, 0); } // 递归函数 int dp(int[] nums, int start) { if (start >= nums.length) { return 0; } if (memo[start] != -1) { return memo[start]; } // 不偷去下一家、偷获取价值 int res = Math.max(dp(nums, start + 1), nums[start] + dp(nums, start + 2)); memo[start] = res; return memo[start]; } // dp表 public int rob1(int[] nums) { int n = nums.length; if (n == 0) { return n; } // base case int[] dp = new int[n + 2]; for (int i = n - 1; i >= 0; i--) { // 做选择， 不偷，偷 dp[i] = Math.max(dp[i + 1], dp[i + 2] + nums[i]); } // 递归到第一个元素 return dp[0]; } // 压缩状态 int rob2(int[] nums) { int n = nums.length; if (n == 0) { return n; } // base case int dp_i_1 = 0, dp_i_2 = 0; int dp_i = 0; for (int i = n - 1; i >= 0; i--) { // 做选择， 不偷，偷 dp_i = Math.max(dp_i_1, dp_i_2 + nums[i]); dp_i_2 = dp_i_1; dp_i_1 = dp_i; } // 递归到第一个元素 return dp_i; } } ``` ### 子序列解题模板：最长回文子序列 #### 俩种思路 * **第一种思路模板是一个一维的 dp 数组**： ```java int n = array.length; int[] dp = new int[n]; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { dp[i] = 最值(dp[i], dp[j] + ...) } } ``` * **在子数组`array[0..i]`中，以\******`array[i]`\******结尾的目标子序列（最长递增子序列）的长度是`dp[i]`**。 * **第二种思路模板是一个二维的 dp 数组**： ```java int n = arr.length; int[][] dp = new dp[n][n]; for (int i = 0; i < n; i++) { for (int j = 1; j < n; j++) { if (arr[i] == arr[j]) dp[i][j] = dp[i][j] + ... else dp[i][j] = 最值(...) } } ``` #### 题目 * 给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。 ```java for 0 <= i < len(s): # 找到以 s[i] 为中心的回文串 palindrome(s, i, i) # 找到以 s[i] 和 s[i+1] 为中心的回文串 palindrome(s, i, i + 1) 更新答案 ``` ### 贪心算法 * 调度区间算法 ```java /** * 调度区间算法 * @param intvs * @return */ public int intervalSchedule(int[][] intvs) { if (intvs.length == 0) return 0; // 根据end从小到大排序 Arrays.sort(intvs, new Comparator() { @Override public int compare(int[] o1, int[] o2) { return o1[1] - o2[2]; } }); // 至少有一个区间不相交 int count = 1; // end最小的区间，从最小end开始计算不相交，如果不相交count+1，并且更新x的end值为当前这个区间的end，继续上述过程 int x_end = intvs[0][1]; for (int[] intv : intvs) { // start int start = intv[0]; // 不想交的区间 if (start >= x_end) { count++; // 更新x x_end = intv[1]; } } return count; } ``` ### 博弈问题 #### 定义dp数组的含义 * `dp[start][end]`其中`start`和`end`定义的选择数组的范围 #### 状态转移方程 * 状态:开始的索引start，结束的索引end，当前轮到的人 ``` dp[start][end][fir or sec] 其中: 0<=start= 0; i--) { for (int j = i + 1; j < n; j++) { dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]); } } return dp[0][n - 1] > 0; } ``` ### KMP(Knuth-Morris-Pratt)字符匹配算法 [KMP](https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/dong-tai-gui-hua-zhi-kmp-zi-fu-pi-pei-suan-fa) #### 算法概述 * **KMP 算法永不回退** **`txt`** **的指针** **`i`\*\*\*\*，不走回头路（不会重复扫描** **`txt`\*\*\*\*），而是借助** **`dp`** **数组中储存的信息把** **`pat`** **移到正确的位置继续匹配**，时间复杂度只需 O(N)，用空间换时间。 #### 定义状态 ```java dp[j][c] = next 0 <= j < M，代表当前的状态 0 <= c < 256，代表遇到的字符（ASCII 码） 0 <= next <= M，代表下一个状态 dp[4]['A'] = 3 表示： 当前是状态 4，如果遇到字符 A， pat 应该转移到状态 3 dp[1]['B'] = 2 表示： 当前是状态 1，如果遇到字符 B， pat 应该转移到状态 2 ``` #### 算法框架 ```java int X # 影子状态 for 0 <= j < M: for 0 <= c < 256: if c == pat[j]: # 状态推进 dp[j][c] = j + 1 else: # 状态重启 # 委托 X 计算重启位置 dp[j][c] = dp[X][c] ``` #### 例子 ```java public int strStr(String haystack, String needle) { int N = haystack.length(); int M = needle.length(); if (M == 0) return M; int[][] dp = new int[M][256]; // base case dp[0][needle.charAt(0)] = 1; // 和dp[i][j]具有相同前缀的状态 int x = 0; for (int i = 1; i < M; i++) { for (int j = 0; j < 256; j++) { // 匹配上 if (needle.charAt(i) == j) { dp[i][j] = i + 1; // 没有匹配，重新激活 } else { dp[i][j] = dp[x][j]; } } // 这里会找到 x = dp[x][needle.charAt(i)]; } // pat初始化状态 int j = 0; for (int i = 0; i < N; i++) { j = dp[j][haystack.charAt(i)]; if (j == M) { return i - M + 1; } } return -1; } ``` ## 回溯(DFS)算法核心思想 * **解决一个回溯问题，实际上就是一个决策树的遍历过程**。 ### 三个问题 1. 路径：也就是已经做出的选择。 2. 选择列表：也就是你当前可以做的选择。 3. 结束条件：也就是到达决策树底层，无法再做选择的条件。 ### 算法框架 ```python result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择 # 核型代码详解 for 选择 in 选择列表: # 做选择 将该选择从选择列表移除 路径.add(选择) backtrack(路径, 选择列表) # 撤销选择，深度优先遍历需要回溯的过程，撤回选择在选择上次没选择的路线。 路径.remove(选择) 将该选择再加入选择列表 ``` ![](/files/eXomNiRtxz6nYnjBfL5z) ```java public class LeetCode17 { public List letterCombinations(String digits) { List combinations = new ArrayList(); if (digits.length() == 0) { return combinations; } Map phoneMap = new HashMap<>(); phoneMap.put('2', "abc"); phoneMap.put('3', "def"); phoneMap.put('4', "ghi"); phoneMap.put('5', "jkl"); phoneMap.put('6', "mno"); phoneMap.put('7', "pqrs"); phoneMap.put('8', "tuv"); phoneMap.put('9', "wxyz"); dfs(phoneMap, combinations, digits, 0, new StringBuffer()); return combinations; } void dfs(Map phoneMap, List combinations, String digits, int index, StringBuffer combination) { // 终止条件，index等于数组字符长度 if (index == digits.length()) { combinations.add(combination.toString()); return; } // 做选择 char digit = digits.charAt(index); String letters = phoneMap.get(digit); int lettersCount = letters.length(); for (int i = 0; i < lettersCount; i++) { combination.append(letters.charAt(i)); dfs(phoneMap, combinations, digits, index + 1, combination); // 撤回选择 combination.deleteCharAt(index); } } } ``` ## BFS算法核心思想 * BFS 相对 DFS 的最主要的区别是：**BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多**。 ### 算法框架 ```java // 计算从起点 start 到终点 target 的最近距离 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; 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++; } } ``` * **为什么 BFS 可以找到最短距离，DFS 不行吗**？ ``` 首先，你看 BFS 的逻辑，depth 每增加一次，队列中的所有节点都向前迈一步，这保证了第一次到达终点的时候，走的步数是最少的。 DFS 不能找最短路径吗？其实也是可以的，但是时间复杂度相对高很多。你想啊，DFS 实际上是靠递归的堆栈记录走过的路径，你要找到最短路径，肯定得把二叉树中所有树杈都探索完才能对比出最短的路径有多长对不对？而 BFS 借助队列做到一次一步「齐头并进」，是可以在不遍历完整棵树的条件下找到最短距离的。 形象点说，DFS 是线，BFS 是面；DFS 是单打独斗，BFS 是集体行动。这个应该比较容易理解吧。 ``` * **既然 BFS 那么好，为啥 DFS 还要存在**？ ``` BFS 可以找到最短距离，但是空间复杂度高，而 DFS 的空间复杂度较低。 还是拿刚才我们处理二叉树问题的例子，假设给你的这个二叉树是满二叉树，节点数为 N，对于 DFS 算法来说，空间复杂度无非就是递归堆栈，最坏情况下顶多就是树的高度，也就是 O(logN)。 但是你想想 BFS 算法，队列中每次都会储存着二叉树一层的节点，这样的话最坏情况下空间复杂度应该是树的最底层节点的数量，也就是 N/2，用 Big O 表示的话也就是 O(N)。 由此观之，BFS 还是有代价的，一般来说在找最短路径的时候使用 BFS，其他时候还是 DFS 使用得多一些（主要是递归代码好写）。 ``` ### 双向BFS优化 * **传统的 BFS 框架就是从起点开始向四周扩散，遇到终点时停止；而双向 BFS 则是从起点和终点同时开始扩散，当两边有交集的时候停止**。 ![img](https://gblobscdn.gitbook.com/assets%2F-LrtQOWSnDdXhp3kYN4k%2Fsync%2F96d7b1ab7db024a1831170c128f5dcacfb68abb8.jpeg?alt=media) ![img](https://gblobscdn.gitbook.com/assets%2F-LrtQOWSnDdXhp3kYN4k%2Fsync%2F946f50b8251df56bfaa1d60a133affd736e4ebb3.jpeg?alt=media) * 图示中的树形结构，如果终点在最底部，按照传统 BFS 算法的策略，会把整棵树的节点都搜索一遍，最后找到 `target`；而双向 BFS 其实只遍历了半棵树就出现了交集，也就是找到了最短距离。从这个例子可以直观地感受到，双向 BFS 是要比传统 BFS 高效的。 * **不过，双向 BFS 也有局限，因为你必须知道终点在哪里**。比如我们刚才讨论的二叉树最小高度的问题，你一开始根本就不知道终点在哪里，也就无法使用双向 BFS；但是第二个密码锁的问题，是可以使用双向 BFS 算法来提高效率的，代码稍加修改即可： ## 二分搜索 ### 二分搜索套路 ![img](https://gblobscdn.gitbook.com/assets%2F-LrtQOWSnDdXhp3kYN4k%2Fsync%2F6262c33549e980c22758927d7a57280b5213ed3f.png?alt=media) ```java int binarySearch(int[] nums, int target) { int left = 0, right = nums.length-1; while(left<=right) { // 这里left + (right - left) / 2等价于(right+left)/2，这样做为了防止int数据溢出 int mid = left + (right - left) / 2; if (nums[mid] == target) { ... } else if (nums[mid] < target) { left = ... } else if (nums[mid] > target) { right = ... } } return ...; } ``` ## 滑动窗口算法 ### 算法框架 ```scala public String minWindow(String s, String t) { if (s == null || s.length() == 0 || t == null || t.length() == 0) { return ""; } // 窗口中的所有字符及其出现的对应次数 Map window = new HashMap<>(); // 模式串中出现的所有字符及其次数 Map patternCount = new HashMap<>(); for (int i = 0; i < t.length(); i++) { patternCount.put(t.charAt(i), patternCount.getOrDefault(t.charAt(i), 0) + 1); } String res = ""; int left = 0; int right = 0; while (right <= s.length() - 1) { // 更新window window.put(s.charAt(right), window.getOrDefault(s.charAt(right), 0) + 1); // 判断模式串的所有字符串是否都落在当前window right++; // 走到这里，说明window已经包含了所有字符,开始缩小left，直到窗口刚好不包含所有字符 while (checkInWindow(window, patternCount)) { // 如果窗口长度 String substring = s.substring(left, right); if (res.length() == 0 || res.length() > substring.length()) { res = substring; } // 从window中删去left指向的字符 window.put(s.charAt(left), window.get(s.charAt(left)) - 1); left++; } } return res; } private boolean checkInWindow(Map window, Map patternCount) { for (Map.Entry entry : patternCount.entrySet()) { // 单词对不上或者不存在 if (!window.containsKey(entry.getKey()) || window.get(entry.getKey()) < entry.getValue()) { return false; } } return true; } ``` * ## Union-Find算法 ### 连通的特性 * 这里所说的「连通」是一种等价关系，也就是说具有如下**三个性质**： 1、自反性：节点`p`和`p`是连通的。 2、对称性：如果节点`p`和`q`连通，那么`q`和`p`也连通。 3、传递性：如果节点`p`和`q`连通，`q`和`r`连通，那么`p`和`r`也连通。 ```java class UF { /* 将 p 和 q 连接 */ public void union(int p, int q); /* 判断 p 和 q 是否连通 */ public boolean connected(int p, int q); /* 返回图中有多少个连通分量,没有连通的节点数 */ public int count(); } ``` ### 算法核心点 1、用 `parent` 数组记录每个节点的父节点，相当于指向父节点的指针，所以 `parent` 数组内实际存储着一个森林（若干棵多叉树）。 2、用 `size` 数组记录着每棵树的重量，目的是让 `union` 后树依然拥有平衡性，而不会退化成链表，影响操作效率。 3、在 `find` 函数中进行路径压缩，保证任意树的高度保持在常数，使得 `union` 和 `connected` API 时间复杂度为 O(1)。 ### 代码实现 ```java public class UF { // 记录连通分量 private int count; // 节点x的节点是parent[x] private int[] parent; // 记录树的"重量" private int[] size; public UF(int n) { // 一开始互不连通 this.count = n; parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { // 节点i指向自己 parent[i] = i; // 初始状态只包含自己一个节点 size[i] = 1; } } /** * 连通p和q * * @param p * @param q */ public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP == rootQ) { return; } // 小树接到大树下，较平衡 if (size[rootP] > size[rootQ]) { parent[rootQ] = rootP; size[rootP] += size[rootQ]; } else { parent[rootP] = rootQ; size[rootQ] += size[rootP]; } count--; } /** * 判断p和q是否连通 * * @param p * @param q * @return */ public boolean connected(int p, int q) { int rootP = find(p); int rootQ = find(q); return rootP == rootQ; } /** * 返回某个节点x的根节点 * * @param x * @return */ private int find(int x) { while (parent[x] != x) { // 路径压缩 parent[x] = parent[parent[x]]; x = parent[x]; } return x; } public int count() { return count; } } ``` ## 单调栈 ### 算法框架模版 ```java // 核心模版 // 倒着往栈里放 for (int i = nums.length - 1; i >= 0; i--) { // 判定个子高矮 while (!s.isEmpty() && s.peek() <= nums[i]) { // 矮个起开，反正也被挡着了。。。 s.pop(); } // nums[i] 身后的 next great number res[i] = s.isEmpty() ? -1 : s.peek(); // s.push(nums[i]); } ``` ### 循环队列模版 ```java public int[] nextGreaterElements(int[] nums) { int n = nums.length; Stack s = new Stack<>(); int[] res = new int[n]; // 假装这个数组长度翻倍了 for (int i = 2 * n - 1; i >= 0; i--) { // 索引要求模 while (!s.empty() && s.peek() <= nums[i % n]) { s.pop(); } res[i % n] = s.empty() ? -1 : s.peek(); s.push(nums[i % n]); } return res; } ``` ## 双索引技术 ### 二分查找法 ```java # 基础二分查找 public int search(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { // 这里left + (right - left) / 2等价于(right+left)/2，这样做为了防止int数据溢出 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; } /** * 寻找左边界的二分搜索 * * @param nums * @param target * @return */ public int leftBoundSearch(int[] nums, int target) { int length = nums.length; if (length == 0) { return -1; } int left = 0, right = length - 1; while (left <= right) { int mid = left + (right - left) / 2; // 左边搜索 if (nums[mid] == target) { right = mid - 1; } if (nums[mid] > target) { right = mid - 1; } if (nums[mid] < target) { left = mid + 1; } } // 防止数据越界 if (left >= nums.length || nums[left] != target) { return -1; } return left; } /** * 寻找右边界的二分搜索 * * @param nums * @param target * @return */ public int rightBoundSearch(int[] nums, int target) { int length = nums.length; if (length == 0) { return -1; } int left = 0, right = length - 1; while (left <= right) { // 这 int mid = left + (right - left) / 2; // 左边搜索 if (nums[mid] == target) { left = mid + 1; } if (nums[mid] > target) { right = mid - 1; } if (nums[mid] < target) { left = mid + 1; } } // 防止数据越界 if (right < 0 || nums[right] != target) { return -1; } return right; } ``` ### 滑动窗口 * Leetcode3/76/209/438/567 ``` public int minSubArrayLen(int s, int[] nums) { int l = 0, r = -1, sum = 0; int res = nums.length + 1; while (l < nums.length) { if (r + 1 < nums.length && sum < s) { sum += nums[++r]; } else { sum -= nums[l++]; } if (sum >= s) { res = Math.min(res, r - l + 1); } } if (res == nums.length + 1) { return 0; } return res; } public String minWindow(String s, String t) { if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) { return ""; } //维护两个数组，记录已有字符串指定字符的出现次数，和目标字符串指定字符的出现次数 //ASCII表总长128 int[] need = new int[128]; int[] have = new int[128]; //将目标字符串指定字符的出现次数记录 for (int i = 0; i < t.length(); i++) { need[t.charAt(i)]++; } //分别为左指针，右指针，最小长度(初始值为一定不可达到的长度) //已有字符串中目标字符串指定字符的出现总频次以及最小覆盖子串在原字符串中的起始位置 int left = 0, right = 0, min = s.length() + 1, count = 0, start = 0; while (right < s.length()) { char r = s.charAt(right); //说明该字符不被目标字符串需要，此时有两种情况 // 1.循环刚开始，那么直接移动右指针即可，不需要做多余判断 // 2.循环已经开始一段时间，此处又有两种情况 // 2.1 上一次条件不满足，已有字符串指定字符出现次数不满足目标字符串指定字符出现次数，那么此时 // 如果该字符还不被目标字符串需要，就不需要进行多余判断，右指针移动即可 // 2.2 左指针已经移动完毕，那么此时就相当于循环刚开始，同理直接移动右指针 if (need[r] == 0) { right++; continue; } //已有字符串中目标字符出现的次数+1 //当且仅当已有字符串目标字符出现的次数小于目标字符串字符的出现次数时，count才会+1 //是为了后续能直接判断已有字符串是否已经包含了目标字符串的所有字符，不需要挨个比对字符出现的次数 if (have[r] < need[r]) { count++; } have[r]++; //移动右指针 right++; //当且仅当已有字符串已经包含了所有目标字符串的字符，且出现频次一定大于或等于指定频次 while (count == t.length()) { //当窗口的长度比已有的最短值小时，更改最小值，并记录起始位置 if (right - left < min) { min = right - left; start = left; } char l = s.charAt(left); //如果左边即将要去掉的字符不被目标字符串需要，那么不需要多余判断，直接可以移动左指针 if (need[l] == 0) { left++; continue; } //如果左边即将要去掉的字符被目标字符串需要，且出现的频次正好等于指定频次，那么如果去掉了这个字符， //就不满足覆盖子串的条件，此时要破坏循环条件跳出循环，即控制目标字符串指定字符的出现总频次(count）-1 if (have[l] == need[l]) { count--; } //已有字符串中目标字符出现的次数-1 have[l]--; //移动左指针 left++; } } //如果最小长度还为初始值，说明没有符合条件的子串 if (min == s.length() + 1) { return ""; } //返回的为以记录的起始位置为起点，记录的最短长度为距离的指定字符串中截取的子串 return s.substring(start, start + min); } ``` ## 查找问题 * 使用查找表，定义好map需要查找的键值对 ```java public boolean containsNearbyDuplicate(int[] nums, int k) { Set window = new HashSet<>(); for (int i = 0; i < nums.length; i++) { if (window.contains(nums[i])) { return true; } window.add(nums[i]); if (window.size() == k + 1) { window.remove(nums[i - k]); } } return false; } public List> groupAnagrams(String[] strs) { Map> records = new HashMap<>(); for (String str : strs) { char[] chars = str.toCharArray(); Arrays.sort(chars); String key = new String(chars); List arr = records.getOrDefault(key, new ArrayList<>()); arr.add(str); records.put(key, arr); } return new ArrayList<>(records.values()); } ``` ## 链表相关 ### 虚拟头节点 ```java public ListNode removeElements(ListNode head, int val) { // 虚拟头节点 ListNode pred = new ListNode(-1); pred.next = head; ListNode pre = pred, curr = head; while (curr != null) { if (curr.val == val) { pre.next = curr.next; } else { pre = curr; } curr = curr.next; } return pred.next; } ``` ### 反转链表 ```java public ListNode fz(ListNode head) { ListNode pre = null, curr = head; while (curr != null) { ListNode tempNext=curr.next; curr.next=pre; pre=curr; curr=tempNext; } return pre; } public ListNode reverseN(ListNode root, int n) { // 翻转最后一个Node if (n == 1) { // 例如1-2-3-4-5 n=3，那么successor为4 successor = root.next; return root; } ListNode last = reverseN(root, n - 1); // node反转 root.next.next = root; // 将1的next关联上4 root.next = successor; return last; } ``` ## 队列和栈 ### 栈 * 利用栈校验括号的合法性 ```java public boolean isValid1(String s) { if (s.length() % 2 != 0) { return false; } Map store = new HashMap<>(); store.put('(', ')'); store.put('[', ']'); store.put('{', '}'); Stack stack = new Stack<>(); for (char c : s.toCharArray()) { // 将做括号放入栈 if (store.containsKey(c)) { stack.push(c); } else { if (!stack.isEmpty()) { Character pop = stack.pop(); if (!store.get(pop).equals(c)) { return false; } } else { return false; } } } return stack.isEmpty(); } ``` ### 队列 #### 层序遍历相关 ```java public List> levelOrder(TreeNode root) { List> res = new ArrayList<>(); if (root == null) return res; Queue queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { List temp = new ArrayList<>(); int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode cur = queue.poll(); temp.add(cur.val); if (cur.left != null) { queue.add(cur.left); } if (cur.right != null) { queue.add(cur.right); } } res.add(temp); } return res; } ``` #### 优先队列TopK ```java public static int[] topKFrequent(int[] nums, int k) { Map occurrences = new HashMap<>(nums.length); for (int num : nums) { occurrences.put(num, occurrences.getOrDefault(num, 0) + 1); } // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数 PriorityQueue queue = new PriorityQueue(new Comparator() { @Override public int compare(int[] m, int[] n) { return m[1] - n[1]; } }); for (Map.Entry entry : occurrences.entrySet()) { int num = entry.getKey(), count = entry.getValue(); // 如果等于k if (queue.size() == k) { assert queue.peek() != null; // 最小堆堆顶小于count，替换位置 if (queue.peek()[1] < count) { queue.poll(); queue.offer(new int[]{num, count}); } } else { queue.offer(new int[]{num, count}); } } int[] ret = new int[k]; for (int i = 0; i < k; ++i) { ret[i] = Objects.requireNonNull(queue.poll())[0]; } return ret; } ``` ​