数据结构与算法 / 系统课时
准备一套可复用的代码模板
准备一套可复用的代码模板
刷题模板的价值不是少敲几行代码,而是把稳定、低认知负担的样板部分固定下来,让注意力集中在状态定义和算法选择上。本节以 Java 17 为例,整理读写、遍历、递归、BFS、堆与常用容器的最小模板,并说明哪些部分必须按题修改。
学习目标
- 建立一份可以直接复制到本地练习环境的 Java 基础模板
- 熟练使用数组遍历、DFS、BFS、优先队列、映射和集合
- 分清“可固定的样板代码”与“必须根据题意重写的算法逻辑”
模板只固定机械部分
真正值得复用的是那些长期不变、写错却很浪费时间的部分,例如输入读取、队列初始化、优先队列比较器、图的邻接表容器,以及 DFS/BFS 的基本框架。
不要把具体题目的状态转移也做成“万能模板”。一旦模板替你决定了状态含义、访问时机或剪枝条件,你很容易在题型相似但约束不同的情况下照抄出错。
可以把自己的模板拆成两层:底层是语言和容器样板,长期稳定;上层只有函数骨架,每道题都重新填写状态、边界与转移。
一份最小可运行模板
下面的程序把常见组件放在同一个文件中。示例输入第一行是数组长度 n 与 k,第二行是数组;程序演示数组遍历、频次统计、递归 DFS、BFS 和用最大堆维护最小的 k 个数。
示例输入:
5 3
5 1 4 2 3import java.io.*;
import java.util.*;
public class Main {
static class FastScanner {
private final BufferedReader br;
private StringTokenizer st;
FastScanner(InputStream in) {
br = new BufferedReader(new InputStreamReader(in));
}
String next() throws IOException {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(br.readLine());
}
return st.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
static void dfs(int u, boolean[] visited, List<List<Integer>> graph, List<Integer> order) {
visited[u] = true;
order.add(u);
for (int v : graph.get(u)) {
// 图上递归先判断访问标记,避免在环中重复进入节点。
if (!visited[v]) {
dfs(v, visited, graph, order);
}
}
}
static List<Integer> bfs(int start, List<List<Integer>> graph) {
boolean[] visited = new boolean[graph.size()];
ArrayDeque<Integer> queue = new ArrayDeque<>();
List<Integer> order = new ArrayList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int u = queue.poll();
order.add(u);
for (int v : graph.get(u)) {
// 入队时标记,避免同一节点被重复加入队列。
if (!visited[v]) {
visited[v] = true;
queue.offer(v);
}
}
}
return order;
}
static List<Integer> smallestK(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder());
for (int x : nums) {
heap.offer(x);
if (heap.size() > k) {
heap.poll();
}
}
List<Integer> result = new ArrayList<>(heap);
Collections.sort(result);
return result;
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
int k = fs.nextInt();
int[] nums = new int[n];
Map<Integer, Integer> freq = new HashMap<>();
Set<Integer> distinct = new HashSet<>();
int sum = 0;
for (int i = 0; i < n; i++) {
nums[i] = fs.nextInt();
sum += nums[i];
freq.merge(nums[i], 1, Integer::sum);
distinct.add(nums[i]);
}
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < 4; i++) {
graph.add(new ArrayList<>());
}
int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}};
for (int[] e : edges) {
graph.get(e[0]).add(e[1]);
graph.get(e[1]).add(e[0]);
}
List<Integer> dfsOrder = new ArrayList<>();
boolean[] dfsVisited = new boolean[graph.size()];
dfs(0, dfsVisited, graph, dfsOrder);
System.out.println("sum=" + sum);
System.out.println("distinct=" + distinct.size());
System.out.println("freq(3)=" + freq.getOrDefault(3, 0));
System.out.println("dfs=" + dfsOrder);
System.out.println("bfs=" + bfs(0, graph));
System.out.println("smallestK=" + smallestK(nums, k));
}
}预期输出:
sum=15
distinct=5
freq(3)=1
dfs=[0, 1, 3, 2]
bfs=[0, 1, 2, 3]
smallestK=[1, 2, 3]邻接表中的边插入顺序会影响 DFS 或 BFS 的访问顺序;这里的输出只对应示例代码中的固定建图顺序。真实题目若只要求可达性或最短距离,不要把某一种访问顺序误当成题目保证。
记住容器职责而不是死记代码
ArrayDeque 适合做 BFS 队列,也常用于栈;PriorityQueue 负责持续取得当前最小值或最大值;HashMap 适合记录计数、映射与“是否见过”;HashSet 只保留成员关系;ArrayList 适合顺序存储和邻接表。
堆最容易写反。Java 的 PriorityQueue 默认是小根堆;如果目标是“保留最小的 k 个元素”,常用容量为 k 的大根堆,这样新元素加入后可以优先淘汰当前最大的那个。模板可以记住比较器写法,但“该用大根还是小根”必须从题意重新判断。
每次复制后只做三类修改
第一类是数据模型:数组、字符串、树节点还是图;第二类是状态与边界:访问标记何时设置、递归终止条件是什么;第三类是返回值:布尔值、距离、计数还是完整方案。
模板应该让你更快进入真正的问题,而不是让你停止思考。长期训练时,最好把模板控制在自己能够不看注释就解释每一行的规模;任何无法解释的“神奇代码”,都不应该进入常用模板。