罗罗编程学习记录
本页内容 展开查看

02.1.1.4 高频解题框架

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.1 复杂度分析与解题框架 / 02.1.1 复杂度与解题框架

02.1.1.4-001 面试解题的通用六步框架是什么?

一句话结论

读题确认边界 → 先给暴力解并报复杂度 → 找结构性质选优化框架 → 口述步骤与不变量 → 写代码处理边界 → 补测试用例与复杂度收尾。

概念解释

  • 先确认输入规模、是否有序、可否修改、有无负数/重复。
  • 暴力解体现你能先把问题做对。
  • 优化从结构性质出发,而不是凭空背题。

原理流程

  1. 复述题意,确认输入输出与约束。
  2. 写暴力思路,标注复杂度。
  3. 观察有序性、重复性、最值性,选框架。
  4. 口述算法步骤与维护的不变量。
  5. 编码,先处理空值与越界。
  6. 跑边界用例,汇报复杂度与可优化点。

代码 / 图示

题意确认 → 暴力 O(?) → 结构观察 → 框架选择
→ 口述不变量 → 编码 → 边界用例 → 复杂度收尾

常见误区

  • 误区:上来直接写最优解;正解:先讲暴力与优化路径,展示推导过程。
  • 误区:不确认约束就假设数组有序;正解:有序、可变性、数值范围必须先问清。

追问

  • Q:完全没思路怎么办? A:从暴力枚举出发,画最小例子找重复与规律。
  • Q:面试官打断让直接写? A:先一句话说清思路与复杂度,再进入编码。

02.1.1.4-002 双指针框架分哪几类?

一句话结论

双指针分相向双指针(左右夹逼,多用于有序数组/回文)、同向双指针(快慢指针,多用于原地划分/窗口)、分离双指针(两数组归并);按指针移动方向与条件选择。

概念解释

  • 相向:l 从左、r 从右,向中间靠。
  • 同向:两指针同方向,一快一慢或左右边界。
  • 分离:两个序列各持指针,按大小推进。

原理流程

  1. 判断数组是否有序或可排序。
  2. 选指针方向与移动条件。
  3. 维护指针间不变量(已处理/满足条件)。
  4. 处理重复元素去重。

代码 / 示例

// 相向:有序数组两数之和
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 等)。

原理流程

  1. 初始化 left=0 与窗口状态。
  2. right 遍历,加入元素并更新状态。
  3. 不合法则 while 收缩 left,同步移除状态。
  4. 合法后更新最优答案。

代码 / 示例

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 个元素之和。
  • 区间和:差分数式。
  • 前缀和不要求元素非负;单调性只在非负时成立。

原理流程

  1. 预处理前缀和数组。
  2. 区间查询做差。
  3. 子数组计数:用哈希记录历史前缀和出现次数。

代码 / 示例

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 求前缀和得原数组。

原理流程

  1. 初始化 diff 与原数组同长(多一位防越界)。
  2. 每个区间操作改两个端点。
  3. 最后扫描求前缀和还原。

代码 / 示例

// 区间 [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。
  • 查找目标:等于返回;找边界用收缩到极值的写法。

原理流程

  1. 确认区间定义与单调性。
  2. 写循环条件与中点。
  3. 比较后收缩一侧,排除已判定位置。
  4. 出循环后按口径判断未命中。

代码 / 示例

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 按"终止条件 → 处理当前节点 → 递归各分支 → 必要时撤销状态"组织;树/图上注意访问标记,避免重复走环。

概念解释

  • 终止条件:越界、空节点、已访问、满足目标。
  • 分支:邻接节点或选择项。
  • 状态撤销:回溯类问题在递归后恢复现场。

原理流程

  1. 定义递归函数签名与返回值。
  2. 写终止与边界判断。
  3. 标记访问、处理当前层。
  4. 递归子分支,回退标记。

代码 / 示例

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 用队列按层扩展:起点入队并标记,逐层出队、扩展未访问邻居入队;天然按距离递增,适合最短步数与层序遍历。

概念解释

  • 队列:保存待扩展节点。
  • 访问标记:入队即标记,避免重复入队。
  • 层数:可按层大小分批处理。

原理流程

  1. 起点入队并标记。
  2. 队列非空:出队,处理。
  3. 邻居未访问则标记入队。
  4. 需要层数时每轮按队列大小分层。

代码 / 示例

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 回溯框架的固定结构是什么?

一句话结论

回溯 = 选择 → 递归 → 撤销选择;在决策树上深度优先遍历,满足约束才深入,走到叶子记录结果,回退时恢复现场。

概念解释

  • 选择列表:当前层可选元素。
  • 路径:已做选择。
  • 剪枝:不满足约束的分支提前返回。

原理流程

  1. 维护当前路径与候选列表。
  2. 遍历选择:加入路径、递归、撤销。
  3. 到达目标长度记录结果。
  4. 重复元素先排序再按规则跳过。

代码 / 示例

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] 代表什么)→ 找最后一步的选择 → 写状态转移 → 确定初始化与遍历顺序 → 核对空间能否压缩。

概念解释

  • 状态:描述子问题的最少变量。
  • 转移:当前状态由哪些前驱推出。
  • 初始化:边界子问题的已知值。

