数据结构与算法 / 系统课时

准备一套可复用的代码模板

准备一套可复用的代码模板

刷题模板的价值不是少敲几行代码,而是把稳定、低认知负担的样板部分固定下来,让注意力集中在状态定义和算法选择上。本节以 Java 17 为例,整理读写、遍历、递归、BFS、堆与常用容器的最小模板,并说明哪些部分必须按题修改。

学习目标

  • 建立一份可以直接复制到本地练习环境的 Java 基础模板
  • 熟练使用数组遍历、DFS、BFS、优先队列、映射和集合
  • 分清“可固定的样板代码”与“必须根据题意重写的算法逻辑”

模板只固定机械部分

真正值得复用的是那些长期不变、写错却很浪费时间的部分,例如输入读取、队列初始化、优先队列比较器、图的邻接表容器,以及 DFS/BFS 的基本框架。

不要把具体题目的状态转移也做成“万能模板”。一旦模板替你决定了状态含义、访问时机或剪枝条件,你很容易在题型相似但约束不同的情况下照抄出错。

可以把自己的模板拆成两层:底层是语言和容器样板,长期稳定;上层只有函数骨架,每道题都重新填写状态、边界与转移。

一份最小可运行模板

下面的程序把常见组件放在同一个文件中。示例输入第一行是数组长度 n 与 k,第二行是数组;程序演示数组遍历、频次统计、递归 DFS、BFS 和用最大堆维护最小的 k 个数。

示例输入:

text
5 3
5 1 4 2 3
java
import 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));
    }
}

预期输出:

text
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 的大根堆,这样新元素加入后可以优先淘汰当前最大的那个。模板可以记住比较器写法,但“该用大根还是小根”必须从题意重新判断。

每次复制后只做三类修改

第一类是数据模型:数组、字符串、树节点还是图;第二类是状态与边界:访问标记何时设置、递归终止条件是什么;第三类是返回值:布尔值、距离、计数还是完整方案。

模板应该让你更快进入真正的问题,而不是让你停止思考。长期训练时,最好把模板控制在自己能够不看注释就解释每一行的规模;任何无法解释的“神奇代码”,都不应该进入常用模板。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

准备一套可复用的代码模板

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通