02.1.1.4 高频解题框架
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.1 复杂度分析与解题框架 / 02.1.1 复杂度与解题框架
02.1.1.4-001 面试解题的通用六步框架是什么?
一句话结论
读题确认边界 → 先给暴力解并报复杂度 → 找结构性质选优化框架 → 口述步骤与不变量 → 写代码处理边界 → 补测试用例与复杂度收尾。
概念解释
- 先确认输入规模、是否有序、可否修改、有无负数/重复。
- 暴力解体现你能先把问题做对。
- 优化从结构性质出发,而不是凭空背题。
原理流程
- 复述题意,确认输入输出与约束。
- 写暴力思路,标注复杂度。
- 观察有序性、重复性、最值性,选框架。
- 口述算法步骤与维护的不变量。
- 编码,先处理空值与越界。
- 跑边界用例,汇报复杂度与可优化点。
代码 / 图示
题意确认 → 暴力 O(?) → 结构观察 → 框架选择
→ 口述不变量 → 编码 → 边界用例 → 复杂度收尾
常见误区
- 误区:上来直接写最优解;正解:先讲暴力与优化路径,展示推导过程。
- 误区:不确认约束就假设数组有序;正解:有序、可变性、数值范围必须先问清。
追问
- Q:完全没思路怎么办? A:从暴力枚举出发,画最小例子找重复与规律。
- Q:面试官打断让直接写? A:先一句话说清思路与复杂度,再进入编码。
02.1.1.4-002 双指针框架分哪几类?
一句话结论
双指针分相向双指针(左右夹逼,多用于有序数组/回文)、同向双指针(快慢指针,多用于原地划分/窗口)、分离双指针(两数组归并);按指针移动方向与条件选择。
概念解释
- 相向:l 从左、r 从右,向中间靠。
- 同向:两指针同方向,一快一慢或左右边界。
- 分离:两个序列各持指针,按大小推进。
原理流程
- 判断数组是否有序或可排序。
- 选指针方向与移动条件。
- 维护指针间不变量(已处理/满足条件)。
- 处理重复元素去重。
代码 / 示例
// 相向:有序数组两数之和
int l = 0, r = a.length - 1;
while (l < r) {
int s = a[l] + a[r];
if (s == target) return new int[]{l, r};
if (s < target) l++; else r--;
}
常见误区
- 误区:无序数组也直接相向双指针;正解:相向依赖有序性,无序先排序或改哈希。
- 误区:双指针一定 O(1) 空间;正解:排序预处理的代价要另算。
追问
- Q:快慢指针在数组上做什么? A:原地划分(移动零、去重),慢指针写位置,快指针扫描。
- Q:两数之和有序用双指针还是哈希? A:双指针 O(1) 空间,哈希 O(n) 空间但不要求有序。
02.1.1.4-003 滑动窗口框架的固定结构是什么?
一句话结论
右指针扩张窗口加入新元素,更新窗口状态;不满足条件时左指针收缩直到重新合法;每步更新答案;窗口只右移不回退。
概念解释
- 窗口:[left, right] 连续区间。
- 状态:窗口内计数、和、字符集等。
- 合法性:题目给定的约束(无重复、和不超 K 等)。
原理流程
- 初始化 left=0 与窗口状态。
- right 遍历,加入元素并更新状态。
- 不合法则 while 收缩 left,同步移除状态。
- 合法后更新最优答案。
代码 / 示例
int left = 0, ans = 0;
Map<Character, Integer> win = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
add(s.charAt(right), win);
while (!valid(win)) {
remove(s.charAt(left++), win);
}
ans = Math.max(ans, right - left + 1);
}
常见误区
- 误区:左边界可以回退;正解:窗口单调右移,回退会破坏线性复杂度。
- 误区:收缩用 if 不用 while;正解:可能需要连续移出多个元素才能合法,必须 while。
追问
- Q:定长窗口怎么写? A:right 到长度后,每次左右同步移动,维护固定大小。
- Q:窗口状态怎么更新才不漏? A:加入与移除成对写清,更新计数后再判合法性。
02.1.1.4-004 前缀和框架解决什么问题?
一句话结论
前缀和把区间和 a[l..r] 转成 pre[r+1]-pre[l],把区间求和从 O(n) 降到 O(1);配合哈希可在 O(n) 内统计满足条件的子数组。
概念解释
- pre[i]:前 i 个元素之和。
- 区间和:差分数式。
- 前缀和不要求元素非负;单调性只在非负时成立。
原理流程
- 预处理前缀和数组。
- 区间查询做差。
- 子数组计数:用哈希记录历史前缀和出现次数。
代码 / 示例
int[] pre = new int[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
// 区间 [l, r] 和 = pre[r + 1] - pre[l]
常见误区
- 误区:前缀和要求数组有序;正解:前缀和只做累加,负数也适用。
- 误区:下标错位;正解:pre 长度 n+1,区间右端对应 pre[r+1]。
追问
- Q:和为 K 的子数组个数? A:哈希存前缀和出现次数,查
pre - K。 - Q:二维前缀和? A:四个角做差,容斥减去重叠区域。
02.1.1.4-005 差分框架解决什么问题?
一句话结论
差分数组把区间批量加减转成两个端点修改:diff[l]+=v、diff[r+1]-=v,最后前缀和还原;多次区间更新后一次性求值,避免逐元素遍历。
概念解释
- diff:相邻元素差值。
- 区间更新:只动两端。
- 还原:对 diff 求前缀和得原数组。
原理流程
- 初始化 diff 与原数组同长(多一位防越界)。
- 每个区间操作改两个端点。
- 最后扫描求前缀和还原。
代码 / 示例
// 区间 [l, r] 全部 +v
diff[l] += v;
if (r + 1 < n) diff[r + 1] -= v;
// 还原
for (int i = 1; i < n; i++) diff[i] += diff[i - 1];
常见误区
- 误区:差分可以直接查询区间和;正解:差分服务批量更新,查询需还原或配合前缀和。
- 误区:忘记 r+1 越界判断;正解:右端点后一位可能超出数组,需截断。
追问
- Q:差分与前缀和什么关系? A:互为逆运算,前缀和还原差分,差分刻画增量。
- Q:二维差分怎么做? A:四个角容斥修改,还原时二维前缀和。
02.1.1.4-006 二分框架的边界口径怎么统一?
一句话结论
先明确搜索区间是闭区间还是左闭右开,循环条件、收缩边界与返回值口径保持一致;常见写法 [l, r] 闭区间,m = l + (r-l)/2,按比较结果收缩。
概念解释
- 区间口径:决定
r = m-1还是r = m。 - 防溢出:
l + (r-l)/2替代(l+r)/2。 - 查找目标:等于返回;找边界用收缩到极值的写法。
原理流程
- 确认区间定义与单调性。
- 写循环条件与中点。
- 比较后收缩一侧,排除已判定位置。
- 出循环后按口径判断未命中。
代码 / 示例
int l = 0, r = n - 1; // 闭区间
while (l <= r) {
int m = l + (r - l) / 2;
if (a[m] == target) return m;
if (a[m] < target) l = m + 1;
else r = m - 1;
}
return -1;
常见误区
- 误区:闭区间写成
while (l < r);正解:口径要配套,混用会漏元素或死循环。 - 误区:
(l+r)/2可能溢出;正解:用l + (r-l)/2。
追问
- Q:找第一个 ≥ target 的位置? A:左闭右开收缩,
r = m,l = m+1,返回 l。 - Q:二分前提不满足怎么办? A:必须有可判断方向的单调性,否则不能二分。
02.1.1.4-007 DFS 框架怎么写?
一句话结论
DFS 按"终止条件 → 处理当前节点 → 递归各分支 → 必要时撤销状态"组织;树/图上注意访问标记,避免重复走环。
概念解释
- 终止条件:越界、空节点、已访问、满足目标。
- 分支:邻接节点或选择项。
- 状态撤销:回溯类问题在递归后恢复现场。
原理流程
- 定义递归函数签名与返回值。
- 写终止与边界判断。
- 标记访问、处理当前层。
- 递归子分支,回退标记。
代码 / 示例
void dfs(int[][] g, int u, boolean[] vis) {
vis[u] = true;
for (int v : g[u]) {
if (!vis[v]) dfs(g, v, vis);
}
}
常见误区
- 误区:图上 DFS 不标记访问;正解:无标记会在环上无限递归。
- 误区:回溯后忘记撤销选择;正解:共享状态必须在递归返回后恢复。
追问
- Q:DFS 空间复杂度? A:递归栈 O(h),h 为搜索深度。
- Q:DFS 与 BFS 怎么选? A:找路径/全部解用 DFS,最短层数用 BFS。
02.1.1.4-008 BFS 框架怎么写?
一句话结论
BFS 用队列按层扩展:起点入队并标记,逐层出队、扩展未访问邻居入队;天然按距离递增,适合最短步数与层序遍历。
概念解释
- 队列:保存待扩展节点。
- 访问标记:入队即标记,避免重复入队。
- 层数:可按层大小分批处理。
原理流程
- 起点入队并标记。
- 队列非空:出队,处理。
- 邻居未访问则标记入队。
- 需要层数时每轮按队列大小分层。
代码 / 示例
Queue<Integer> q = new ArrayDeque<>();
q.offer(start);
vis[start] = true;
while (!q.isEmpty()) {
int u = q.poll();
for (int v : g[u]) {
if (!vis[v]) { vis[v] = true; q.offer(v); }
}
}
常见误区
- 误区:出队时才标记访问;正解:入队时标记,否则同一节点被多个邻居重复入队。
- 误区:BFS 适合求所有路径;正解:BFS 强项是最少步数,穷举所有解更常用 DFS。
追问
- Q:如何记录步数? A:分层处理或节点携带距离信息。
- Q:双向 BFS 解决什么? A:起点与终点同时扩展,缩小搜索前沿。
02.1.1.4-009 回溯框架的固定结构是什么?
一句话结论
回溯 = 选择 → 递归 → 撤销选择;在决策树上深度优先遍历,满足约束才深入,走到叶子记录结果,回退时恢复现场。
概念解释
- 选择列表:当前层可选元素。
- 路径:已做选择。
- 剪枝:不满足约束的分支提前返回。
原理流程
- 维护当前路径与候选列表。
- 遍历选择:加入路径、递归、撤销。
- 到达目标长度记录结果。
- 重复元素先排序再按规则跳过。
代码 / 示例
void backtrack(List<Integer> path, int[] nums, boolean[] used) {
if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true; path.add(nums[i]);
backtrack(path, nums, used);
path.remove(path.size() - 1); used[i] = false;
}
}
常见误区
- 误区:记录结果直接引用路径;正解:必须拷贝一份,否则后续撤销会改掉已存结果。
- 误区:重复排列不去重;正解:排序后同层跳过相等元素。
追问
- Q:回溯与 DFS 区别? A:回溯是带路径状态与撤销的 DFS,强调枚举选择。
- Q:剪枝条件写在哪? A:进入递归前判断,不合法直接 continue/return。
02.1.1.4-010 DP 状态设计的步骤是什么?
一句话结论
先定义状态含义(dp[i] 代表什么)→ 找最后一步的选择 → 写状态转移 → 确定初始化与遍历顺序 → 核对空间能否压缩。
概念解释
- 状态:描述子问题的最少变量。
- 转移:当前状态由哪些前驱推出。
- 初始化:边界子问题的已知值。
原理流程
- 明确 dp 下标与语义。
- 枚举最后一步决策,写转移方程。
- 填初始值,按依赖顺序填表。
- 检查答案位置与空间压缩可能。
代码 / 示例
爬楼梯:dp[i] = 到第 i 阶的方法数
转移:dp[i] = dp[i-1] + dp[i-2]
初始化:dp[0]=1, dp[1]=1
答案:dp[n]
常见误区
- 误区:状态定义含糊就写转移;正解:先把 dp[i] 的自然语言含义写清。
- 误区:遍历顺序与依赖方向矛盾;正解:被依赖的状态必须先算出。
追问
- Q:什么是无后效性? A:当前状态确定后,未来决策不受到达路径影响。
- Q:空间压缩条件? A:转移只依赖前一行/前几项时,可用滚动变量。
02.1.1.4-011 单调栈框架解决哪类问题?
一句话结论
单调栈用于找"左右第一个更大/更小"的位置;栈内保持单调递增或递减序列,新元素弹出破坏单调性的栈顶,结算对应答案。
概念解释
- 递增栈:栈底到栈顶递增,弹出时遇到右侧更大值。
- 递减栈:对应右侧更小值。
- 每个元素入栈、出栈各一次,O(n)。
原理流程
- 遍历元素,当前值与栈顶比较。
- 破坏单调性则弹出并记录答案。
- 当前元素入栈。
- 遍历完栈内剩余元素按边界结算。
代码 / 示例
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && a[st.peek()] < a[i]) {
int idx = st.pop();
// a[i] 是 idx 右侧第一个更大
}
st.push(i);
}
常见误区
- 误区:栈存值不存下标;正解:需要算距离/宽度时必须存下标。
- 误区:弹出条件方向写反;正解:先明确要找更大还是更小,再定栈的单调性。
追问
- Q:单调栈为什么 O(n)? A:每个元素最多入栈出栈一次。
- Q:柱状图最大矩形用哪种栈? A:递增栈,弹出时以柱高为矩形高计算左右宽度。
02.1.1.4-012 单调队列框架解决什么问题?
一句话结论
单调队列维护窗口内候选最值,队首保持当前最大(或最小);新元素从队尾剔除劣值,队首越界则出队,滑动窗口最值 O(n)。
概念解释
- 双端队列:队首出结果,队尾维护候选。
- 单调性:递减队列队首最大。
- 下标入队:判断是否滑出窗口。
原理流程
- 新元素入队前,队尾劣于它的全部弹出。
- 队首下标超出窗口则弹出。
- 队首即窗口最值。
代码 / 示例
Deque<Integer> q = new ArrayDeque<>(); // 存下标,值递减
for (int i = 0; i < n; i++) {
while (!q.isEmpty() && a[q.peekLast()] <= a[i]) q.pollLast();
q.offerLast(i);
if (q.peekFirst() <= i - k) q.pollFirst();
if (i >= k - 1) ans[i - k + 1] = a[q.peekFirst()];
}
常见误区
- 误区:单调队列就是普通队列;正解:队尾可弹出,是双端队列。
- 误区:存值不存下标;正解:需要按窗口位置淘汰队首,必须存下标。
追问
- Q:与堆求窗口最值区别? A:堆 O(n log k),单调队列 O(n),但只适用于滑动窗口结构。
- Q:队尾弹出条件怎么定? A:按要最大还是最小,弹出劣于新元素的候选。
02.1.1.4-013 哈希表提速框架怎么用?
一句话结论
需要"按值快速查存在性/下标/计数"时用哈希表把内层查找降到 O(1);一遍扫描中边查边放,避免同一元素重复使用。
概念解释
- 键:题目用来匹配的值。
- 值:下标、计数、原始记录。
- 平均 O(1),最坏冲突另算。
原理流程
- 确定匹配键。
- 扫描元素,先查哈希再写入。
- 命中即得结果;未命中则登记当前元素。
代码 / 示例
Map<Integer, Integer> idx = new HashMap<>();
for (int i = 0; i < n; i++) {
int need = target - a[i];
if (idx.containsKey(need)) return new int[]{idx.get(need), i};
idx.put(a[i], i);
}
常见误区
- 误区:先全部放入再扫描;正解:两数之和场景先查后放,避免元素自匹配。
- 误区:哈希表无条件 O(1);正解:最坏冲突退化,均匀性依赖哈希函数。
追问
- Q:计数用什么结构? A:哈希表计数,范围已知时用数组更快。
- Q:键是数组/字符串怎么办? A:自定义可哈希结构或转为可哈希表示。
02.1.1.4-014 堆(优先队列)框架解决什么问题?
一句话结论
动态维护 Top-K、合并有序序列、取最值时用堆;小顶堆保最大 K 个,大顶堆保最小 K 个,入堆出堆 O(log k)。
概念解释
- 堆:完全二叉树,父节点与子节点满足堆序。
- 小顶堆:堆顶最小;用于保留最大 K 个。
- 规模 k 时整体 O(n log k)。
原理流程
- 明确要最大 K 还是最小 K。
- 选对应堆型。
- 堆满后与堆顶比较,劣值剔除。
代码 / 示例
// 最大 K 个:小顶堆
Queue<Integer> heap = new PriorityQueue<>();
for (int x : nums) {
heap.offer(x);
if (heap.size() > k) heap.poll();
}
常见误区
- 误区:求最大 K 个用大顶堆;正解:小顶堆堆顶是 K 个中的最小值,便于淘汰。
- 误区:堆排序是原地结构所以空间 O(1);正解:堆化在数组上可原地,但优先队列容器另有存储。
追问
- Q:合并 K 个有序链表? A:小顶堆存 K 个当前节点,每次取堆顶。
- Q:堆与排序选哪个? A:只需 Top-K 用堆 O(n log k);全量排序 O(n log n)。
02.1.1.4-015 排序配合双指针的套路是什么?
一句话结论
先排序获得有序性,再用双指针夹逼或枚举固定点;去重在固定点与指针移动处跳过重复,适用于三数之和、区间合并类问题。
概念解释
- 排序打破原顺序,题目不要求保序时可用。
- 有序后移动方向唯一,避免内层枚举。
- 去重:相等元素跳过相同分支。
原理流程
- 排序。
- 固定外层枚举点。
- 内层双指针按和值移动。
- 命中后跳过重复值。
代码 / 示例
Arrays.sort(a);
for (int i = 0; i < n - 2; i++) {
if (i > 0 && a[i] == a[i - 1]) continue;
int l = i + 1, r = n - 1;
while (l < r) {
int s = a[i] + a[l] + a[r];
if (s == 0) { /* 记录,跳过重复 */ l++; r--; }
else if (s < 0) l++; else r--;
}
}
常见误区
- 误区:排序后忘记去重;正解:固定点与双指针命中处都要跳重复。
- 误区:题目要求输出原下标还排序;正解:需保留下标映射,排序会打乱原位置。
追问
- Q:四数之和怎么扩展? A:外层两层枚举 + 内层双指针,配合剪枝。
- Q:排序代价计入复杂度吗? A:计入,整体为 O(n log n) + 双指针轮次。
02.1.1.4-016 模拟与分类讨论框架怎么用?
一句话结论
规则明确但无高级结构可用时,按题意模拟过程,先把输入分情况讨论清楚,再逐类实现;重点是状态转移规则与边界分支不遗漏。
概念解释
- 模拟:忠实复现题目过程。
- 分类:按取值范围、符号、位置分情况。
- 状态机:复杂流程拆成状态与转移。
原理流程
- 列全所有输入情形。
- 为每种情形写处理规则。
- 主流程按规则调度。
- 用边界用例覆盖各分支。
代码 / 图示
分类清单:
空输入 / 单元素 / 首尾位置
正 / 负 / 零
越界 / 等值 / 重复
常见误区
- 误区:只写正常分支;正解:边界与特殊值必须单列。
- 误区:模拟题不需要复杂度分析;正解:仍要统计循环与辅助空间量级。
追问
- Q:状态机怎么落地? A:枚举状态值,按输入驱动转移,避免散落 if。
- Q:模拟题容易错在哪? A:下标、方向、进位与边界条件,需用例逐条核对。
02.1.1.4-017 边界用例清单有哪些必查项?
一句话结论
必查:空输入、单元素、两个元素、全部相等、严格递增/递减、含重复、含负数/零/最大值、越界下标、整数溢出;按题目补特殊约束。
概念解释
- 空与最小规模:验证初始条件。
- 极端值:验证比较与溢出。
- 重复与对称:验证去重与指针收敛。
原理流程
- 编码前列出输入规模下限。
- 构造边界与极端用例。
- 手算预期结果后跑代码对照。
代码 / 图示
清单:
[] / [x] / [x,x] / 已排序 / 逆序
含 0、负数、Integer.MAX_VALUE
目标不存在 / 目标在首尾
常见误区
- 误区:只测正常例子;正解:面试官常补边界用例考察严谨性。
- 误区:溢出靠语言默认行为;正解:相加前判断上溢下溢,必要时用更大类型。
追问
- Q:两数之和负数怎么测? A:正负相消、同号相加分别构造。
- Q:链表为空与只有一个节点? A:反转、合并、删除倒数第 N 都要覆盖。
02.1.1.4-018 口述思路与写代码的顺序怎么安排?
一句话结论
先一句话结论 + 复杂度,再讲数据结构与关键步骤,确认方向后写骨架(函数签名、主循环、返回),填细节,最后补边界与用例。
概念解释
- 先说思路避免写错方向返工。
- 骨架先行:结构正确后填局部逻辑。
- 边写边解释不变量。
原理流程
- 报方案与复杂度。
- 口述指针/状态定义。
- 写主流程骨架。
- 填分支与边界处理。
- 跑用例验证。
代码 / 图示
汇报:"用左右双指针,有序数组,O(n) 时间 O(1) 空间"
骨架:函数 → 指针初始化 → while → 比较移动 → 返回
细节:去重、越界、空输入
常见误区
- 误区:闷头写完全程不沟通;正解:关键决策点先与面试官对齐。
- 误区:代码细节卡壳时停住;正解:先说清卡在哪、备选方案是什么。
追问
- Q:写代码时被打断提问怎么办? A:先回答概念问题,再回到已写部分继续。
- Q:要不要先命名变量? A:变量名体现语义,先定好状态名再写逻辑。