计算机考研杂货铺
数据结构
组成原理
操作系统
计算机网络
学习资源
我的课程
明亮模式
夜间模式
护眼模式
学习资源
独家心法
算法设计题指南
算法设计题指南
从题目约束选择算法，用数组、链表、树和图的典型套路完成思想、代码与复杂度分析
全屏播放
←
/
→
翻页 ·
F
浏览器全屏 ·
S
演讲者备注 ·
?
快捷键
# 算法设计题怎么做 读懂约束 → 选择思路 → 写出实现 → 检查边界 配套讲义：[算法设计题解题框架](/data_structure/basic/alg_design/) --- ## 算法题练什么 - 看到数据结构，能调出 **基本操作** - 看到 **约束**，能联想到常见解法 - 解释为什么是全面的，不会漏解 > 记住模板后，还要知道模板依赖什么条件。 --- ## 题目通常包含的问题 1. **基本思想**：维护什么信息，按什么顺序处理 2. **算法实现**：按题目要求用 C/C++ 描述，关键处加注释 3. **复杂度**：时间、辅助空间及其依据 具体小问和分值以题目为准。 不会最优解时，先留下满足题意的可行方案，再尝试优化。 --- ## 先有可行解，再尝试优化 基本思想从哪里来？先想一个肯定能得到答案的方法。 - 例如选两个数，先枚举所有数对，确认不会漏解 - 再检查时间、空间是否满足要求；不满足就找重复工作 - 考场上暂时想不到最优解，也应把可行方案的思想、代码和复杂度写清楚 得分取决于具体题目与评分要求，不能把暴力解当作固定分数保证。 --- ## 动笔之前，先圈出约束 | 检查项 | 影响什么 | | --- | --- | | 有序吗？值域有限吗？ | 二分、双指针、桶标记能否使用 | | 是否允许额外空间？ | 排序、原地标记、链表逆置是否允许 | | 要求什么复杂度？ | 是否允许排序或辅助数组 | | 输出什么？ | 返回值、原地修改、输出序列 | --- ## 从简单解到最优解 先写可行解，再找重复工作 ```text 枚举所有候选 → 找出反复计算的信息 → 用有序性、辅助记录或状态维护消除重复 ``` - 每次重新查“出现过吗” → 标记表 - 每次重新扫描右侧最值 → 后缀预处理 - 每次从链表头找位置 → 双指针同步移动 优化之后，要重新核对空间和输入修改限制。 --- ## 算法题常见套路 | 输入结构 | 优先考虑 | | --- | --- | | 数组 / 顺序表 | 排序、二分、双指针、多指针、标记、前后缀 | | 链表 | 固定间距、快慢指针、逆置、长度对齐 | | 二叉树 | DFS 递归、中序有序性、层序遍历 | | 图 | 遍历、度统计、拓扑、路径与生成树 | 下面按数组、链表、二叉树、图，归纳核心思路与常用操作。 历年题用于积累模型；不要据此排除某类结构。 --- ## 数组常见问题和套路 | 题目问题 / 条件 | 转化思路 → 套路 | | --- | --- | | 有序数组中查值或边界 | 每次排除一半候选 → 二分 | | 某个值是否出现、哪个值缺失 | 值映射到下标 → 桶标记 | | 对每个位置查询左侧 / 右侧信息 | 汇总重叠范围 → 前后缀预处理 | | 找出现次数严格超过一半的元素 | 不同元素成对抵消 → 投票并验证 | | 找两个数之和；允许重排 | 排序得到单调性 → 首尾双指针 | | 多个有序数组中选数，使极差最小 | 淘汰当前最小值 → 多指针 | 先看目标与条件，再选方法；“无序数组”本身不能决定用哪种套路。 --- ## 排序、二分与双指针 - **排序兜底**：先排序，再查找、去重或选数；通常 O(n log n) - **二分查找**：利用有序性，每次排除一半区间；O(log n) - **首尾双指针**：利用单调性，每次排除一个端点；扫描 O(n) 两数之和：升序排列后，比较 A[l]+A[r] 与目标 S。 ```text 和小于 S → l++ 和大于 S → r-- 和等于 S → 找到答案 ``` 排序前确认：是否允许改变原顺序？ --- ## 桶标记：用下标记录“出现过” **核心**：值映射到下标，避免反复查找。 [2018 年第 41 题](/study_methods/408quiz/2018/#41)：找未出现的最小正整数。 - 长度为 n，答案一定在 **[1,n+1]** - 用 seen[1..n] 记录出现情况，再找第一个未出现的值 - 若 1 到 n 都出现，答案就是 n+1 时间 O(n)，辅助空间 O(n)。若要求 O(1) 辅助空间，考虑原地置换或标记。 --- ## 前后缀：把重复扫描变成一次预处理 **适用**：对每个位置，查询它左边 / 右边的信息。 ```text 前缀最大值：P[i] = max(P[i-1], A[i]) 从左向右 后缀最大值：S[i] = max(A[i], S[i+1]) 从右向左 ``` - 先 O(n) 预处理，再 O(1) 查询；注意是否包含当前位置 - 例如选 i<j 使乘积最大：固定 A[i]，正数配右侧最大值，负数配右侧最小值 - 只求最终答案时，可边扫描边维护最值，省去整张表 **抓住重复信息，再决定存表还是维护变量。** --- ## 投票算法：异值对消，最后验证 [2013 年第 41 题](/study_methods/408quiz/2013/#41)：找出现次数严格超过 n/2 的主元素。 **核心**：删去一对不同元素，不会改变主元素的身份。 ```text 票数为 0 → 当前元素成为候选 与候选相同 → 票数 +1 与候选不同 → 票数 -1 ``` - 第一遍对消，留下候选；第二遍计数，验证是否真的过半 - 票数是对消后的余额，不是真实出现次数 时间 O(n)，辅助空间 O(1)。 --- ## 多指针：每次淘汰当前最小值 [2020 年第 41 题](/study_methods/408quiz/2020/#41)：三个有序数组，各取一数，使距离最小。 ```text D = |a-b| + |b-c| + |c-a| = 2 × (最大值 - 最小值) ``` - 三个指针从各数组首部开始，每轮更新最优答案 - **移动当前最小值对应的指针**：保留最小值、增大其他值，不能缩小极差 - 任一数组耗尽即结束 每个指针只向前走，时间 O(n₁+n₂+n₃)，辅助空间 O(1)。 --- ## 链表常见问题和套路 | 目标 | 核心操作 | | --- | --- | | 倒数第 k 个结点 | 一个指针先走 k 步，再同步前进 | | 中间结点 | 快指针走两步，慢指针走一步 | | 逆序处理 | 原地逆置，改变链接方向 | | 首尾交替重排 | 找中点 + 逆置后半段 + 交替合并 | | 公共尾部起点 | 长度对齐，或双指针换头 | **链表不能随机访问：用指针间距、访问顺序代替反复定位。** --- ## 链表：双指针与逆置 - **固定间距**：p 先走 k 步，再与 q 同速；p 到 NULL 时，q 为倒数第 k 个 - **快慢指针**：fast 每轮两步、slow 一步；fast 到末尾时，slow 在中部 - **原地逆置**：维护已逆置部分 prev 和未处理部分 cur ```c while (cur != NULL) { NODE *next = cur->next; // 先保存后继 cur->next = prev; prev = cur; cur = next; } ``` 均为 O(n) 时间、O(1) 辅助空间；具体指针初值按是否带头结点确定。 --- ## 链表：组合基本操作 [2019 年第 41 题](/study_methods/408quiz/2019/#41)：首尾交替重排。 ```text 原表：1 → 2 → 3 → 4 → 5 拆分：1 → 2 → 3 4 → 5 逆置：1 → 2 → 3 5 → 4 合并：1 → 5 → 2 → 4 → 3 ``` **快慢指针找中点 → 断开 → 逆置后半段 → 交替合并** - 单独的基本操作要熟练，组合时明确每一步的输入与输出 - 修改链接前保存后继，拆分后再合并，避免断链或成环 时间 O(n)，辅助空间 O(1)。 --- ## 链表：公共结点先对齐 **关键性质**：无环单链表一旦相交，后面就是共享尾部。 - 先求长度：长表先走长度差，再同步前进 - 或双指针换头：各自走完本表，再从另一表开始 ```c while (p != q) { p = p ? p->next : firstB; q = q ? q->next : firstA; } ``` 换头让两者走过相同的总路程，抵消长度差。 比较结点地址；时间 O(m+n)，辅助空间 O(1)。 --- ## 二叉树常见问题和套路 | 目标 | 核心思路 | | --- | --- | | 高度、子树结点数 | 后序：先求左右子树，再合并 | | 深度、路径、WPL | DFS：从根向下携带状态 | | BST 第 k 小、检查有序性 | 中序：利用有序序列 | | 按层输出、每层统计 | BFS：队列按层处理 | **遍历顺序取决于：需要的信息什么时候能得到？** --- ## 二叉树：递归与遍历 写递归先明确：**函数语义 → 空树返回值 → 子树结果如何合并**。 ```c int height(BTNode *root) { if (root == NULL) return 0; return 1 + max(height(root->left), height(root->right)); } ``` - **中序**：BST 得到有序序列，可边访问边计数找第 k 小 - **层序**：队列保存待处理结点；按层统计时，先固定本层大小 遍历时间 O(n)；递归栈 O(h)，层序队列 O(w)。 --- ## 二叉树：中序与层序模板 **中序**：BST 按键值顺序访问，在 visit 中计数、比较或更新答案。 ```c void inorder(BTNode *p) { if (p == NULL) return; inorder(p->left); visit(p); inorder(p->right); } ``` **层序**：非空根先入队，出队时把孩子加入队尾。 ```cpp if (root) q.push(root); // q 为结点指针队列 while (!q.empty()) { BTNode *p = q.front(); q.pop(); visit(p); if (p->left) q.push(p->left); if (p->right) q.push(p->right); } ``` --- ## 图常见问题和套路 | 目标 | 算法与条件 | | --- | --- | | 可达性、连通分量 | DFS / BFS | | 最少边数 | 无权 / 等权图 → BFS | | 最小路径权值和 | 非负边权 → Dijkstra | | 连接全部顶点，总成本最小 | 无向连通带权图 → Prim / Kruskal | | 依赖顺序、有向环判断 | 拓扑排序 | | 工期、关键活动 | AOE 网 → 关键路径 | | 每条边恰好走一次 | 欧拉路径 → 连通性 + 度条件 | 先分清目标：最短路径、最小生成树、关键路径解决不同问题。 --- ## 图：遍历是基础 - **DFS**：递归 / 栈，沿一条路径深入 - **BFS**：队列，逐层扩展；可求无权图最少边数 - visited 防止重复访问；BFS 在入队时标记 - 遍历整个图时，从未访问顶点继续启动 --- ## 图：DFS / BFS 模板 邻接表 adj[u] 保存 u 的邻接点；visited 初始全为 false。 ```cpp void dfs(int u) { visited[u] = true; visit(u); for (int v : adj[u]) if (!visited[v]) dfs(v); } ``` ```cpp visited[s] = true; q.push(s); // q 为顶点编号队列 while (!q.empty()) { int u = q.front(); q.pop(); visit(u); for (int v : adj[u]) { if (visited[v]) continue; visited[v] = true; // 入队时标记 q.push(v); } } ``` --- ## 图：拓扑排序与关键路径 **拓扑排序：解决先后依赖** 已统计 indegree；q 初始为空，adj 保存出边邻接点。 ```cpp for (int u = 0; u < V; ++u) if (indegree[u] == 0) q.push(u); int count = 0; while (!q.empty()) { int u = q.front(); q.pop(); visit(u); ++count; for (int v : adj[u]) if (--indegree[v] == 0) q.push(v); } // count < V：存在有向环 ``` **AOE 关键路径：在依赖顺序上加入工期** - 按拓扑序求事件最早时间 ve，逆拓扑序求最迟时间 vl - 活动 u→v、工期 w：若 `ve[u] == vl[v]-w`，就是关键活动 --- ## 图：欧拉路径看连通性与度 无向图，每条边恰好走一次： - 所有度大于 0 的顶点必须连通 - 奇度顶点 **0 个**：存在欧拉回路 - 奇度顶点 **2 个**：存在非闭合欧拉路径，两个奇度顶点为端点 **核心理由**：途经顶点时，进入与离开配对；只有起终点可以各剩一条边。 有向图需改看入度、出度条件。 --- ## 最后检查什么 - **条件**：有序性、能否修改输入、时间与空间限制 - **边界**：空输入、单元素、重复值、全负数、指针越界 - **实现**：先保存再改链接，先查询再更新状态，递归计入栈空间 平时：独立写 → 对照思路 → 合上答案重写 → 换条件再做。 完整推导与模板：[算法设计题解题框架](/data_structure/basic/alg_design/) 书写配套：[408 大题书写规范](/study_methods/talk/answer_writing/)
自动选项验证
回到顶部
固定导航栏
刷新选项
批量检查已选
答题板
反馈
题目收藏
我的课程