LeetCode常用算法模板

代码模板 

 

1、DFS：适用于树和图的遍历、组合问题。
2、BFS：适用于树和图的层次遍历、最短路径问题。
3、二分查找：适用于有序数组的搜索问题。
4、动态规划：适用于最优化问题、序列问题。
5、贪心算法：适用于局部最优问题、调度问题。
6、回溯算法：适用于组合、排列、子集问题。
7、滑动窗口：适用于子数组、子串问题。
8、拓扑排序：适用于依赖关系问题、课程安排问题。

9、快慢指针：多用于检测链表中的环、找到环的起点。

10、双指针：处理字符串、数组、链表问题。
11、优先队列：处理调度、合并等问题。
12、并查集：处理动态连通性问题。
13、前缀和：用于快速计算子数组和。
14、单调栈：用于查找数组中前后更大或更小的元素。
15、排序：包括快速排序、归并排序和堆排序等常见排序算法。

一、深度优先搜索模板

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。该算法会尽可能深地搜索树的分支，直到不能继续为止，然后回溯并继续搜索下一条路径。DFS 可以用于解决广泛的问题，包括路径查找、连通性问题、拓扑排序等。

适用问题类型

DFS 适用于以下类型的问题：

1. 图的遍历：例如连通性问题、环检测等。
2. 路径查找：例如找从起点到终点的所有路径。
3. 树的遍历：例如前序遍历、中序遍历、后序遍历。
4. 组合问题：例如生成所有可能的组合或排列。
5. 回溯问题：例如八皇后问题、解数独等。

LeetCode 热题 100 与经典面试 150 中的 DFS 相关问题

基础 DFS 问题

1. 104. 二叉树的最大深度
2. 200. 岛屿数量
3. 733. 图像渲染

中等难度 DFS 问题

1. 79. 单词搜索
2. 130. 被围绕的区域
3. 494. 目标和

高级 DFS 问题

1. 329. 矩阵中的最长递增路径
2. 753. 破解保险箱

    /*** 深度优先搜索模板（DFS）*/public class DFSTemplate {/*** 二叉树定义*/class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val = val;}}/*** 深度优先搜索*/public void dfs(TreeNode node) {if (node == null) {return;}// 处理当前节点System.out.println(node.val);// 递归处理左右子节点dfs(node.left);dfs(node.right);}/*** 二叉树的最大深度*/public int maxDepth(TreeNode root) {if (root == null) {return 0;}return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));}}

 二、广度优先搜索模板

广度优先搜索（BFS）是一种用于遍历或搜索树或图的算法。该算法会从根节点开始，首先访问所有相邻节点，然后对每个相邻节点的相邻节点进行访问。BFS 通常使用队列来实现，适用于查找最短路径以及层次遍历等问题。

适用问题类型

BFS 适用于以下类型的问题：

1. 图的遍历：例如连通性问题、环检测等。
2. 最短路径问题：例如无权图中的最短路径。
3. 层次遍历：例如二叉树的层次遍历。
4. 迷宫问题：例如从起点到终点的最短路径。

LeetCode 热题 100 与经典面试 150 中的 BFS 相关问题

基础 BFS 问题

1. 102. 二叉树的层序遍历
2. 107. 二叉树的层次遍历 II
3. 111. 二叉树的最小深度

中等难度 BFS 问题

1. 200. 岛屿数量
2. 207. 课程表
3. 417. 太平洋大西洋水流问题

高级 BFS 问题

1. 301. 删除无效的括号
2. 127. 单词接龙
3. 490. 迷宫

    /*** 广度优先搜索模板（BFS）*/public class BFSTemplate {/*** 二叉树定义*/class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val = val;}}/*** 广度优先搜索*/public void bfs(TreeNode root) {if (root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();System.out.println(node.val);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}/*** 二叉树的层序遍历*/public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) {return result;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int levelSize = queue.size();List<Integer> level = new ArrayList<>();for (int i = 0; i < levelSize; i++) {TreeNode node = queue.poll();level.add(node.val);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}result.add(level);}return result;}}

 三、二分查找模板

二分查找算法用于在有序数组中高效地查找目标值。它通过不断将查找范围减半，使得查找过程的时间复杂度为 (O(log n))。

