第 01 课
14 种经典模式
双指针、滑动窗口、前缀和、单调栈等。
课程内容
14 种经典刷题模式
算法面试的题目千变万化，但底层模式只有十几种。掌握模式后，看到新题就能快速归类、套用模板。本课是 DSA 课程的模式总览与刷题路线。
模式速查表
| 模式 | 识别信号 | 经典题 |
|---|---|---|
| 双指针 | 有序数组、首尾逼近 | 两数之和 II、盛水最多的容器 |
| 滑动窗口 | 连续子串/子数组 + 最值 | 无重复字符的最长子串 |
| 快慢指针 | 链表环、中点 | 环形链表、链表的中间结点 |
| 前缀和 | 区间和查询 | 和为 K 的子数组 |
| 单调栈 | 下一个更大/更小元素 | 每日温度、柱状图最大矩形 |
| 二分查找 | 有序 / 答案可二分 | 搜索旋转排序数组、爱吃香蕉的珂珂 |
| BFS | 最短路径、层序 | 二叉树层序遍历、岛屿数量 |
| DFS / 回溯 | 所有组合、排列、子集 | 全排列、组合总和、N 皇后 |
| 动态规划 | 最值/计数 + 重叠子问题 | 爬楼梯、最长递增子序列 |
| 贪心 | 局部最优推全局最优 | 跳跃游戏、分发饼干 |
| 堆（优先队列） | 第 K 大/小、流式数据 | 数组中第 K 大元素、数据流中位数 |
| 并查集 | 连通性问题 | 省份数量、冗余连接 |
| 字典树 Trie | 前缀匹配 | 实现 Trie、单词搜索 II |
| 位运算 | 状态压缩、出现次数 | 只出现一次的数字 |
两个最常用模式的模板
滑动窗口
// 模板：求满足条件的最长/最短子串
int left = 0;
Map<Character, Integer> window = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
// 1. 右指针进入窗口
char c = s.charAt(right);
window.merge(c, 1, Integer::sum);
// 2. 窗口不满足条件时收缩左边界
while (/* 需要收缩 */) {
char d = s.charAt(left);
window.merge(d, -1, Integer::sum);
left++;
}
// 3. 更新答案
}
回溯
void backtrack(路径, 选择列表) {
if (满足结束条件) {
结果.add(new ArrayList<>(路径));
return;
}
for (选择 : 选择列表) {
做选择; // 路径.add(选择)
backtrack(路径, 选择列表); // 递归
撤销选择; // 路径.removeLast()
}
}
刷题路线（配合本站 DSA 课程）
- 第 1~2 周：数组 + 哈希表 + 双指针（对应 DSA 第 8~10 课作业）
- 第 3~4 周：链表 + 栈/队列 + 二分查找（DSA 第 18~19 课作业）
- 第 5~6 周：树 + 回溯 + DFS/BFS（DSA 第 14、20 课作业）
- 第 7~8 周：动态规划 + 贪心 + 堆，混合刷题
刷题方法论
- 15 分钟原则：毫无思路就看题解，看懂后关掉题解自己默写，隔 3 天重做
- 每道题记录：模式、关键思路、易错点（用本站进度标记 + 笔记）
- 宁可一道题做三遍，不要三道题各做一遍