算法学习-笔试手撕中的Java ACM输入总结以及出错点避雷_大厂面试算法是acm模式吗

在面试的过程中，许多大厂的算法编程题都是要求ACM输入输出模式的，对于在力扣上刷习惯核心模式的我们会略显生疏，因此本文对相关的输入输出进行简单汇总，方便查阅。

本文参考牛客网OJ在线编程输入输出专场。

和控制台交互的输入输出

整体的程序框架需要自己导入常用的包，并且类名public Class Main和主方法名public static void main(String[] args)需要留意。

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc= new Scanner(System.in);
     
        }
    }
}
1
2
3
4
5
6
7
8
9

ACM输出很简单：

System.out.print();
System.out.println();
1
2

ACM输入分为几种情况：
首先需要了解：

1. sc.hasNext()可以用于判断接下来是否还有输入，常用于程序没有指定输入行数的情况，需要while(sc.hasNext())外层循环不断读取。
2. sc.nextLine()可以读取本行的String，包括其末尾的回车。
   其用法经常是：
   • int n=Integer.valueOf(sc.nextLine())，将本行读取到的String转换为数字。
   • String[]ss=sc.nextLine().split(" ")，将本行读取到的String根据空格分割为String数组。关于split还有一些注意项可以参考我的另一篇文章算法学习-字符串处理及其常用API，把这种题目刷熟练的男人真的很帅。
3. sc.nextInt()、sc.nextLong()用于读取下一个int或long类型的数字，但是不能读取末尾的回车。

下面几个注意点：

1. 当碰到先读取数字，然后又读取一行字符串的情况：

5
c d a bb e
1
2

我们想要读取这两行的数据，当采用下面的读法，String s读出来的是空字符，因为nextInt()仅仅读取到了5，但是没有把后面的回车换行符读进去，留在了缓存区里面。然后sc.nextLine()读取到了回车符，出现错误。

int n=sc.nextInt();
String s=sc.nextLine();
1
2

我们可以用多加一行sc.nextLine();读取掉换行符。

int n=sc.nextInt();
sc.nextLine();
String s=sc.nextLine();
1
2
3

或者更推荐的做法是，直接用int n=Integer.parseInt(sc.nextLine());或者int n=Integer.valueOf(sc.nextLine());连带回车符一起读取。

int n=Integer.valueOf(sc.nextLine());
String s=sc.nextLine();
1
2

2. 有时候读取到的数据直接会用，但是需要考虑越界的情况，可以考虑sc.nextLong()
   比方说：

Scanner sc = new Scanner(System.in);
long n  = sc.nextLong();
long k  = sc.nextLong();
long result  = (long) (k* n*(n+1)/2);
1
2
3
4

当时在写程序的时候就是直接用了sc.nextInt()导致卡$k\ast n\ast (n+1)$整体越界了，因为这里是先做int运算，然后再转换为long类型，需要提前就将运算数据转为long.

构建数据结构

在上面可以读取控制台输入输出了以后，就需要将相关的字符串转换为好处理的数据结构。

数组

字符串转换为数组
输入：

[2,7,11,15]
1

