[Java] ACM 模式刷题模板——面试时手动构建链表、二叉树

最近许多小伙伴都开始秋招了，有的同学习惯了力扣的核心代码模式，在笔试、面试的时候适应不了需要手动处理输入输出的 ACM 模式。从核心代码模式转到 ACM 模式并不难，看完这篇文章你就可以胜任绝大部分场景。

从控制台读取输入

以两数之和为例，它的输入是这样的：

[2,7,11,15]
9

我们需要读入第一行的字符串和第二行的整数，然后将字符串转换成数组。首先，使用 Scanner 进行逐行读取。

import java.util.Scanner;
   
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = s.nextLine();         //读取字符串
        System.out.println("字符串："line);
        int a = s.nextInt();                //读取整数
        System.out.println("整数："+a);
    }
}

手动构建数据结构

从控制台读取字符串之后，需要手动将这些字符串转换成数组、链表和二叉树，转化的代码都是很固定的，可以作为模板使用。

数组

数组的构建非常简单，将字符串根据分隔符分割，然后转换成整型即可。代码如下：

    private static int[] StringToIntArray(String str) {
        String[] parts = str                //根据“,”分割成字符串数组
            .substring(1, str.length() - 2)
            .split(",");
        int[] nums = new int[parts.length];
        for (int i = 0; i < parts.length; i ++) 
            nums[i] = Integer.parseInt(parts[i]);    //转为整型数组
        
        return nums;
    }

链表

链表的构建也不难。

    private static ListNode StringToListNode(String str) {
        String[] parts = str    //分割字符串
            .substring(1, str.length() - 2)
            .split(",");

        ListNode dummy = new ListNode(-1), cur = dummy;        //虚拟头结点

        for (int s: parts) {
            cur.next = new ListNode(Integer.parseInt(s));      //逐个添加链表的结点
            cur = cur.next;
        }

        return dummy.next;    //返回真正的头结点
    }

二叉树

构建二叉树的代码就很长了，个人感觉手动构建二叉树相当于一道中等题了。

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    private static class TreeNode {    //二叉树类
        int val;
        TreeNode left, right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();

        TreeNode root = StringToTreeNode(str);
    }

    private static TreeNode StringToTreeNode(String str) {
        String[] parts = str
            .substring(1, str.length() - 1)
            .split(",");

        String item = parts[0];
        TreeNode root = new TreeNode(Integer.parseInt(item));    //二叉树的根节点

        Queue<TreeNode> q = new LinkedList<>();    //使用队列添加结点
        q.offer(root);

        int index = 1;
        while (!q.isEmpty()) {
            TreeNode node = q.poll();

            if (index == parts.length) break;

            item = parts[index ++];
            if (!item.equals("null")) {
                node.left = new TreeNode(Integer.parseInt(item));
                q.offer(node.left);
            }

            if (index == parts.length) break;

            item = parts[index ++];
            if (!item.equals("null")) {
                node.right = new TreeNode(Integer.parseInt(item));
                q.offer(node.right);
            }
        }

        return root;
    }
}