常见算法模板
常见算法模板
一、双指针算法模板
双指针通常用两个变量表示两个位置：
int left = 0;
int right = nums.length - 1;常见用途：
- 有序数组查找
- 数组去重
- 反转数组
- 链表快慢指针
- 判断回文
- 移动零
1.1 左右指针模板
适合：有序数组、两数之和、反转数组、回文判断。
int left = 0;
int right = nums.length - 1;
while (left < right) {
if (满足条件) {
// 处理结果
left++;
right--;
} else if (需要左指针右移) {
left++;
} else {
right--;
}
}典型思路
left 从左往右走
right 从右往左走
每次根据条件移动一个指针1.2 快慢指针模板
适合：数组去重、移动零、链表找中点、判断环。
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] 满足条件) {
nums[slow] = nums[fast];
slow++;
}
}典型思路
fast 负责遍历数组
slow 负责记录结果位置1.3 链表快慢指针模板
适合：找链表中点、判断链表是否有环。
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;典型思路
slow 每次走一步
fast 每次走两步1.4 简单记忆
左右指针：一左一右，向中间靠近
快慢指针：一个遍历，一个记录位置
链表快慢指针：slow 走一步，fast 走两步二、滑动窗口模板
2.1 适用场景
滑动窗口常用于处理：
- 连续子数组
- 连续子字符串
- 最长 / 最短区间
- 满足某个条件的区间
常见关键词：连续、子数组、子字符串、最长、最短、满足条件
2.2 核心思想
滑动窗口使用两个指针：
int left = 0;
int right = 0;含义：
right：负责扩大窗口
left：负责缩小窗口窗口范围一般是：
[left, right]2.3 基础模板
int left = 0;
for (int right = 0; right < nums.length; right++) {
// 1. 加入右边元素，扩大窗口
while (窗口不满足条件) {
// 2. 移除左边元素，缩小窗口
left++;
}
// 3. 更新答案
}2.4 最长窗口模板
适合求：
最长子数组
最长子字符串模板：
int left = 0;
int result = 0;
for (int right = 0; right < nums.length; right++) {
// 加入 nums[right]
while (窗口不满足条件) {
// 移除 nums[left]
left++;
}
result = Math.max(result, right - left + 1);
}2.5 最短窗口模板
适合求：
最短子数组
最小覆盖子串模板：
int left = 0;
int result = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
// 加入 nums[right]
while (窗口满足条件) {
result = Math.min(result, right - left + 1);
// 移除 nums[left]
left++;
}
}2.6 记忆口诀
right 扩大窗口
left 缩小窗口
不满足就移动 left(最长窗口类问题)
每次更新答案三、二分查找模板
3.1 适用场景
二分查找常用于：
- 有序数组
- 查找某个值
- 查找左边界
- 查找右边界
- 在答案范围中找最优解
常见关键词：有序、查找、最小值最大、最大值最小、满足条件的第一个位置、满足条件的最后一个位置
3.2 基础模板
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;3.3 查找左边界模板
适合找：
第一个等于 target 的位置int left = 0;
int right = nums.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
if (nums[mid] == target) {
result = mid;
}
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;3.4 查找右边界模板
适合找：
最后一个等于 target 的位置int left = 0;
int right = nums.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
if (nums[mid] == target) {
result = mid;
}
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;3.5 答案二分模板
答案二分不是在数组里找某个数，而是在一个“答案范围”里找最优答案。
核心是写一个 check(mid) 函数，用来判断：
mid 这个答案是否可行答案二分常见有两种类型：
1. 找最小可行值：找第一个满足条件的答案
2. 找最大可行值：找最后一个满足条件的答案3.5.1 找最小可行值
适合这类题目：
最小的最大值
最小容量
最小速度
最短时间
最少需要多少常见例子：
船的最小载重
吃香蕉的最小速度
完成任务的最短时间
分割数组，使最大子数组和最小特点：
答案太小：不可行
答案变大：开始可行
答案再变大：仍然可行也就是：
false false false true true true
↑
找第一个 true模板：
int left = 最小可能答案;
int right = 最大可能答案;
while (left < right) {
int mid = left + (right - left) / 2;
if (check(mid)) {
// mid 已经可行，但可能还可以更小
right = mid;
} else {
// mid 不可行，只能增大答案
left = mid + 1;
}
}
return left;记忆：
找最小可行值：
check(mid) 为 true，说明 mid 可行，继续往左找
所以 right = mid3.5.2 找最大可行值
适合这类题目：
最大的最小值
最大距离
最大长度
最多可以是多少常见例子：
两球之间的最大最小距离
牛棚放牛的最大最小距离
切绳子能得到的最大长度特点：
答案小：可行
答案变大：可能仍然可行
答案太大：不可行也就是：
true true true true false false
↑
找最后一个 true模板：
int left = 最小可能答案;
int right = 最大可能答案;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (check(mid)) {
// mid 可行，说明可以尝试更大的答案
left = mid;
} else {
// mid 不可行，只能减小答案
right = mid - 1;
}
}
return left;记忆：
找最大可行值：
check(mid) 为 true，说明 mid 可行，继续往右找
所以 left = mid
注意：
这里 mid 要写成 left + (right - left + 1) / 2
也就是让 mid 偏右，避免死循环3.5.3 两种模板对比
找最小可行值：false false false true true true
↑
找第一个 true
找最大可行值：true true true true false false
↑
找最后一个 true// 找最小可行值
if (check(mid)) {
right = mid;
} else {
left = mid + 1;
}// 找最大可行值
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}3.5.4 最简单记忆口诀
找最小 true：
mid 可行，收右边
right = mid
找最大 true：
mid 可行，收左边
left = mid
mid 要 +1 偏右3.6 记忆口诀
有序数组想二分
left 和 right 定范围
mid 判断往哪边走
找左边界收 right
找右边界收 left
答案二分靠 check四、前缀和模板
4.1 适用场景
前缀和常用于快速计算：
- 连续子数组和
- 区间和
- 子数组和等于某个值
- 二维矩阵区域和
常见关键词：连续子数组、区间和、范围求和、子数组和
4.2 核心思想
提前保存从开头到当前位置的总和。
prefix[i] 表示 nums[0] 到 nums[i - 1] 的和所以区间 [left, right] 的和为：
prefix[right + 1] - prefix[left]4.3 一维前缀和模板
int n = nums.length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
// 求 nums[left] 到 nums[right] 的和
int sum = prefix[right + 1] - prefix[left];4.4 哈希表 + 前缀和模板
适合求：
和为 k 的连续子数组个数Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int prefixSum = 0;
int count = 0;
for (int num : nums) {
prefixSum += num;
if (map.containsKey(prefixSum - k)) {
count += map.get(prefixSum - k);
}
map.put(prefixSum, map.getOrDefault(prefixSum, 0) + 1);
}4.5 二维前缀和模板
适合求矩阵中的区域和。
int m = matrix.length;
int n = matrix[0].length;
int[][] prefix = new int[m + 1][n + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
prefix[i + 1][j + 1] =
prefix[i][j + 1]
+ prefix[i + 1][j]
- prefix[i][j]
+ matrix[i][j];
}
}
// 求左上角 (r1, c1) 到右下角 (r2, c2) 的区域和
int sum =
prefix[r2 + 1][c2 + 1]
- prefix[r1][c2 + 1]
- prefix[r2 + 1][c1]
+ prefix[r1][c1];4.6 记忆口诀
前缀和先累加
区间和用相减
子数组和配哈希
二维区域多减多加五、栈模板
5.1 适用场景
栈常用于处理：
- 括号匹配
- 最近的元素关系
- 表达式计算
- 单调栈问题
- DFS 模拟递归
常见关键词：匹配、最近、上一个、下一个、括号、有效
5.2 核心思想
栈的特点是：
先进后出
后进先出Java 中常用：
Deque<Integer> stack = new ArrayDeque<>();常用操作：
stack.push(x); // 入栈
stack.pop(); // 出栈
stack.peek(); // 查看栈顶
stack.isEmpty(); // 判断是否为空5.3 基础模板
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
// 根据条件弹出栈顶元素
while (!stack.isEmpty() && 满足条件) {
stack.pop();
}
// 当前元素入栈
stack.push(nums[i]);
}5.4 括号匹配模板
适合题目：
有效的括号Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
char top = stack.pop();
if (c == ')' && top != '(') return false;
if (c == ']' && top != '[') return false;
if (c == '}' && top != '{') return false;
}
}
return stack.isEmpty();5.5 单调栈模板
适合题目：
下一个更大元素
每日温度
柱状图最大矩形Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
int index = stack.pop();
// nums[i] 是 nums[index] 右边第一个更大的元素
}
stack.push(i);
}5.6 记忆口诀
括号匹配用栈
最近关系用栈
下一个更大用单调栈
栈顶不满足就弹出六、哈希表模板
6.1 适用场景
哈希表常用于：
- 快速查找
- 判断元素是否存在
- 统计元素出现次数
- 去重
- 两数之和
- 字母异位词
常见关键词：出现次数、是否存在、重复、去重、配对、计数
6.2 核心思想
哈希表可以快速判断一个元素是否出现过。
Java 中常用两种：
Set<Integer> set = new HashSet<>();
Map<Integer, Integer> map = new HashMap<>();含义：
HashSet：只关心元素是否存在
HashMap：关心元素和它对应的信息6.3 HashSet 模板
适合判断元素是否出现过。
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (set.contains(num)) {
// num 已经出现过
}
set.add(num);
}6.4 HashMap 计数模板
适合统计元素出现次数。
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}6.5 两数之和模板
适合题目：
数组中找两个数，使它们的和等于 targetMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (map.containsKey(need)) {
return new int[]{map.get(need), i};
}
map.put(nums[i], i);
}6.6 字符计数模板
适合题目：
字母异位词
字符出现次数int[] count = new int[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}6.7 记忆口诀
查存在用 HashSet
存映射用 HashMap
统计次数用 getOrDefault
字符计数可用数组七、队列 / BFS 模板
7.1 适用场景
队列和 BFS 常用于：
- 二叉树层序遍历
- 图的最短路径
- 岛屿扩散问题
- 迷宫最短步数
- 每一层逐步扩散的问题
常见关键词：层序遍历、最短路径、扩散、一步一步走、从起点到终点
7.2 核心思想
队列的特点是：
先进先出BFS 的思想是：
先访问离起点近的节点
再访问离起点远的节点
一层一层向外扩散Java 中常用：
Queue<Integer> queue = new LinkedList<>();常用操作：
queue.offer(x); // 入队
queue.poll(); // 出队
queue.peek(); // 查看队头
queue.isEmpty(); // 判断是否为空7.3 BFS 基础模板
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[n];
// 起点入队
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int next : graph[cur]) {
if (visited[next]) {
continue;
}
queue.offer(next);
visited[next] = true;
}
}7.4 二叉树层序遍历模板
Queue<TreeNode> queue = new LinkedList<>();
if (root != null) {
queue.offer(root);
}
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}7.5 网格 BFS 模板
适合岛屿、迷宫、最短路径、扩散类问题。
常见判断条件：
1. 是否越界
2. 是否已经访问过
3. 当前格子是否可以走例如：
grid[x][y] == '1' 表示可以走
grid[x][y] == '0' 表示不能走方向数组：
int[][] dirs = {
{1, 0},
{-1, 0},
{0, 1},
{0, -1}
};模板：
Queue<int[]> queue = new ArrayDeque<>();
boolean[][] visited = new boolean[m][n];
// 起点入队
queue.offer(new int[]{startX, startY});
visited[startX][startY] = true;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int x = cur[0];
int y = cur[1];
for (int[] dir : dirs) {
int nextX = x + dir[0];
int nextY = y + dir[1];
// 1. 判断是否越界
if (nextX < 0 || nextX >= m || nextY < 0 || nextY >= n) {
continue;
}
// 2. 判断是否已经访问过
if (visited[nextX][nextY]) {
continue;
}
// 3. 判断当前格子是否可以走
// 这里假设 '0' 表示不能走，'1' 表示可以走
if (grid[nextX][nextY] == '0') {
continue;
}
queue.offer(new int[]{nextX, nextY});
visited[nextX][nextY] = true;
}
}如果题目是迷宫，也可以把判断条件改成：
if (grid[nextX][nextY] == '#') {
continue;
}如果题目中：
0 表示可以走
1 表示障碍物那么判断条件就改成：
if (grid[nextX][nextY] == 1) {
continue;
}7.6 记忆口诀
BFS 用队列
先进先出
一层一层遍历
求最短路径优先想 BFS八、DFS模板
8.1 适用场景
DFS 常用于：
- 二叉树遍历
- 图的遍历
- 岛屿问题
- 路径搜索
- 连通区域问题
常见关键词：搜索、遍历、路径、连通、岛屿、从一个点一直走到底
8.2 核心思想
DFS 的思想是：
从一个起点出发
沿着一个方向一直往下搜索
走不通了再返回
继续尝试其他方向8.3 基础模板
public void dfs(int cur, boolean[] visited, List<Integer>[] graph) {
if (visited[cur]) {
return;
}
visited[cur] = true;
for (int next : graph[cur]) {
dfs(next, visited, graph);
}
}8.4 二叉树 DFS 模板
public void dfs(TreeNode root) {
if (root == null) {
return;
}
// 处理当前节点
dfs(root.left);
dfs(root.right);
}8.5 网格 DFS 模板
适合岛屿、迷宫、连通区域问题。
常见判断条件：
1. 是否越界
2. 是否已经访问过
3. 当前格子是否可以走例如：
grid[x][y] == '1' 表示可以走
grid[x][y] == '0' 表示不能走方向数组：
int[][] dirs = {
{1, 0},
{-1, 0},
{0, 1},
{0, -1}
};模板：
public void dfs(int x, int y, char[][] grid, boolean[][] visited) {
int m = grid.length;
int n = grid[0].length;
// 1. 判断是否越界
if (x < 0 || x >= m || y < 0 || y >= n) {
return;
}
// 2. 判断是否已经访问过
if (visited[x][y]) {
return;
}
// 3. 判断当前格子是否可以走
// 这里假设 '0' 表示不能走，'1' 表示可以走
if (grid[x][y] == '0') {
return;
}
// 标记当前格子已经访问过
visited[x][y] = true;
// 向四个方向继续搜索
for (int[] dir : dirs) {
int nextX = x + dir[0];
int nextY = y + dir[1];
dfs(nextX, nextY, grid, visited);
}
}如果题目是迷宫，也可以把判断条件改成：
if (grid[x][y] == '#') {
return;
}如果题目中：
0 表示可以走
1 表示障碍物那么判断条件就改成：
if (grid[x][y] == 1) {
return;
}8.6 记忆口诀
DFS 用递归
先处理当前点
再搜索相邻点
走到底再回退九、贪心模板
贪心通常没有固定的模板，仅供参考！
9.1 适用场景
贪心常用于：
- 每一步都选择当前最优
- 区间问题
- 跳跃游戏
- 买卖股票
常见关键词：最多、最少、最大、最小、能否、当前最优
9.2 核心思想
每一步都做当前最好的选择
希望最终得到整体最优解注意：
贪心需要满足：局部最优可以推出全局最优9.3 基础模板
public int greedy(int[] nums) {
int result = 0;
for (int i = 0; i < nums.length; i++) {
// 根据当前情况做最优选择
// 更新 result
}
return result;
}9.4 区间贪心模板
区间贪心常见做法：
先按照区间右端点从小到大排序
每次优先选择结束位置最早的区间注意：
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));不要写成：
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);因为 a[1] - b[1] 可能整数溢出。
9.4.1 无重叠区间模板
适合题目：
最多可以选择多少个互不重叠的区间
最少需要删除多少个区间，使剩下的区间互不重叠核心判断：
当前区间的左端点 >= 上一个选择区间的右端点
说明两个区间不重叠模板：
public int intervalSchedule(int[][] intervals) {
if (intervals == null || intervals.length == 0) {
return 0;
}
// 按右端点从小到大排序
Arrays.sort(intervals, (a, b) -> Integer.compare(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];
}
}
// count 表示最多可以选择多少个互不重叠区间
return count;
}如果题目问的是：
最少需要删除多少个区间，使剩下的区间互不重叠那么答案是：
return intervals.length - count;完整写法：
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals == null || intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, (a, b) -> Integer.compare(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;
}9.4.2 用最少箭引爆气球模板
适合题目：
用最少数量的箭引爆所有气球核心判断：
当前气球的左端点 > 当前箭能覆盖的右端点
说明需要一支新箭注意这里是：
intervals[i][0] > end不是：
intervals[i][0] >= end因为如果两个气球刚好在端点接触，例如：
[1, 2] 和 [2, 3]一支箭射在 2 的位置，可以同时引爆两个气球。
模板：
public int findMinArrowShots(int[][] points) {
if (points == null || points.length == 0) {
return 0;
}
// 按右端点从小到大排序
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
int arrows = 1;
int end = points[0][1];
for (int i = 1; i < points.length; i++) {
// 当前气球已经不能被上一支箭覆盖，需要新箭
if (points[i][0] > end) {
arrows++;
end = points[i][1];
}
}
return arrows;
}9.4.3 两类题目的区别
无重叠区间：
新区间左端点 >= end，说明不重叠，可以选择
if (intervals[i][0] >= end)
射气球：
新区间左端点 > end，说明上一支箭射不到了，需要新箭
if (points[i][0] > end)记忆口诀：
区间贪心按右端点排序
无重叠区间看 >=
射气球看 >
防止溢出用 Integer.compare
空数组先判断9.5 跳跃游戏模板
int maxReach = 0;
for (int i = 0; i < nums.length; i++) {
if (i > maxReach) {
return false;
}
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;9.6 记忆口诀
贪心看当前
每步选最优
区间先排序
能否到达看最远十、动态规划模板
10.1 适用场景
动态规划常用于处理：
- 最值问题
- 方案数问题
- 路径问题
- 子序列问题
- 背包问题
- 状态可以由前面结果推出来的问题
常见关键词：最大、最小、多少种方法、方案数、路径数、子序列、不能相邻、选择或不选择
10.2 核心思想
动态规划的核心是：
把大问题拆成小问题
先解决小问题
再用小问题的结果推出大问题的结果最重要的是定义清楚 dp 的含义。
dp[i] 表示到第 i 个位置时的某种最优解或方案数
dp[i][j] 表示在两个维度状态下的最优解或方案数10.3 动态规划五步
1. 定义 dp 数组含义
2. 初始化 dp
3. 写出状态转移方程
4. 确定遍历顺序
5. 返回最终结果注意：
不同题目的 dp 含义不同，状态转移方程也不同。
不能所有 DP 都套同一个 Math.max(dp[i - 1], nums[i])。10.4 一维 DP 模板
适合题目：
爬楼梯
打家劫舍
最大子数组和
买卖股票
背包问题通用模板：
public int solve(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int[] dp = new int[n];
// 1. 初始化
dp[0] = 初始值;
// 2. 状态转移
for (int i = 1; i < n; i++) {
dp[i] = 根据 dp[i - 1]、dp[i - 2]、nums[i] 推出;
}
// 3. 返回答案
return dp[n - 1];
}10.5 最大子数组和模板
适合题目：
连续子数组的最大和dp[i] 含义：
dp[i] 表示以 nums[i] 结尾的最大子数组和状态转移：
要么只选 nums[i]
要么接在前面的子数组后面模板：
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
int result = dp[0];
for (int i = 1; i < n; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
result = Math.max(result, dp[i]);
}
return result;
}10.6 打家劫舍模板
适合题目：
不能选择相邻元素，求最大金额dp[i] 含义：
dp[i] 表示偷到第 i 间房子时，能获得的最大金额状态转移：
第 i 间房子有两个选择：
1. 不偷第 i 间：dp[i - 1]
2. 偷第 i 间：dp[i - 2] + nums[i]模板：
public int rob(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
if (n == 1) {
return nums[0];
}
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];
}10.7 爬楼梯模板
适合题目：
每次可以爬 1 阶或 2 阶，求爬到第 n 阶的方法数dp[i] 含义：
dp[i] 表示爬到第 i 阶的方法数状态转移：
爬到第 i 阶有两种来源：
1. 从第 i - 1 阶爬 1 步上来
2. 从第 i - 2 阶爬 2 步上来模板：
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}10.8 二维 DP 模板
适合题目：
路径问题
编辑距离
最长公共子序列
最长回文子序列
二维网格最值问题核心思路：
dp[i][j] 通常表示到达位置 (i, j) 时的最优解
或者表示两个字符串前 i 个和前 j 个字符之间的关系通用模板：
class Solution {
public int solve(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
// 1. 定义 dp[i][j]：表示到达位置 (i, j) 时的最优解
int[][] dp = new int[m][n];
// 2. 初始化
dp[0][0] = grid[0][0];
// 3. 状态转移
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 根据题目写转移方程
}
}
// 4. 返回结果
return dp[m - 1][n - 1];
}
}10.9 记忆口诀
DP 先定义状态
再初始化边界
根据前面状态推出当前状态
最后返回目标状态的结果
最大子数组和：看接不接前面
打家劫舍：看偷不偷当前
爬楼梯：看从哪一步上来
二维 DP：看上面、左边或两个维度的前置状态十一、回溯算法模板
11.1 适用场景
回溯常用于枚举所有可能的答案：
- 子集
- 组合
- 排列
- 括号生成
- 棋盘搜索
- 数独
- N 皇后
常见关键词：所有方案、所有组合、所有排列、搜索、选择、撤销、路径
11.2 核心思想
回溯的本质是：
尝试一种选择
继续递归
撤销选择
尝试下一种选择可以理解成在一棵搜索树上做 DFS。
每一层表示一次选择
path 记录当前路径
result 保存所有答案11.3 基础模板
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> solve(int[] nums) {
backtrack(nums, 0);
return result;
}
public void backtrack(int[] nums, int startIndex) {
// 1. 终止条件
if (满足条件) {
result.add(new ArrayList<>(path));
return;
}
// 2. 遍历当前层可以选择的元素
for (int i = startIndex; i < nums.length; i++) {
// 3. 做选择
path.add(nums[i]);
// 4. 递归进入下一层
backtrack(nums, i + 1);
// 5. 撤销选择
path.remove(path.size() - 1);
}
}
}搜索树示意：
[]
/ | \
[1] [2] [3]
/ \ |
[1,2] [1,3] [2,3]11.4 子集问题模板
适合题目：
每个元素可以选，也可以不选
要求返回所有可能的集合例如：
nums = [1, 2, 3]
结果：
[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]模板：
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
backtrack(nums, 0);
return result;
}
public void backtrack(int[] nums, int startIndex) {
// 子集问题：每一个节点都是一个结果
result.add(new ArrayList<>(path));
for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]);
backtrack(nums, i + 1);
path.remove(path.size() - 1);
}
}
}关键点：
result.add(new ArrayList<>(path));子集问题中，每一层的 path 都是一个答案11.5 组合问题模板
适合题目：
从 n 个数中选 k 个
不关心顺序例如：
n = 4, k = 2
结果：
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]模板：
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
backtrack(n, k, 1);
return result;
}
public void backtrack(int n, int k, int startIndex) {
// 当 path 的长度等于 k，说明已经选够了
if (path.size() == k) {
result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i <= n; i++) {
path.add(i);
backtrack(n, k, i + 1);
path.remove(path.size() - 1);
}
}
}关键点：
backtrack(n, k, i + 1);组合问题不能重复选，所以递归时从 i + 1 开始11.6 排列问题模板
适合题目：
所有数字都要用上
顺序不同就是不同结果例如：
nums = [1, 2, 3]
结果：
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]模板：
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
used = new boolean[nums.length];
backtrack(nums);
return result;
}
public void backtrack(int[] nums) {
// 当 path 长度等于 nums.length，说明一个排列完成
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
// 当前数字已经用过了，跳过
if (used[i]) {
continue;
}
path.add(nums[i]);
used[i] = true;
backtrack(nums);
path.remove(path.size() - 1);
used[i] = false;
}
}
}关键点：
boolean[] used;排列问题中，每一层都可以从头开始选
但是为了防止重复使用元素，需要 used[i]11.7 三类问题对比
子集：每个节点都是答案
组合：选够 k 个才是答案，递归从 i + 1 开始
排列：选够 nums.length 个才是答案，每层从 0 开始，用 used 防重复| 类型 | 是否关心顺序 | 是否需要 startIndex | 是否需要 used |
|---|---|---|---|
| 子集 | 不关心 | 需要 | 不需要 |
| 组合 | 不关心 | 需要 | 不需要 |
| 排列 | 关心 | 不需要 | 需要 |
11.8 回溯中的核心变量
| 变量 | 作用 | 常见场景 |
|---|---|---|
result | 保存所有答案 | 所有回溯题 |
path | 保存当前正在构造的答案 | 所有回溯题 |
startIndex | 控制从哪里开始选，避免重复 | 子集、组合 |
used | 标记元素是否已经用过 | 排列 |
简单理解：
result：最终答案集合
path：当前正在选择的路径
startIndex：组合 / 子集问题用，防止重复选择
used：排列问题用，防止同一个元素重复使用11.9 记忆口诀
回溯就是选、递归、撤销
result 存结果
path 存路径
组合子集用 startIndex
排列问题用 used
子集每层都收集
组合选够 k 个收集
排列选够所有元素收集十二、并查集模板
12.1 适用场景
并查集常用于处理：
- 判断两个元素是否连通
- 合并两个集合
- 连通分量数量
- 朋友圈 / 省份数量
- 冗余连接
- 图中是否有环
常见关键词：连通、合并、属于同一个集合、朋友圈、省份数量、冗余连接
12.2 核心思想
并查集主要有两个操作：
find：查找当前节点属于哪个集合
union：合并两个集合如果两个节点的根节点相同，说明它们在同一个集合中。
12.3 基础模板
class UnionFind {
int[] parent;
public UnionFind(int n) {
parent = new int[n];
// 初始时，每个节点的父节点都是自己
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// 查找根节点
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) {
parent[rootX] = rootY;
}
}
// 判断是否属于同一个集合
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
}12.4 统计连通分量模板
class UnionFind {
int[] parent;
int count;
public UnionFind(int n) {
parent = new int[n];
count = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
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) {
return;
}
parent[rootX] = rootY;
count--;
}
}12.5 常见使用方式
UnionFind uf = new UnionFind(n);
for (int[] edge : edges) {
int a = edge[0];
int b = edge[1];
uf.union(a, b);
}
// 判断两个点是否连通
boolean connected = uf.isConnected(x, y);12.6 记忆口诀
find 找老大
union 做合并
根节点相同就是连通
合并成功 count 减一十三、单调栈模板
13.1 适用场景
单调栈常用于：
- 下一个更大元素
- 下一个更小元素
- 每日温度
- 柱状图最大矩形
常见关键词：下一个更大、下一个更小、右边第一个更大、右边第一个更小、最近更大、最近更小
13.2 核心思想
栈中元素保持单调递增或单调递减
当前元素破坏单调性时，就弹出栈顶13.3 下一个更大元素模板
Deque<Integer> stack = new ArrayDeque<>();
int[] result = new int[nums.length];
Arrays.fill(result, -1);
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
int index = stack.pop();
// nums[i] 是 nums[index] 右边第一个更大的元素
result[index] = nums[i];
}
stack.push(i);
}13.4 每日温度模板
Deque<Integer> stack = new ArrayDeque<>();
int[] answer = new int[temperatures.length];
for (int i = 0; i < temperatures.length; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int index = stack.pop();
// i - index 表示等了多少天
answer[index] = i - index;
}
stack.push(i);
}13.5 记忆口诀
找下一个更大，用递减栈
找下一个更小，用递增栈
当前元素破坏单调性，就弹出栈顶
栈里通常存下标，不直接存值十四、堆 / 优先队列模板
14.1 适用场景
堆 / 优先队列常用于：
- Top K 问题
- 第 K 大 / 第 K 小
- 合并 K 个有序链表
- 数据流中位数
- 按优先级取元素
常见关键词：最大、最小、第 K 个、Top K、优先级、动态取最大 / 最小
14.2 核心思想
优先队列可以快速取出当前最大值或最小值Java 默认是小顶堆：
PriorityQueue<Integer> pq = new PriorityQueue<>();大顶堆写法：
PriorityQueue<Integer> maxHeap =
new PriorityQueue<>((a, b) -> Integer.compare(b, a));14.3 常用操作
pq.offer(x); // 加入元素
pq.poll(); // 取出堆顶元素
pq.peek(); // 查看堆顶元素
pq.size(); // 堆中元素数量14.4 Top K 模板
适合求：
数组中第 K 大元素PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int num : nums) {
pq.offer(num);
if (pq.size() > k) {
pq.poll();
}
}
return pq.peek();14.5 自定义排序模板
适合对象或数组排序。
PriorityQueue<int[]> pq =
new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
pq.offer(new int[]{value, index});
int[] cur = pq.poll();14.6 记忆口诀
默认小顶堆
大顶堆要改排序
Top K 用大小为 k 的堆
每次取堆顶就是当前最优元素十五、树的遍历模板
15.1 适用场景
树的遍历常用于：
- 二叉树前序遍历
- 二叉树中序遍历
- 二叉树后序遍历
- 二叉树层序遍历
- 求树的深度
- 判断树是否对称
常见关键词：二叉树、遍历、深度、路径、子树、递归
15.2 核心思想
前序：根 -> 左 -> 右
中序：左 -> 根 -> 右
后序：左 -> 右 -> 根
层序：一层一层遍历15.3 前序遍历模板
public void preorder(TreeNode root) {
if (root == null) {
return;
}
// 先处理当前节点
visit(root);
preorder(root.left);
preorder(root.right);
}15.4 中序遍历模板
public void inorder(TreeNode root) {
if (root == null) {
return;
}
inorder(root.left);
// 中间处理当前节点
visit(root);
inorder(root.right);
}15.5 后序遍历模板
public void postorder(TreeNode root) {
if (root == null) {
return;
}
postorder(root.left);
postorder(root.right);
// 最后处理当前节点
visit(root);
}15.6 层序遍历模板
Queue<TreeNode> queue = new LinkedList<>();
if (root != null) {
queue.offer(root);
}
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
// 处理当前节点
visit(node);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}15.7 记忆口诀
前序根在前
中序根在中
后序根在后
层序用队列十六、图论模板
16.1 适用场景
图论常用于：
- 节点之间的关系
- 判断是否连通
- 是否存在路径
- 最短路径
- 拓扑排序
- 课程表问题
常见关键词：节点、边、路径、连通、依赖关系、先后顺序
16.2 图的表示方式
邻接表最常用：
List<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] edge : edges) {
int a = edge[0];
int b = edge[1];
graph[a].add(b);
}16.3 图的 DFS 模板
boolean[] visited = new boolean[n];
public void dfs(int cur, List<Integer>[] graph) {
if (visited[cur]) {
return;
}
visited[cur] = true;
for (int next : graph[cur]) {
dfs(next, graph);
}
}16.4 图的 BFS 模板
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[n];
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int next : graph[cur]) {
if (visited[next]) {
continue;
}
visited[next] = true;
queue.offer(next);
}
}16.5 拓扑排序模板
适合处理有依赖关系的问题。
int[] indegree = new int[n];
List<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] edge : edges) {
int from = edge[0];
int to = edge[1];
graph[from].add(to);
indegree[to]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
int count = 0;
while (!queue.isEmpty()) {
int cur = queue.poll();
count++;
for (int next : graph[cur]) {
indegree[next]--;
if (indegree[next] == 0) {
queue.offer(next);
}
}
}
// count == n 表示没有环
return count == n;16.6 记忆口诀
图用邻接表
遍历用 DFS / BFS
最短路径优先 BFS
依赖关系用拓扑排序
入度为 0 先入队
评论