实现代码：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String input=sc.nextLine();
        int[] ans=StringToIntArray(input);
        // 验证结果
        System.out.println(Arrays.toString(ans));
    }
	
	// 字符串转换为数组
    public static int[] StringToIntArray(String s){
        String[] parts=s.substring(1,s.length()-1).split(",");
        int[]ans=new int[parts.length];
        for(int i=0;i<parts.length;i++){
            ans[i]=Integer.parseInt(parts[i]);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

链表

字符串转换为链表
输入：

[4,1,8,4,5]
1

实现代码：

import java.util.Scanner;

public class Main {
    static class ListNode{
        int val;
        ListNode next;
        ListNode(int val){
            this.val=val;
            this.next=null;
        }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String input=sc.nextLine();
        ListNode head=StringToListNode(input);
        // 验证结果
        printListNode(head);
    }

    public static ListNode StringToListNode(String s){
        String[] parts=s.substring(1,s.length()-1).split(",");
        // 尾插法创建链表
        ListNode dummyHead=new ListNode(-1);
        ListNode cur=dummyHead;
        for(int i=0;i<parts.length;i++){
           cur.next=new ListNode(Integer.parseInt(parts[i]));
           cur=cur.next;
        }
        return dummyHead.next;
    }

    public static void printListNode(ListNode head){
        ListNode cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
    }
}
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

二叉树

字符串转换为二叉树
输入：通常是层序输入的序列

[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
1

这里提供两种实现方式，一种是直接用队列层序建树，还有一种是借助数组预处理，更推荐简单的数组预处理方式。
实现代码：

import java.util.*;

public class Main{
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val=val;
        }
    }
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        String input=sc.nextLine();
        TreeNode root=stringToTreeNode(input);
        printTree(root);
    }

    public static TreeNode stringToTreeNode(String s){ // 通过队列进行构造
        String[] parts=s.substring(1,s.length()-1).split(",");
        TreeNode root=null;
        if(parts==null||parts.length==0) return root;

        root=new TreeNode(Integer.parseInt(parts[0]));
        ArrayDeque<TreeNode> que=new ArrayDeque<>();
        que.offer(root);

        // 层序遍历建立树
        int index=1; // 表示已经建立好连接关系的节点数
        if(index==parts.length) return root;
        while(!que.isEmpty()){
            TreeNode top=que.poll();
            String iterm=parts[index++];
            if(!Objects.equals(iterm,"null")){ // 不为null才需要创建节点，否则默认左子树默认为null并继续下一个
                TreeNode cur=new TreeNode(Integer.parseInt(iterm));
                top.left=cur;
                que.offer(cur); // 本层top的连接关系已经确定，节点cur入队用于cur下面的关系连接
            }
            if(index==parts.length) break;
            iterm=parts[index++];
            if(!Objects.equals(iterm,"null")){
                TreeNode cur=new TreeNode(Integer.parseInt(iterm));
                top.right=cur;
                que.offer(cur);
            }
            if(index==parts.length) break;
        }
        return root;
    }

	// 验证
    public static void printTree(TreeNode root){
        if(root==null) return;
        ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
        LinkedList<TreeNode> que=new LinkedList<>(); // LinkedList才能offer null值
        que.offer(root);
        while(!que.isEmpty()){
            ArrayList<Integer> l=new ArrayList<>();
            int size=que.size();
            for(int i=0;i<size;i++){
                TreeNode top=que.poll();
                if(top!=null){
                    que.offer(top.left);
                    que.offer(top.right);
                    l.add(top.val);
                }else{
                    l.add(-1);
                }
            }
            ans.add(l);
        }
        for(int i=0;i<ans.size();i++){
            for(int j=0;j<ans.get(i).size();j++){
                System.out.print(ans.get(i).get(j)+" ");
            }
            System.out.println();
        }
    }
}
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

另一种方法是通过数组预处理进行构造，如果父节点的数组下标是i，那么它的左孩子下标就是i * 2 + 1，右孩子下标就是 i * 2 + 2。

实验代码如下：

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

public class Main{
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val=val;
        }
    }
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        String input=sc.nextLine();
        TreeNode root=stringToTreeNode(input);
        printTree(root);
    }

    static TreeNode stringToTreeNode(String input){
        String[]parts=input.substring(1,input.length()-1).split(",");
        TreeNode root=null;

        // 先将输入的数组转换为二叉树数组，如果原先输入为null，就在数组中存null，建立的树中也是null
        List<TreeNode> treeNodeList=new ArrayList<>();
        for(int i=0;i<parts.length;i++){
            TreeNode node=null;
            if("null".equals(parts[i])){
                treeNodeList.add(node);
            }else{
                node=new TreeNode(Integer.valueOf(parts[i]));
                treeNodeList.add(node);
            }
            if(i==0) root=node; // 赋予根结点
        }

        // 遍历二叉树数组完成树的建立,i*2+1<parts.length是为了保证非满二叉树的时候，不遗漏节点
        for(int i=0;i*2+1<parts.length;i++){
            TreeNode node=treeNodeList.get(i);
            if(node!=null){
                node.left=treeNodeList.get(2*i+1);
                if(i*2+2<parts.length) node.right=treeNodeList.get(2*i+2);
            }
        }

        return root;
    }

    public static void printTree(TreeNode root){
        if(root==null) return;
        ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
        LinkedList<TreeNode> que=new LinkedList<>(); // LinkedList才能offer null值
        que.offer(root);
        while(!que.isEmpty()){
            ArrayList<Integer> l=new ArrayList<>();
            int size=que.size();
            for(int i=0;i<size;i++){
                TreeNode top=que.poll();
                if(top!=null){
                    que.offer(top.left);
                    que.offer(top.right);
                    l.add(top.val);
                }else{
                    l.add(-1);
                }
            }
            ans.add(l);
        }
        for(int i=0;i<ans.size();i++){
            for(int j=0;j<ans.get(i).size();j++){
                System.out.print(ans.get(i).get(j)+" ");
            }
            System.out.println();
        }
    }
}
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

输出：