极高进阶

校招高频算法题型与变种#

一句话答案#

校招算法面试 80% 的题可归入 10 种模式：双指针、滑动窗口、二分查找、BFS/DFS、回溯、动态规划、单调栈/队列、堆/TopK、前缀和/差分、并查集，识别模式比死记题目更重要。

核心要点

一、十大题型模式映射表

#	模式	识别信号	代表题	复杂度
1	双指针	有序数组、回文、链表相交/环	两数之和II、三数之和、接雨水	O(n)
2	滑动窗口	连续子数组/子串、最值、定长/变长	最小覆盖子串、无重复最长子串、长度最小子数组	O(n)
3	二分查找	有序/单调性、最小化最大值、查边界	搜索旋转数组、寻找峰值、Koko吃香蕉	O(log n)
4	BFS/DFS	图/树遍历、最短路径、连通分量	岛屿数量、二叉树层序遍历、课程表	O(V+E)
5	回溯	排列/组合/子集、棋盘类	全排列、N皇后、组合总和、电话号码字母组合	指数级
6	动态规划	最优子结构、重叠子问题、计数/最值	最长递增子序列、编辑距离、零钱兑换、背包问题	O(n²)或O(n×m)
7	单调栈/队列	下一个更大/更小、滑动窗口最值	每日温度、柱状图最大矩形、滑动窗口最大值	O(n)
8	堆/TopK	第K大/小、合并K个有序、流式中位数	前K个高频元素、合并K个排序链表、数据流中位数	O(n log k)
9	前缀和/差分	区间和查询、子数组和等于K	和为K的子数组、区间加法、航班预订统计	O(n)
10	并查集	连通性判断、集合合并	冗余连接、账户合并、最长连续序列	O(α(n))≈O(1)

二、各模式核心模板（Java）

双指针——对撞型

int left = 0, right = nums.length - 1;
while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == target) return new int[]{left, right};
    else if (sum < target) left++;
    else right--;
}

java

滑动窗口——变长窗口

int left = 0;
Map<Character, Integer> window = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    window.merge(c, 1, Integer::sum);
    while (/* 窗口需要收缩的条件 */) {
        char d = s.charAt(left);
        window.merge(d, -1, Integer::sum);
        left++;
    }
    // 更新答案
}

java

二分查找——左边界

int left = 0, right = nums.length; // 注意右边界
while (left < right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < target) left = mid + 1;
    else right = mid; // 收缩右边界找第一个>=target
}
return left;

java

BFS 模板

Queue<int[]> queue = new LinkedList<>();
queue.offer(start);
boolean[][] visited = new boolean[m][n];
int step = 0;
while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
        int[] cur = queue.poll();
        if (/* 到达终点 */) return step;
        for (int[] dir : dirs) {
            int nx = cur[0] + dir[0], ny = cur[1] + dir[1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                visited[nx][ny] = true;
                queue.offer(new int[]{nx, ny});
            }
        }
    }
    step++;
}

java

回溯模板

void backtrack(List<List<Integer>> res, List<Integer> path, int[] nums, int start) {
    if (/* 满足条件 */) { res.add(new ArrayList<>(path)); return; }
    for (int i = start; i < nums.length; i++) {
        if (/* 剪枝条件 */) continue;
        path.add(nums[i]);
        backtrack(res, path, nums, i + 1); // 组合用i+1，排列用0+visited
        path.remove(path.size() - 1);      // 撤销选择
    }
}

java

动态规划——框架

// 1. 定义状态：dp[i] = 以nums[i]结尾的最优解
// 2. 状态转移：dp[i] = max/min(dp[j] + ...) for all valid j
// 3. 初始化：dp[0] = base case
// 4. 遍历顺序：确保计算dp[i]时所依赖的dp[j]已经算过
// 5. 返回值：dp[n-1] 或 max(dp[0..n-1])

java

单调栈——下一个更大元素

Deque<Integer> stack = new ArrayDeque<>();
int[] res = new int[nums.length];
Arrays.fill(res, -1);
for (int i = 0; i < nums.length; i++) {
    while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
        res[stack.pop()] = nums[i];
    }
    stack.push(i);
}

java

三、变种识别技巧