适用问题类型

二分查找适用于以下类型的问题：

1. 查找有序数组中的目标值。
2. 查找范围内的某个条件的最优解。
3. 解决一些需要优化搜索范围的复杂问题。

LeetCode 热题 100 与经典面试 150 中的二分查找相关问题

基础二分查找问题

1. 33. 搜索旋转排序数组
2. 34. 在排序数组中查找元素的第一个和最后一个位置
3. 35. 搜索插入位置

边界和变体问题

1. 69. x 的平方根
2. 74. 搜索二维矩阵
3. 153. 寻找旋转排序数组中的最小值
4. 162. 寻找峰值

复杂问题

1. 240. 搜索二维矩阵 II
2. 275. H 指数 II
3. 300. 最长递增子序列
4. 378. 有序矩阵中第 K 小的元素

    /*** 二分查找模板*/public class BinarySearchTemplate {/*** 二分查找*/public 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 {right = mid - 1;}}return -1;}/*** 搜索旋转排序数组*/public int 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) {return mid;}if (nums[left] <= nums[mid]) {if (nums[left] <= target && target < nums[mid]) {right = mid - 1;} else {left = mid + 1;}} else {if (nums[mid] < target && target <= nums[right]) {left = mid + 1;} else {right = mid - 1;}}}return -1;}}

四、动态规划模板

动态规划是一种解决复杂问题的方法，它通过将问题分解为更小的子问题，并利用子问题的解来构建原问题的解。动态规划主要用于求解最优子结构和重叠子问题的问题。

适用问题类型

动态规划适用于以下类型的问题：

1. 最优子结构：问题的最优解包含了其子问题的最优解。
2. 重叠子问题：子问题的解可以被多次使用。
3. 决策问题：例如背包问题、路径问题等。

LeetCode 热题 100 与经典面试 150 中的动态规划相关问题

基础动态规划问题

1. 70. 爬楼梯
2. 53. 最大子序和
3. 198. 打家劫舍
4. 213. 打家劫舍 II
5. 152. 乘积最大子数组

中等难度动态规划问题

1. 62. 不同路径
2. 63. 不同路径 II
3. 91. 解码方法
4. 221. 最大正方形
5. 139. 单词拆分

高级动态规划问题

