1.Java快读模板

我们以往使用的Scanner sc = new Scanner(System.in);和String s = sc.nextLine();在输入数据非常大的时候会变得很慢，增加程序运行时间，因此用字符缓冲流来代替，提高运行速度!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 缓冲输入流
private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
// 输出流
private static final PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

private static String Line() {
    String p = "";
    try {
        p = bf.readLine();
    } catch (IOException e) {
        e.printStackTrace();
    }
    return p;
}

public static void main(String[] args) {
    String inStr = Line();
    pw.println(inStr);	// 输出(支持任意类型)
    pw.flush();	// 要有flush才能输出
}

2.二叉树处理模板

二叉树是最常见的数据结构之一，在处理输入的通常是一个数组要转化为二叉树，而输出的时候往往要将二叉树转化为数组。

下面是二叉树节点类+根据int类型数组生成二叉树+给定root打印二叉树值的代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package leetcode.Binary_Trees;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author Fomalhaut
 * @date 2022/4/26
 * @desc 二叉树工具类:序列化与反序列化(不带多余null)
 */
public class TreeUtils {
    /**
     * 序列化二叉树
     * @param root 根节点引用
     * @return String 序列化后以字符串形式表示的二叉树序列
     */
    public static String serialize(TreeNode root) {
        if(root == null) {
            return "[]";
        }
        List<String> list = new ArrayList<>();
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while(!que.isEmpty()) {
            TreeNode node = que.poll();
            if(node != null) {
                // 1.node不为空的情况
                // node的值加入sb(自动转型)
                list.add(node.val + "");
                // 左右子节点无论是否为空照样入队
                que.add(node.left);
                que.add(node.right);
            }else {
                // 2.node为空的情况
                // "null"这个字符串加入sb即可
                list.add("null");
                // 空节点没有左右子节点了
            }
        }
        int flag = list.size() - 1;
        for (int i = list.size() - 1; i >= 0; i--) {
            if(!"null".equals(list.get(i))) {
                flag = i;
                break;
            }
        }
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i <= flag; i++) {
            sb.append(list.get(i)).append(",");
        }
        return sb.deleteCharAt(sb.length() - 1).append("]").toString();
    }

    /**
     * 反序列化二叉树
     * @param data 二叉树字符串序列
     * @return TreeNode 反序列化后二叉树根节点引用
     */
    public static TreeNode deserialize(String data) {
        if("[]".equals(data)) {
            return null;
        }
        // 首先将字符串转化为每个值的字符串数组(去头尾+","分割)
        String[] strs = data.substring(1, data.length() - 1).split(",");
        int strsLen = strs.length;
        // 遍历序列化数据的索引(初始化为1指向root左子节点)
        int i = 1;
        // 辅助队列
        Queue<TreeNode> que = new LinkedList<>();
        // 创建根节点
        TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
        // 根节点入队
        que.add(root);
        // 开启遍历
        while(!que.isEmpty()) {
            // 队头节点出队
            TreeNode node = que.poll();
            // 只要strs[i](出队节点的某个子节点)不是null就可以参与树的构建
            if(i < strsLen && !"null".equals(strs[i])) {
                // 构建新的左子节点并完成指向
                TreeNode left = new TreeNode(Integer.parseInt(strs[i]));
                node.left = left;
                // 左子节点入队
                que.add(left);
            }
            // 索引向右移动
            i++;
            if(i < strsLen && !"null".equals(strs[i])) {
                // 构建新的右子节点并完成指向
                TreeNode right = new TreeNode(Integer.parseInt(strs[i]));
                node.right = right;
                // 右子节点入队
                que.add(right);
            }
            // 索引继续向右移动
            i++;
        }
        // 返回根节点
        return root;
    }
}

3.链表处理模板

链表是最简单的数据结构之一，下面给出链表节点类+根据int数组生成链表+给定head打印节点值代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * @author Fomalhaut
 * @date 2022/4/25
 * @desc 链表工具类:构建+打印
 */
public class LinkListUtil {
    // 由数组生成链表
    public static ListNode generateLinkList(int[] arr) {
        ListNode nex = null;
        for (int i = arr.length - 1; i >= 0; i--) {
            ListNode cur = new ListNode(arr[i]);
            cur.next = nex;
            nex = cur;
        }
        return nex;
    }

    // 打印链表
    public static void printLinkList(ListNode head) {
        ListNode cur = head;
        List<Integer> list = new ArrayList<>();
        while (cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        System.out.println(list);
    }
}

/**
 * @author Fomalhaut
 * @date 2022/4/25
 * @desc 节点类
 */
public class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}