大题答题模板

模板 1：算法设计题标准结构

1. 设计思想
   说明核心数据结构和关键思路。

2. 算法步骤
   用自然语言或伪代码分步描述。

3. 关键代码 / 伪代码
   变量命名清晰，边界写全。

4. 正确性说明
   说明循环不变式或关键结论。

5. 复杂度分析
   时间复杂度：
   空间复杂度：

模板 2：链表题

设计思想：
设置若干指针，利用单链表局部修改指针域完成操作。

算法步骤：
1. 判空。
2. 初始化前驱/当前/快慢指针。
3. 扫描或定位目标结点。
4. 修改 next 域完成插入、删除、反转或合并。
5. 返回结果。

模板 3：树题

设计思想：
树问题通常采用递归或队列层序遍历。递归函数返回值必须先定义清楚。

算法步骤：
1. 若根结点为空，直接返回。
2. 按先序/中序/后序/层序遍历访问结点。
3. 在访问过程中累计答案或构造结果。
4. 返回最终结果。

模板 4：图题

设计思想：
根据题意选择邻接矩阵或邻接表，并在此基础上进行 BFS / DFS / 入度统计 / 最短路。

算法步骤：
1. 根据输入建立图。
2. 初始化 visited / indegree / dist 等辅助数组。
3. 按 BFS、DFS 或拓扑排序规则推进。
4. 在遍历过程中统计或更新答案。

模板 5：排序/查找题

设计思想：
利用序列有序性，选择折半查找、partition、快排或归并思想降低复杂度。

算法步骤：
1. 明确区间和边界。
2. 比较中点或基准。
3. 舍弃不可能区间或进行划分。
4. 直到找到目标或区间为空。

考场表达建议

• 不要直接写一坨代码，先写“设计思想”。
• 复杂度一定单独起一行。
• 若题目要求“尽可能高效”，要主动点出为什么你的做法优于朴素做法。
• 如果没时间写完整正确性证明，至少说明“为什么不会漏”和“为什么不会错”。

拿分点清单

• 题意转化是否正确。
• 数据结构是否合理。
• 关键步骤是否完整。
• 复杂度是否准确。
• 边界条件是否说明。