原理流程

  1. 明确 dp 下标与语义。
  2. 枚举最后一步决策,写转移方程。
  3. 填初始值,按依赖顺序填表。
  4. 检查答案位置与空间压缩可能。

代码 / 示例

爬楼梯: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)。

原理流程

  1. 遍历元素,当前值与栈顶比较。
  2. 破坏单调性则弹出并记录答案。
  3. 当前元素入栈。
  4. 遍历完栈内剩余元素按边界结算。

代码 / 示例

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)。

概念解释

  • 双端队列:队首出结果,队尾维护候选。
  • 单调性:递减队列队首最大。
  • 下标入队:判断是否滑出窗口。

原理流程

  1. 新元素入队前,队尾劣于它的全部弹出。
  2. 队首下标超出窗口则弹出。
  3. 队首即窗口最值。

代码 / 示例

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),最坏冲突另算。

原理流程

  1. 确定匹配键。
  2. 扫描元素,先查哈希再写入。
  3. 命中即得结果;未命中则登记当前元素。

代码 / 示例

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)。

原理流程

  1. 明确要最大 K 还是最小 K。
  2. 选对应堆型。
  3. 堆满后与堆顶比较,劣值剔除。

代码 / 示例

// 最大 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 排序配合双指针的套路是什么?

一句话结论

先排序获得有序性,再用双指针夹逼或枚举固定点;去重在固定点与指针移动处跳过重复,适用于三数之和、区间合并类问题。

概念解释

  • 排序打破原顺序,题目不要求保序时可用。
  • 有序后移动方向唯一,避免内层枚举。
  • 去重:相等元素跳过相同分支。

原理流程

  1. 排序。
  2. 固定外层枚举点。
  3. 内层双指针按和值移动。
  4. 命中后跳过重复值。

代码 / 示例

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 模拟与分类讨论框架怎么用?

一句话结论

规则明确但无高级结构可用时,按题意模拟过程,先把输入分情况讨论清楚,再逐类实现;重点是状态转移规则与边界分支不遗漏。

概念解释

  • 模拟:忠实复现题目过程。
  • 分类:按取值范围、符号、位置分情况。
  • 状态机:复杂流程拆成状态与转移。

原理流程

  1. 列全所有输入情形。
  2. 为每种情形写处理规则。
  3. 主流程按规则调度。
  4. 用边界用例覆盖各分支。

代码 / 图示

分类清单:
空输入 / 单元素 / 首尾位置
正 / 负 / 零
越界 / 等值 / 重复

常见误区

  • 误区:只写正常分支;正解:边界与特殊值必须单列。
  • 误区:模拟题不需要复杂度分析;正解:仍要统计循环与辅助空间量级。

追问

  • Q:状态机怎么落地? A:枚举状态值,按输入驱动转移,避免散落 if。
  • Q:模拟题容易错在哪? A:下标、方向、进位与边界条件,需用例逐条核对。

02.1.1.4-017 边界用例清单有哪些必查项?

一句话结论

必查:空输入、单元素、两个元素、全部相等、严格递增/递减、含重复、含负数/零/最大值、越界下标、整数溢出;按题目补特殊约束。

概念解释

  • 空与最小规模:验证初始条件。
  • 极端值:验证比较与溢出。
  • 重复与对称:验证去重与指针收敛。

原理流程

  1. 编码前列出输入规模下限。
  2. 构造边界与极端用例。
  3. 手算预期结果后跑代码对照。

代码 / 图示

清单:
[] / [x] / [x,x] / 已排序 / 逆序
含 0、负数、Integer.MAX_VALUE
目标不存在 / 目标在首尾

常见误区

  • 误区:只测正常例子;正解:面试官常补边界用例考察严谨性。
  • 误区:溢出靠语言默认行为;正解:相加前判断上溢下溢,必要时用更大类型。

追问

  • Q:两数之和负数怎么测? A:正负相消、同号相加分别构造。
  • Q:链表为空与只有一个节点? A:反转、合并、删除倒数第 N 都要覆盖。

02.1.1.4-018 口述思路与写代码的顺序怎么安排?

一句话结论

先一句话结论 + 复杂度,再讲数据结构与关键步骤,确认方向后写骨架(函数签名、主循环、返回),填细节,最后补边界与用例。

概念解释

  • 先说思路避免写错方向返工。
  • 骨架先行:结构正确后填局部逻辑。
  • 边写边解释不变量。

原理流程

  1. 报方案与复杂度。
  2. 口述指针/状态定义。
  3. 写主流程骨架。
  4. 填分支与边界处理。
  5. 跑用例验证。

代码 / 图示

汇报:"用左右双指针,有序数组,O(n) 时间 O(1) 空间"
骨架:函数 → 指针初始化 → while → 比较移动 → 返回
细节:去重、越界、空输入

常见误区

  • 误区:闷头写完全程不沟通;正解:关键决策点先与面试官对齐。
  • 误区:代码细节卡壳时停住;正解:先说清卡在哪、备选方案是什么。

追问

  • Q:写代码时被打断提问怎么办? A:先回答概念问题,再回到已写部分继续。
  • Q:要不要先命名变量? A:变量名体现语义,先定好状态名再写逻辑。