当前位置:   article > 正文

算法学习-笔试手撕中的Java ACM输入总结以及出错点避雷_大厂面试算法是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包括其末尾的回车
    其用法经常是:
  3. sc.nextInt()sc.nextLong()用于读取下一个intlong类型的数字,但是不能读取末尾的回车

下面几个注意点:

  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
  1. 有时候读取到的数据直接会用,但是需要考虑越界的情况,可以考虑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 ∗ n ∗ ( n + 1 ) k*n*(n+1) kn(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

输出:
请添加图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/AllinToyou/article/detail/419005
推荐阅读
相关标签
  

闽ICP备14008679号