1. 300. 最长递增子序列
2. 322. 零钱兑换
3. 1143. 最长公共子序列
4. 518. 零钱兑换 II
5. 139. 单词拆分

    /*** 动态规划（DP）模板*/public class DpTemplate {public int dp(int[] nums) {int n = nums.length;int[] dp = new int[n];// 初始化dp[0] = nums[0];for (int i = 1; i < n; i++) {dp[i] = Math.max(dp[i - 1], nums[i]);}return dp[n - 1];}/*** 最长上升子序列*/public int lengthOfLIS(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int[] dp = new int[nums.length];Arrays.fill(dp, 1);int maxLength = 1;for (int i = 1; i < nums.length; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}maxLength = Math.max(maxLength, dp[i]);}return maxLength;}}

五、贪心算法模板

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法通常用于解决最优化问题，特别是那些可以通过一系列局部最优解来构成全局最优解的问题。

适用问题类型

贪心算法适用于以下类型的问题：

1. 最优化问题：例如最小生成树、最短路径问题等。
2. 活动选择问题：例如区间调度问题。
3. 资源分配问题：例如背包问题、任务调度问题等。

LeetCode 热题 100 与经典面试 150 中的贪心算法相关问题

基础贪心算法问题

1. 55. 跳跃游戏
2. 45. 跳跃游戏 II
3. 122. 买卖股票的最佳时机 II
4. 135. 分发糖果
5. 435. 无重叠区间

中等难度贪心算法问题

1. 406. 根据身高重建队列
2. 452. 用最少数量的箭引爆气球
3. 763. 划分字母区间
4. 134. 加油站
5. 316. 去除重复字母

高级贪心算法问题

1. 871. 最低加油次数
2. 621. 任务调度器
3. 665. 非递减数列
4. 406. 根据身高重建队列

    /*** 贪心算法模板*/public class GreedyTemplate {public int solve(int[] nums) {int result = 0;for (int num : nums) {// 执行贪心选择if (someCondition(num)) {result += num;}}return result;}private boolean someCondition(int num) {// 自定义条件return true;}/*** 无重叠区间*/public int eraseOverlapIntervals(int[][] intervals) {if (intervals.length == 0) {return 0;}Arrays.sort(intervals, (a, b) -> a[1] - b[1]);int count = 1;int end = intervals[0][1];for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] >= end) {count++;end = intervals[i][1];}}return intervals.length - count;}}

六、回溯算法模板

回溯算法是一种通过逐步构建解决方案并在发现当前部分解决方案不能导致最终解决方案时及时回溯的方法。它适用于组合问题、排列问题和某些路径问题。回溯算法尝试所有可能的选项，并在发现一个选择不符合问题要求时撤销选择，并尝试其他选项。

适用问题类型

回溯算法适用于以下类型的问题：

1. 组合问题：例如子集、组合、排列等。
2. 路径问题：例如迷宫问题、N皇后问题等。
3. 约束满足问题：例如数独、八皇后问题等。

LeetCode 热题 100 与经典面试 150 中的回溯算法相关问题

组合和排列问题

1. 46. 全排列
2. 47. 全排列 II
3. 78. 子集
4. 77. 组合
5. 79. 单词搜索

路径问题

1. 93. 复原 IP 地址
2. 131. 分割回文串
3. 39. 组合总和
4. 40. 组合总和 II

约束满足问题

1. 51. N 皇后
2. 52. N 皇后 II
3. 37. 解数独

    /*** 回溯算法模板*/public class BacktrackingTemplate {private List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> solve(int[] nums) {backtrack(new ArrayList<>(), nums);return result;}/*** 回溯方法*/private void backtrack(List<Integer> tempList, int[] nums) {if (tempList.size() == nums.length) {result.add(new ArrayList<>(tempList));} else {for (int i = 0; i < nums.length; i++) {if (tempList.contains(nums[i])) {continue;}tempList.add(nums[i]);backtrack(tempList, nums);// 回溯，尝试所有可能结果tempList.remove(tempList.size() - 1);}}}/*** 全排列*/public List<List<Integer>> permute(int[] nums) {List<List<Integer>> result = new ArrayList<>();backtrack(result, new ArrayList<>(), nums);return result;}private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums) {if (tempList.size() == nums.length) {result.add(new ArrayList<>(tempList));} else {for (int i = 0; i < nums.length; i++) {if (tempList.contains(nums[i])) {continue;}tempList.add(nums[i]);backtrack(result, tempList, nums);tempList.remove(tempList.size() - 1);}}}}

七、滑动窗口模板

滑动窗口算法是一种高效解决子数组、子串等序列问题的技术。它通常用于求解具有固定或可变长度的连续子数组或子串问题。通过维护一个窗口（通常是左右指针），滑动窗口算法可以在O(n)的时间复杂度内解决许多问题。

适用问题类型

滑动窗口算法适用于以下类型的问题：

1. 子数组/子串问题：例如最长无重复子串、最小覆盖子串等。
2. 固定长度或变化长度的窗口：例如最大/最小子数组和问题。

LeetCode 热题 100 与经典面试 150 中的滑动窗口相关问题

基础滑动窗口问题

1. 3. 无重复字符的最长子串
2. 76. 最小覆盖子串
3. 567. 字符串的排列
4. 438. 找到字符串中所有字母异位词

中等难度滑动窗口问题

1. 209. 长度最小的子数组
2. 904. 水果成篮
3. 424. 替换后的最长重复字符

高级滑动窗口问题

1. 239. 滑动窗口最大值
2. 480. 滑动窗口中位数

    /*** 滑动窗口模板*/public class SlidingWindowTemplate {public int solve(int[] nums) {int left = 0, right = 0;int maxLength = 0;while (right < nums.length) {// 扩大窗口right++;// 收缩窗口while (someCondition()) {left++;}maxLength = Math.max(maxLength, right - left);}return maxLength;}private boolean someCondition() {// 自定义条件return false;}/*** 最长无重复子串*/public int lengthOfLongestSubstring(String s) {Set<Character> set = new HashSet<>();int left = 0, right = 0, maxLength = 0;while (right < s.length()) {if (!set.contains(s.charAt(right))) {set.add(s.charAt(right));right++;maxLength = Math.max(maxLength, set.size());} else {set.remove(s.charAt(left));left++;}}return maxLength;}}

八、拓扑排序模板

拓扑排序用于有向无环图（DAG）的顶点排序，使得对于图中的每一条有向边 (u, v)，顶点 u 在拓扑排序中出现在顶点 v 前面。拓扑排序通常应用于解决依赖关系问题，例如任务调度、编译顺序等。

拓扑排序的常用方法有两种：Kahn 算法和深度优先搜索（DFS）。

适用问题类型

拓扑排序适用于以下类型的问题：

1. 依赖关系问题：例如任务调度、编译顺序等。
2. 有向无环图（DAG）上的排序问题。

LeetCode 热题 100 与经典面试 150 中的拓扑排序相关问题

基础拓扑排序问题

1. 207. 课程表
2. 210. 课程表 II

中等难度拓扑排序问题

1. 269. 火星词典
2. 444. 序列重建

高级拓扑排序问题

1. 1136. 平行课程
2. 1203. 项目管理

    /*** 拓扑排序模板*/public class TopologicalSortTemplate {public List<Integer> topologicalSort(int numCourses, int[][] prerequisites) {List<Integer> result = new ArrayList<>();List<Integer>[] graph = new List[numCourses];int[] inDegree = new int[numCourses];for (int i = 0; i < numCourses; i++) {graph[i] = new ArrayList<>();}for (int[] pre : prerequisites) {graph[pre[1]].add(pre[0]);inDegree[pre[0]]++;}Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (inDegree[i] == 0) {queue.offer(i);}}while (!queue.isEmpty()) {int course = queue.poll();result.add(course);for (int next : graph[course]) {inDegree[next]--;if (inDegree[next] == 0) {queue.offer(next);}}}return result.size() == numCourses ? result : new ArrayList<>();}/*** 课程表*/public boolean canFinish(int numCourses, int[][] prerequisites) {List<Integer>[] graph = new List[numCourses];int[] inDegree = new int[numCourses];for (int i = 0; i < numCourses; i++) {graph[i] = new ArrayList<>();}for (int[] pre : prerequisites) {graph[pre[1]].add(pre[0]);inDegree[pre[0]]++;}Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (inDegree[i] == 0) {queue.offer(i);}}int count = 0;while (!queue.isEmpty()) {int course = queue.poll();count++;for (int next : graph[course]) {inDegree[next]--;if (inDegree[next] == 0) {queue.offer(next);}}}return count == numCourses;}}

九、快慢指针模板

快慢指针是一种常用于链表操作的技巧，通过使用两个指针以不同的速度遍历链表，可以解决许多复杂的问题，如检测链表是否有环、找到环的起点、找到链表的中间节点等。

适用问题类型

快慢指针适用于以下类型的问题：

1. 环检测：例如检测链表是否有环。
2. 寻找中间节点：例如找到链表的中间节点。
3. 环的起点：例如找到链表环的起点。
4. 其他问题：例如判断链表是否为回文。

LeetCode 热题 100 与经典面试 150 中的快慢指针相关问题

基础快慢指针问题

1. 141. 环形链表
2. 142. 环形链表 II
3. 876. 链表的中间结点

中等难度快慢指针问题

1. 234. 回文链表
2. 143. 重排链表

高级快慢指针问题

1. 287. 寻找重复数

    /*** 快慢指针模板*/public class FastSlowPointerTemplate {/*** 链表定义*/public class ListNode {int val;ListNode next;ListNode(int val) {this.val = val;}}/*** 是否有环*/public boolean hasCycle(ListNode head) {if (head == null || head.next == null) {return false;}ListNode slow = head;ListNode fast = head.next;while (slow != fast) {if (fast == null || fast.next == null) {return false;}slow = slow.next;fast = fast.next.next;}return true;}/*** 环形链表II*/public ListNode detectCycle(ListNode head) {if (head == null || head.next == null) {return null;}ListNode slow = head;ListNode fast = head;// 检测环while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {// 发现环，寻找环的起点ListNode pointer1 = head;ListNode pointer2 = slow;while (pointer1 != pointer2) {pointer1 = pointer1.next;pointer2 = pointer2.next;}return pointer1;}}return null;}}

十、双指针模板

双指针是一种在数组或链表中使用两个指针来迭代的技巧。这两种指针可以同步移动或异步移动，用于解决各种问题，如排序、搜索、合并、去重等。双指针技术通常用于一维数据结构，如数组和链表。

双指针模式有以下几种常见类型：

1. 对撞指针：从数组的两端向中间移动，常用于二分查找、回文串检查等。
2. 快慢指针：一个指针移动快，另一个指针移动慢，常用于链表的环检测、链表中点查找等。
3. 滑动窗口：两个指针定义一个窗口，用于子数组和子串问题。

适用问题类型

双指针适用于以下类型的问题：

1. 对撞指针：如二分查找、回文串检查、两数之和等。
2. 快慢指针：如链表中的环检测、链表中点查找等。
3. 滑动窗口：如子数组和子串问题。

LeetCode 热题 100 与经典面试 150 中的双指针相关问题

基础双指针问题

1. 15. 三数之和
2. 16. 最接近的三数之和
3. 26. 删除排序数组中的重复项
4. 27. 移除元素
5. 125. 验证回文串

中等难度双指针问题

1. 167. 两数之和 II - 输入有序数组
2. 259. 较小的三数之和
3. 344. 反转字符串
4. 345. 反转字符串中的元音字母

高级双指针问题

1. 11. 盛最多水的容器
2. 42. 接雨水
3. 76. 最小覆盖子串
4. 992. K 个不同整数的子数组

    /*** 双指针模板*/public class TwoPointerTemplate {public int solve(int[] nums, int target) {int left = 0, right = nums.length - 1;int result = 0;while (left < right) {// 执行逻辑int sum = nums[left] + nums[right];if (sum == target) {// 找到目标result++;left++;right--;} else if (sum < target) {left++;} else {right--;}}return result;}/*** 两数之和II-输入有序数组*/public int[] twoSum(int[] numbers, int target) {int left = 0, right = numbers.length - 1;while (left < right) {int sum = numbers[left] + numbers[right];if (sum == target) {// 注意：返回的索引是从 1 开始return new int[]{left + 1, right + 1};} else if (sum < target) {left++;} else {right--;}}// 没找到，返回无效值return new int[]{-1, -1};}}

十一、优先队列模板

优先队列是一种特殊的队列结构，其中每个元素都有一个优先级，删除操作总是删除具有最高优先级的元素。优先队列通常用堆（Heap）来实现，具有快速插入和删除操作的特性。

在 Java 中，优先队列可以通过 PriorityQueue 类来实现。默认情况下，PriorityQueue 是一个最小堆，即堆顶元素是优先级最低的元素。可以通过传入自定义比较器来实现最大堆。

适用问题类型

优先队列适用于以下类型的问题：

1. 排序问题：例如合并K个有序链表。
2. 实时数据流处理：例如找到数据流中的第K大的元素。
3. 调度问题：例如任务调度、最短路径算法（如Dijkstra算法）。

LeetCode 热题 100 与经典面试 150 中的优先队列相关问题

基础优先队列问题

1. 215. 数组中的第K个最大元素
2. 703. 数据流中的第K大元素
3. 347. 前 K 个高频元素
4. 295. 数据流的中位数

中等难度优先队列问题

1. 378. 有序矩阵中第K小的元素
2. 692. 前K个高频单词
3. 373. 查找和最小的K对数字

高级优先队列问题

1. 239. 滑动窗口最大值
2. 23. 合并K个排序链表
3. 502. IPO

    /*** 优先队列模板*/public class PriorityQueueTemplate {public class ListNode {int val;ListNode next;public ListNode(int val) {this.val = val;}}public int solve(int[] nums) {PriorityQueue<Integer> pq = new PriorityQueue<>();for (int num : nums) {pq.offer(num);}while (!pq.isEmpty()) {System.out.println(pq.poll());}// 根据实际问题返回结果return 0;}public ListNode mergeKLists(ListNode[] lists) {if (lists == null || lists.length == 0) {return null;}PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val);for (ListNode node : lists) {if (node != null) {pq.offer(node);}}ListNode dummy = new ListNode(0);ListNode current = dummy;while (!pq.isEmpty()) {current.next = pq.poll();current = current.next;if (current.next != null) {pq.offer(current.next);}}return dummy.next;}}

十二、并查集模板

并查集是一种用于处理不相交集合合并及查询的高效数据结构。它支持以下两种操作：

1. Find：确定元素属于哪个集合。
2. Union：合并两个集合。

并查集通常通过“路径压缩”和“按秩合并”两种优化来提高性能，使得这两种操作都接近于常数时间复杂度。

适用问题类型

并查集适用于以下类型的问题：

1. 连通性问题：例如判断图中节点连通性、网络连通问题等。
2. 动态连通性：例如动态连通分量数目计算。
3. 集合合并与查询：例如岛屿数量、冗余连接等。

LeetCode 热题 100 与经典面试 150 中的并查集相关问题

基础并查集问题

1. 200. 岛屿数量
2. 547. 省份数量
3. 684. 冗余连接

中等难度并查集问题

1. 721. 账户合并
2. 128. 最长连续序列

高级并查集问题

1. 305. 岛屿数量 II
2. 399. 除法求值

    /*** 并查集模板*/public class UnionFindTemplate {private int[] parent;private int[] rank;public UnionFindTemplate(int size) {parent = new int[size];rank = new int[size];for (int i = 0; i < size; i++) {parent[i] = i;rank[i] = 1;}}public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]); // 路径压缩}return parent[x];}public void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX]++;}}}/*** 岛屿数量*/public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) {return 0;}int rows = grid.length;int cols = grid[0].length;UnionFind uf = new UnionFind(rows * cols);int count = 0;// 初始化并查集和计数for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (grid[i][j] == '1') {count++;}}}// 遍历网格，进行合并操作for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (grid[i][j] == '1') {grid[i][j] = '0';count--;// 合并相邻的岛屿if (i > 0 && grid[i - 1][j] == '1') {uf.union(i * cols + j, (i - 1) * cols + j);count++;}if (i < rows - 1 && grid[i + 1][j] == '1') {uf.union(i * cols + j, (i + 1) * cols + j);count++;}if (j > 0 && grid[i][j - 1] == '1') {uf.union(i * cols + j, i * cols + j - 1);count++;}if (j < cols - 1 && grid[i][j + 1] == '1') {uf.union(i * cols + j, i * cols + j + 1);count++;}}}}return count;}class UnionFind {private int[] parent;private int[] rank;public UnionFind(int size) {parent = new int[size];rank = new int[size];for (int i = 0; i < size; i++) {parent[i] = i;rank[i] = 1;}}public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}public void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX]++;}}}}}

十三、前缀和模板

前缀和是一种通过预处理数组来快速计算任意子数组和的技术。前缀和数组的每个元素表示原数组从起点到当前索引的累积和。通过前缀和数组，可以在常数时间内计算任何子数组的和。

适用问题类型

前缀和适用于以下类型的问题：

1. 子数组和问题：例如求解固定长度或变化长度的子数组和问题。
2. 区间求和问题：例如累积和、连续子数组的最大和等。
3. 差分数组：用于快速处理区间更新问题。

LeetCode 热题 100 与经典面试 150 中的前缀和相关问题

基础前缀和问题

1. 303. 区域和检索 - 数组不可变
2. 560. 和为 K 的子数组
3. 238. 除自身以外数组的乘积

中等难度前缀和问题

1. 525. 连续数组
2. 930. 和相同的二元子数组
3. 1248. 统计「优美子数组」

高级前缀和问题

1. 974. 和可被 K 整除的子数组
2. 1524. 和为奇数的子数组数目

    /*** 前缀和模板*/public class PrefixSumTemplate {public int[] calculatePrefixSum(int[] nums) {int n = nums.length;int[] prefixSum = new int[n + 1];for (int i = 0; i < n; i++) {prefixSum[i + 1] = prefixSum[i] + nums[i];}return prefixSum;}public int rangeSum(int[] prefixSum, int left, int right) {return prefixSum[right + 1] - prefixSum[left];}private int[] prefixSum;/*** 区域和检索-数组不可变*/public PrefixSumTemplate(int[] nums) {int n = nums.length;prefixSum = new int[n + 1];for (int i = 0; i < n; i++) {prefixSum[i + 1] = prefixSum[i] + nums[i];}}public int sumRange(int left, int right) {return prefixSum[right + 1] - prefixSum[left];}}

十四、单调栈模板

单调栈是一种用于解决一系列特定问题的数据结构，特别适用于处理“下一个更大元素”或“前一个更小元素”等问题。单调栈可以是单调递增栈或单调递减栈：

• 单调递增栈：栈内元素从栈底到栈顶递增。
• 单调递减栈：栈内元素从栈底到栈顶递减。

单调栈的关键在于通过维护栈的单调性，快速找到某些元素的最近位置关系（如下一个更大元素、前一个更小元素等）。

适用问题类型

单调栈适用于以下类型的问题：

1. 下一个/前一个更大/更小元素问题：如找下一个更大元素、找前一个更小元素等。
2. 柱状图中最大矩形：如求解直方图中最大矩形面积。
3. 滑动窗口问题：如在滑动窗口中找到最大值或最小值。

LeetCode 热题 100 与经典面试 150 中的单调栈相关问题

基础单调栈问题

1. 496. 下一个更大元素 I
2. 503. 下一个更大元素 II
3. 739. 每日温度

中等难度单调栈问题

1. 42. 接雨水
2. 84. 柱状图中最大的矩形
3. 907. 子数组的最小值之和

高级单调栈问题

1. 316. 去除重复字母
2. 862. 和至少为 K 的最短子数组

    /*** 单调栈模板*/public class MonotonicStackTemplate {public int[] nextGreaterElement(int[] nums) {int n = nums.length;int[] result = new int[n];Stack<Integer> stack = new Stack<>();for (int i = n - 1; i >= 0; i--) {while (!stack.isEmpty() && stack.peek() <= nums[i]) {stack.pop();}result[i] = stack.isEmpty() ? -1 : stack.peek();stack.push(nums[i]);}return result;}/*** 每日温度*/public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int[] result = new int[n];Stack<Integer> stack = new Stack<>();for (int i = 0; i < n; i++) {while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {int index = stack.pop();result[index] = i - index;}stack.push(i);}return result;}}

十五、冒泡排序模板

冒泡排序是一种简单的排序算法，通过重复地遍历数组，比较相邻元素并交换它们的位置，如果它们的顺序错误。这个过程会将较大的元素“冒泡”到数组的末端。冒泡排序的时间复杂度为O(n²)，空间复杂度为O(1)，是一个原地且稳定的排序算法。

适用问题类型

冒泡排序适用于需要简单实现的排序任务，特别是当数据量较小时。由于其时间复杂度较高，不适合大规模数据的排序。然而，冒泡排序在理解和实现排序算法的基本原理方面是一个很好的起点。

LeetCode 热题 100 与经典面试 150 中的冒泡排序相关问题

冒泡排序在实际应用中并不常见，因为它的效率不如其他排序算法。然而，它的基本思想在一些初学者和教学场景中非常重要。

    /*** 冒泡排序模板*/public class BubbleSortTemplate {public void bubbleSort(int[] nums) {int n = nums.length;boolean swapped;for (int i = 0; i < n - 1; i++) {swapped = false;for (int j = 0; j < n - 1 - i; j++) {if (nums[j] > nums[j + 1]) {swap(nums, j, j + 1);swapped = true;}}// 如果在内层循环中没有发生交换，说明数组已经有序，提前结束if (!swapped) {break;}}}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}

十六、快速排序模板

快速排序是一种高效的排序算法，采用分治法（Divide and Conquer）策略来排序数组。基本思想是选择一个“基准”（pivot），将数组分成两部分，一部分小于基准，一部分大于基准，然后递归地对这两部分进行排序。

适用问题类型

快速排序适用于需要高效排序的各种类型的数组和列表。它在许多情况下表现良好，特别是当数组几乎随机排列时。快速排序的平均时间复杂度为O(n log n)，最坏情况下为O(n²)，但通过改进可以避免最坏情况。

LeetCode 热题 100 与经典面试 150 中的快速排序相关问题

快速排序常用于解决需要排序的中间步骤问题，例如：

1. 912. 排序数组
2. 215. 数组中的第K个最大元素

虽然快速排序本身作为一个完整的题目不常见，但它的概念和应用在许多排序和选择问题中非常有用。

    /*** 快速排序模板*/public class QuickSortTemplate {public void quickSort(int[] nums, int left, int right) {if (left < right) {int pivotIndex = partition(nums, left, right);quickSort(nums, left, pivotIndex - 1);quickSort(nums, pivotIndex + 1, right);}}private int partition(int[] nums, int left, int right) {int pivot = nums[right];int i = left;for (int j = left; j < right; j++) {if (nums[j] < pivot) {swap(nums, i, j);i++;}}swap(nums, i, right);return i;}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}

十七、归并排序模板

归并排序是一种基于分治法的排序算法。其基本思想是将数组分成两个子数组，分别对这两个子数组进行排序，然后合并这两个有序的子数组以得到最终的有序数组。归并排序的时间复杂度为O(n log n)，是一种稳定的排序算法。

适用问题类型

归并排序适用于需要高效排序的各种类型的数组和列表。它在许多情况下表现良好，尤其是在数据量较大且需要稳定排序的情况下。

LeetCode 热题 100 与经典面试 150 中的归并排序相关问题

归并排序常用于解决需要排序的中间步骤问题，例如：

1. 148. 排序链表
2. 912. 排序数组

    /*** 归并排序模板*/public class MergeSortTemplate {public void mergeSort(int[] nums, int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);merge(nums, left, mid, right);}}private void merge(int[] nums, int left, int mid, int right) {int[] temp = new int[right - left + 1];int i = left, j = mid + 1, k = 0;while (i <= mid && j <= right) {if (nums[i] <= nums[j]) {temp[k++] = nums[i++];} else {temp[k++] = nums[j++];}}while (i <= mid) {temp[k++] = nums[i++];}while (j <= right) {temp[k++] = nums[j++];}System.arraycopy(temp, 0, nums, left, temp.length);}}

十八、堆排序模板

堆排序是一种基于堆（通常是二叉堆）的排序算法。它利用堆这种数据结构来实现排序，分为两个主要步骤：

1. 构建最大堆：将数组构建成一个最大堆。
2. 排序过程：将堆顶元素（最大值）移到数组末尾，然后重新调整堆，使之成为新的最大堆，重复该过程直到排序完成。

堆排序的时间复杂度为O(n log n)，不需要额外的空间，是一种原地排序算法。然而，堆排序的写操作较多，不是稳定排序。

适用问题类型

堆排序适用于需要高效排序且不需要稳定性的各种类型的数组和列表。由于堆排序是原地排序，不需要额外的空间，适合在内存受限的环境中使用。

LeetCode 热题 100 与经典面试 150 中的堆排序相关问题

堆排序常用于解决需要排序的中间步骤问题，例如：

1. 215. 数组中的第K个最大元素
2. 347. 前K个高频元素

虽然堆排序本身作为一个完整的题目不常见，但它的概念和应用在许多排序和选择问题中非常有用。

    /*** 堆排序模板*/public class HeapSortTemplate {public void heapSort(int[] nums) {int n = nums.length;// Build heap (rearrange array)for (int i = n / 2 - 1; i >= 0; i--) {heapify(nums, n, i);}// One by one extract an element from heapfor (int i = n - 1; i >= 0; i--) {// Move current root to endswap(nums, 0, i);// Call max heapify on the reduced heapheapify(nums, i, 0);}}private void heapify(int[] nums, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;// If left child is larger than rootif (left < n && nums[left] > nums[largest]) {largest = left;}// If right child is larger than largest so farif (right < n && nums[right] > nums[largest]) {largest = right;}// If largest is not rootif (largest != i) {swap(nums, i, largest);// Recursively heapify the affected sub-treeheapify(nums, n, largest);}}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}