原题	变种	关键差异
两数之和（哈希）	三数之和（排序+双指针）	增加一层循环+去重
二分查找精确值	二分查找左/右边界	while条件和边界更新不同
岛屿数量（DFS）	岛屿最大面积	DFS返回面积并累加
全排列（无重复）	全排列II（有重复）	先排序+跳过相邻重复
0-1背包	完全背包	内层循环正序 vs 倒序
LRU缓存	LFU缓存	增加频率维度+双哈希
最长递增子序列O(n²)	最长递增子序列O(nlogn)	patience sorting + 二分

四、高频校招真题清单（Top 30）

难度	题目	模式	出现频率
Easy	两数之和	哈希	★★★★★
Easy	反转链表	链表	★★★★★
Easy	有效括号	栈	★★★★
Easy	合并两个有序链表	链表	★★★★
Easy	二叉树最大深度	DFS	★★★★
Medium	三数之和	双指针	★★★★★
Medium	无重复最长子串	滑动窗口	★★★★★
Medium	LRU缓存	哈希+链表	★★★★★
Medium	二叉树层序遍历	BFS	★★★★
Medium	全排列	回溯	★★★★
Medium	零钱兑换	DP	★★★★
Medium	最长递增子序列	DP/二分	★★★★
Medium	岛屿数量	DFS	★★★★
Medium	搜索旋转排序数组	二分	★★★★
Medium	每日温度	单调栈	★★★
Medium	合并区间	排序	★★★
Medium	课程表	拓扑排序	★★★
Medium	前K个高频元素	堆	★★★
Medium	最小覆盖子串	滑动窗口	★★★
Medium	最长回文子串	双指针/DP	★★★
Medium	和为K的子数组	前缀和	★★★
Medium	最小路径和	DP	★★★
Medium	组合总和	回溯	★★★
Hard	接雨水	双指针/单调栈	★★★★
Hard	合并K个排序链表	堆	★★★
Hard	滑动窗口最大值	单调队列	★★★
Hard	编辑距离	DP	★★★
Hard	柱状图最大矩形	单调栈	★★
Hard	数据流中位数	双堆	★★
Hard	N皇后	回溯	★★

五、手写注意事项

边界处理：空数组、单元素、全相同元素、Integer溢出（用 long 或 mid = left + (right-left)/2）
循环不变量：明确定义 [left, right] 还是 [left, right) 并全程保持一致
返回值：确认返回索引还是值、是否需要排序/去重
复杂度分析：主动说出时间和空间复杂度
测试用例：写完后用 1-2 个边界 case 手动跑一遍

面试回答（2分钟版）

我准备算法的方式是按模式分类刷题，把常见题归入十种模式：双指针、滑动窗口、二分、BFS/DFS、回溯、DP、单调栈、堆、前缀和、并查集。面试时我先识别题目属于哪种模式再套模板。比如看到连续子数组求最值就想到滑动窗口，看到有序或单调性就想二分，看到排列组合就想回溯。每种模式我都有一个核心模板，变种只是在模板基础上改条件或加约束。比如全排列有重复元素的变种就是先排序再跳过相邻重复。手写代码时我特别注意三件事：边界处理确保不越界，循环不变量保持一致，写完后用边界case手动验证。

追问与易错

追问方向：

“滑动窗口什么时候用定长什么时候用变长？”→ 定长：求定长子数组最值；变长：求满足条件的最短/最长子数组
“DP 怎么判断用一维还是二维？”→ 看状态依赖几个维度：一个序列一维，两个序列或矩阵二维
“回溯怎么剪枝？”→ 排序后跳重复、提前判断不可能满足条件、记忆化
“什么时候用 BFS 什么时候用 DFS？”→ 最短路径/层序用BFS，路径搜索/连通性/树遍历用DFS
“时间复杂度怎么快速分析？”→ 看循环嵌套层数、递归树深度×宽度、是否有二分/排序

易错点：

❌ 二分查找 mid = (left+right)/2 溢出——用 left + (right-left)/2
❌ 回溯忘记撤销选择——每次 add 后必须有对应 remove
❌ 滑动窗口忘记收缩——while 条件写错导致窗口只扩不缩
❌ DP 初始化不完整——忘了 dp[0] 或 dp[0][j] 的 base case
❌ DFS 忘记标记已访问——导致死循环或重复计算
✅ 写完代码主动说复杂度+跑边界case，面试官印象分很高