牛客网北邮考研机试题解

二进制数

题目链接

https://www.nowcoder.com/practice/103dd589fed14457a673c613d8de3841?tpId=67&tqId=29634&tPage=1&ru=%2Fkaoyan%2Fretest%2F1005&qru=%2Fta%2Fbupt-kaoyan%2Fquestion-ranking

思路解析

直接用javaInteger内置的toBinaryString函数就可以

AC代码

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Integer string = scanner.nextInt();
        System.out.println(Integer.toBinaryString(string));
    }
}

哈夫曼树

题目链接

https://www.nowcoder.com/practice/162753046d5f47c7aac01a5b2fcda155?tpId=67&tqId=29635&tPage=1&ru=%2Fkaoyan%2Fretest%2F1005&qru=%2Fta%2Fbupt-kaoyan%2Fquestion-ranking

思路解析

求哈夫曼树的带权路径长度 = 所有叶子节点的带权路径长度之和。

每个节点的带权路径长度 = 节点的权值 * 路径长度(从根到该节点的分支数)

如果我们按照上面思路,就必须要构建完整的哈尔曼树了,还要计算每个节点的层数用层次遍历,很麻烦。

树的带权路径长度 = 所有非叶子节点的权值之和。

所以问题关键变成了:怎么计算所有非叶子节点的权值。

构建哈尔曼树,每次都是拿两个权值最小节点合并成一个非叶子节点(非叶子节点的权值是前面两个节点权值之和)。所以可以使用java的PriorityQueue优先队列。加入到优先队列,虽然队列内部顺序不清楚,但是每次出队(队首)的元素都是最小的。

AC代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        PriorityQueue<Integer> list = new PriorityQueue<Integer>();
        for (int i = 0; i < n; i++) {
            list.add(scanner.nextInt());
        }
        
        int result = 0;
        while(list.size() > 1){
            int a = list.poll();
            int b = list.poll();
            int temp = a+b;
            list.add(temp);
            result += temp;
        }
        
        System.out.println(result);
        
    }
}

比较奇偶数个数

题目链接

https://www.nowcoder.com/practice/188472f474d5421cb8218b8ad561023b?tpId=67&tqId=29636&tPage=1&ru=%2Fkaoyan%2Fretest%2F1005&qru=%2Fta%2Fbupt-kaoyan%2Fquestion-ranking

思路解析

这个太简单了,边输入,边统计就可以了

AC代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int odd = 0;
        int even = 0;
        for (int i = 0; i < n; i++) {
            if (scanner.nextInt() % 2 == 0) {
                even ++;
            }else{
                odd ++;
            }
        }
        if (even > odd) {
            System.out.println("NO");
        }else {
            System.out.println("YES");
        }
    }
}

查找第K小数

题目链接

https://www.nowcoder.com/practice/204dfa6fcbc8478f993d23f693189ffd?tpId=67&tqId=29637&tPage=1&ru=%2Fkaoyan%2Fretest%2F1005&qru=%2Fta%2Fbupt-kaoyan%2Fquestion-ranking

思路解析

我太喜欢java里面的list的sort方法,太方便了。

所以,我先对list进行去重,再排序,就可以直接输出第k-1个数就可以了

AC代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer>list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(scanner.nextInt());
        }
        int k = scanner.nextInt();
        list = new ArrayList<>(new LinkedHashSet<>(list));
        Collections.sort(list);
        
        System.out.println(list.get(k-1));
    }
}

矩阵幂

题目链接

https://www.nowcoder.com/practice/31e539ab08f949a8bece2a7503e9319a?tpId=67&tqId=29638&tPage=1&ru=%2Fkaoyan%2Fretest%2F1005&qru=%2Fta%2Fbupt-kaoyan%2Fquestion-ranking

思路解析

本题最重要的是实现,两个矩阵相乘。

相乘后的矩阵的某个元素result[i][j] 为A矩阵i行a[i][?] 与B矩阵j列b[?][j]对应相乘的结果。

AC代码

import java.util.Scanner;

public class Main {
    
    public static int size = 0;
    public static void main(String[] args) {
        
        Main mutiple = new Main();
        mutiple.handle();
    }    
    
    public void handle(){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        size = n;
        int k = scanner.nextInt();
        int [][] array = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                array[i][j] = scanner.nextInt();
            }
        }
        
        int [][] origin = array;
        for (int i = 1; i < k; i++) {
            array = cheng(array, origin);
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(array[i][j]);
                if (j!=n-1) {
                    System.out.print(" ");
                }
            }
            System.out.println();
        }
        
        
    }
    
    
    public int[][] cheng(int [][] arrayA,int [][]arrayB){
        int[][] result = new int[size][size];
        
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                int temp = 0;
                for (int l = 0; l < size; l++) {
                    temp += arrayA[i][l] * arrayB[l][j];    
                }
                result[i][j] = temp;
            }
        }
        
        return result;
        
    }
}

C翻转

题目链接

https://www.nowcoder.com/practice/74bdb725421c4f80b4aca7266818baf0?tpId=67&tqId=29639&tPage=1&ru=%2Fkaoyan%2Fretest%2F1005&qru=%2Fta%2Fbupt-kaoyan%2Fquestion-ranking

思路解析

北邮2014年计院机试(上午) 的问题B:旋转图像 和这个其实是类似的:

都是寻找旋转90°后的矩阵和原矩阵的对应关系。

比如顺时针旋转90°,旋转后的矩阵就是以前矩阵按列输出,并且是按照最后一个数字输出。

比如下面的矩阵:

顺时针旋转90°,就是从第一列最后一个数字开始输出,7,4,1/ 8,5,2/9,6,3依次输出即可。

数字1是序号是(x-1,y-1) 则数字7的位置为(x-1+b-1,y-1),(其中b=3)旋转后的矩阵的

第一行是(x-1+b-1-?, y-1+0)

第二行是(x-1+b-1-?, y-1+1)

第三行是(x-1+b-1-?, y-1+2)

?是表示这个元素在该行的位置,是该行的第?+1元素。代码中? = j - y + 1

旋转后的矩阵,每一行的第二个坐标规律为y-1+(i-x+1)

AC代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        
        
        int[][] array = new int[5][5]; 
        
        for(int i = 0; i <5;i++){
            for (int j = 0; j < 5; j++) {
                array[i][j] = scanner.nextInt();
            }
        }
        
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        
        String oper = a+""+b;
        
        int x = scanner.nextInt();
        int y = scanner.nextInt();

        int [][] newArray = new int[5][5];
        
        switch (a) {
            case 1:
                
                for (int i = x-1; i < x + b -1; i++) {
                    for (int j = y -1; j < y + b -1; j++) {
                                                newArray[i][j] = array[x+b+y-j-3][y+i-x];    
                    }
                }
                
                
                break;
            case 2:
                
                for (int i = x-1; i < x + b -1; i++) {
                    for (int j = y -1; j < y + b -1; j++) {
                        newArray[i][j] = array[j- y + x][x+y+b-i-3];    
                    }
                }
                
                break;
        default:
            break;
        }
        
        for(int i = 0; i <5;i++){
            for (int j = 0; j < 5; j++) {
                if (i>= x-1 && i < x + b -1 && j>=y-1 && j < y + b -1) {
                    System.out.print(newArray[i][j]);
                }else {
                    System.out.print(array[i][j]);
                }
                if (j != 4) {
                    System.out.print(" ");
                }
            }
            System.out.println();
        }
    }
}

打牌

题目链接

https://www.nowcoder.com/practice/82442ee76977479e8ab4b88dfadfca9f?tpId=67&tqId=29640&tPage=1&ru=%2Fkaoyan%2Fretest%2F1005&qru=%2Fta%2Fbupt-kaoyan%2Fquestion-ranking

思路解析

这道题目已经简化了,给的数据一定是排序好的(手里拿着已经排好序的牌),所以在判断的时候,我们使用一个循环,在循环中构造中大于题目给的牌,然后用java的String.contains判断,自己手上的 牌有没有构造的牌即可。

AC代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String string = scanner.nextLine();
        String string2 = scanner.nextLine();
        
        char[] array = string2.toCharArray();
        
        int lenght = array.length;
        boolean isHave = false;

        switch (lenght) {
        case 1:
            int value = Integer.parseInt(string2);
            char[] arrayByhave  = string.toCharArray();
            for (int i = 0; i < arrayByhave.length; i++) {
                if (Integer.parseInt(arrayByhave[i] + "") > value ) {
                    isHave = true;
                    break;
                }
            }
            
            break;

        case 2:
        case 3:
        case 4:
//            System.out.println("ok");
            int start = Integer.parseInt(array[0] + "");
            for (int i = start + 1; i <= 9; i++) {
                String temp = "";
                for (int j = 0; j < lenght; j++) {
                    temp += i + ""; 
                }
//                System.out.println("临时生成的字符串" + temp);
                
                if (string.contains(temp)) {
                    isHave = true;
                    break;
                }
            }
            
            
            break;
        case 5:
            String[]  strArray = new String[]{"12345", "23456", "34567","45678","56789"}; 
            int flag = 0;
            for (int i = 0; i < strArray.length; i++) {
                if (string2.equals(strArray[i])) {
                    flag = i;
                    break;
                }
            }
            
            String[] str1Array = string.split("");
            List<String> list = new ArrayList<>(new LinkedHashSet<>(Arrays.asList(str1Array)));
            StringBuilder sb = new StringBuilder();  
            for (int i = 0; i < list.size(); i++) {  
                    sb.append(list.get(i));  
            }
            String listToString = sb.toString();
//            System.out.println("字符串" + listToString);
            for (int i = flag + 1; i < strArray.length; i++) {
                if (listToString.contains(strArray[i])) {
                    isHave = true;
                    break;
                }
            }
            break;
        default:
            break;
        }
        
        if (isHave) {
            System.out.println("YES");
        }else {
            System.out.println("NO");
        }
        
    }

}

树查找

题目链接

https://www.nowcoder.com/practice/9a10d5e7d99c45e2a462644d46c428e4?tpId=67&tqId=29641&tPage=1&ru=%2Fkaoyan%2Fretest%2F1005&qru=%2Fta%2Fbupt-kaoyan%2Fquestion-ranking

思路解析

这道题目虽然是树的题目,但没必要构造出真实的树,因为题目说了是完全二叉树,输出某一深度的所有节点。某一深度k的所有节点编号是有范围的,起始编号是2^(k-1) ,终点编号是 min(节点总数-1,2^k -1)。

如果起始编号 > 终点编码,那就是不存在该深度的结点。

AC代码

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(scanner.nextInt());
        }
        int depth = scanner.nextInt();
        int vertexNumStart = 0;
        int vertexNumEnd = 0;
        for (int i = 1; i < depth; i++) {
            vertexNumStart += vertexsInDepth(i);
            
        }
        vertexNumEnd = vertexNumStart + vertexsInDepth(depth);
        int end = Math.min(list.size(), vertexNumEnd);
        if (end <= vertexNumStart) {
            System.out.println("EMPTY");
        }else {
            for (int i = vertexNumStart; i < end; i++) {
                System.out.print(list.get(i));
                if (i!=end -1) {
                    System.out.print(" ");
                }
            }        
        }
    }
    
    public static int vertexsInDepth(int depth) {
        return (int) Math.pow(2, depth -1);
    }
}

查找

题目链接

https://www.nowcoder.com/practice/a988eda518f242c29009f8620f654ede?tpId=67&tqId=29642&tPage=1&ru=%2Fkaoyan%2Fretest%2F1005&qru=%2Fta%2Fbupt-kaoyan%2Fquestion-ranking

思路解析

题目是查找,事实上内容是对字符串的操作。

一个是对字符串部分子串翻转,一个是对部分子串替换。

这个使用java的StringBuilder内置的reverse()replace两个方法就很简单的完成了。

AC代码

import java.util.Scanner;

public class Main {
    static Scanner scanner;
    static String string;
    public static void main(String[] args) {
        scanner = new Scanner(System.in);
        string = scanner.next();
        int num = scanner.nextInt();
        for (int i = 0; i < num; i++) {
            Main search = new Main();
            search.handle();    
        }
    }
    
    public void handle(){
        String opration = scanner.next();
        char[] toArray = opration.toCharArray();
        switch (toArray[0]) {
        case '0':
            int start = Integer.parseInt(toArray[1] + "");
            int end = Integer.parseInt(toArray[1] + "") + Integer.parseInt(toArray[2] + "");
            String subString = string.substring(start,end);
            subString = new StringBuilder(subString).reverse().toString();
            string = new StringBuilder(string).replace(start, end, subString).toString();
            break;
        case '1':
            int start1 = Integer.parseInt(toArray[1] + "");
            int end1 = Integer.parseInt(toArray[1] + "") + Integer.parseInt(toArray[2] + "");
            StringBuilder     ToReplaceStrSb = new StringBuilder();
            for (int i = 3; i < toArray.length; i++) {
                ToReplaceStrSb.append(toArray[i]);
            }
            String toReplaceStr = ToReplaceStrSb.toString();
            string = new StringBuilder(string).replace(start1, end1, toReplaceStr).toString();
            break;

        default:
            break;
        }
        
        System.out.println(string);

    }
}

复数集合

题目链接

https://www.nowcoder.com/practice/abdd24fa839c414a9b83aa9c4ecd05cc?tpId=67&tqId=29643&tPage=1&ru=%2Fkaoyan%2Fretest%2F1005&qru=%2Fta%2Fbupt-kaoyan%2Fquestion-ranking

思路解析

这道题目很简单,就是新建一个复数的类,然后添加和删除复数,没什么好说了。

难点就是对输入进行处理。

AC代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {
    List<Fu> fus = new ArrayList<>();

    static Scanner scanner;
    public static void main(String[] args) {
        scanner = new Scanner(System.in);
        Main fushu = new Main();
        fushu.handle();
    }
    
    public void  handle() {
        fus.clear();
        int num = scanner.nextInt();
        scanner.nextLine();
        for (int i = 0; i < num; i++) {
            String oper = scanner.nextLine();
            String[] operArray = oper.split(" ");
            switch (operArray[0]) {
            case "Pop":
                Pop();
                break;

            case "Insert":
                Insert(operArray[1]);
                break;
            default:
                break;
            }
        }
    }
    
    public void Pop(){
        if (fus.size() == 0) {
            System.out.println("empty");
        }else {
            Collections.sort(fus,new Comparator<Fu>() {
                @Override
                public int compare(Fu o1, Fu o2) {
                    if (o1.getMoValue() < o2.getMoValue()){
                        return 1;
                    }else if (o1.getMoValue() > o2.getMoValue()) {
                        return -1;
                    }else {
                        if (o1.xu > o2.xu) {
                            return 1;
                        }else {
                            return -1;
                        }
                    }
                }
            });    
            System.out.println(fus.get(0).shi + "+i" + fus.get(0).xu);
            fus.remove(0);
            System.out.println("SIZE = " + fus.size());
        }
        
    
        
    }
    
    public void Insert(String data){
        String[] array = data.split("\\+");
        fus.add(new Fu(Integer.parseInt(array[0]),getRealXu(array[1])));
                System.out.println("SIZE = " + fus.size());
    }
    
    public int getRealXu(String str){
        return Integer.parseInt(str.substring(1));
    };
    
    
    class Fu{
        int shi;
        int xu;
        
        public int getMoValue(){
            return (int) (Math.pow(shi, 2) + Math.pow(xu, 2));        
        }
        
        public Fu() {
        }

        public Fu(int shi, int xu) {
            super();
            this.shi = shi;
            this.xu = xu;
        }
    }
    
}

二叉排序树

题目链接

https://www.nowcoder.com/practice/b42cfd38923c4b72bde19b795e78bcb3?tpId=67&tqId=29644&tPage=1&ru=%2Fkaoyan%2Fretest%2F1005&qru=%2Fta%2Fbupt-kaoyan%2Fquestion-ranking

思路解析

这道题有一点难度。

首先构造二叉排序树是一个递归的过程。不断的寻找插入位置,然后把节点插入到合适位置。

但是对于java这门语言,函数传参只能传值,不能传指针或者是引用,所以我们不能用课本上写的那样递归。

课本上递归的终止条件是bt == null,而我们的终止条件是bt.right == null || bt.left == null,因为课本上的函数都是传的引用进去的,所以bt == null的时候,后面给bt赋值一个新的节点,新的节点会自动的链接到他的父节点上!但是我们传的是值过去的就必须手动的链接新的节点。

这题的二叉树的结构就是用左右孩子结构。

AC代码

import java.util.Scanner;

public class Main {
    
    static Scanner scanner;
    TreeNode root;
    public static void main(String[] args) {
        scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            Main binarySortingTree = new Main();
            binarySortingTree.handle();    
        }
    }
        
    
    public void handle() {
        int num = scanner.nextInt();
        int value = scanner.nextInt();
        root = new TreeNode(value);
        for (int i = 1; i < num; i++) {
            int temp = scanner.nextInt();
            BSTInsert(root,temp);
        }
        
        
        preoder(root);
        System.out.println();
        inorder(root);
        System.out.println();
        postOrder(root);
        System.out.println();
        
    }
    

    
    
    public void preoder(TreeNode p) {
        if (p != null) {
            System.out.print(p.value + " ");
            preoder(p.left);
            preoder(p.right);
        }
    }
    
    
    public void inorder(TreeNode p){
        if (p != null) {
            inorder(p.left);
            System.out.print(p.value + " ");
            inorder(p.right);
        }
        
    }
    
    public void postOrder(TreeNode p){
        if (p != null) {
            postOrder(p.left);
            postOrder(p.right);
            System.out.print(p.value + " ");
        }
    }
    
    

    public void BSTInsert(TreeNode bt, int value){
        if (value != bt.value) {
            if (value > bt.value) {
                if (bt.right == null) {
                    bt.right = new TreeNode(value);
                }else{
                    BSTInsert(bt.right, value);
                }
            }else if (value < bt.value) {
                if (bt.left == null) {
                    bt.left = new TreeNode(value);
                }else{
                    BSTInsert(bt.left, value);
                }
            }
        }
    }
    class TreeNode{
        int value;
        TreeNode left;
        TreeNode right;
        
        public TreeNode(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
        
        public TreeNode() {
        }
        
        
    }
}

找最小数

题目链接

https://www.nowcoder.com/practice/ba91786c4759403992896d859e87a6cd?tpId=67&tqId=29645&tPage=1&ru=%2Fkaoyan%2Fretest%2F1005&qru=%2Fta%2Fbupt-kaoyan%2Fquestion-ranking

思路解析

这题很简单,仍然是一对数字,但不能使用Map,因为Map的key不能重复,所以不符合题目的输入。自建一个类。然后使用list的sort方法排序即可。

AC代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main minPair = new Main();
        minPair.handle();
    }
    
    public void handle(){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Pair> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            Pair temp = new Pair(scanner.nextInt(), scanner.nextInt());
            list.add(temp);
        }
        
        Collections.sort(list,new Comparator<Pair>() {

            @Override
            public int compare(Pair o1, Pair o2) {
                if (o1.getKey() > o2.getKey()) {
                    return 1;
                }else if (o1.getKey() < o2.getKey()) {
                    return -1;
                }else {
                    return o1.getValue().compareTo(o2.getValue());
                }
            }
        });
        System.out.println(list.get(0).getKey() + " " + list.get(0).getValue());
    }
    
    class Pair{
        int x;
        int y;
        
        Pair(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
    
         public Integer getKey(){
            return x;
        }
         public Integer getValue(){
            return y;
        }
         
        @Override
        public String toString() {
            // TODO 自动生成的方法存根
            return "x=" + x + "y=" + y;
        }
    }
}

查找

题目链接

https://www.nowcoder.com/practice/d93db01c2ee44e8a9237d63842aca8aa?tpId=67&tqId=29646&tPage=1&ru=%2Fkaoyan%2Fretest%2F1005&qru=%2Fta%2Fbupt-kaoyan%2Fquestion-ranking

AC代码

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                list.add(scanner.nextInt());
            }
            int m = scanner.nextInt();
            for (int i = 0; i < m; i++) {
                int temp = scanner.nextInt();
                if (list.contains(temp)) {
                    System.out.println("YES");
                }else {
                    System.out.println("NO");
                }
            }
        }
    }
}
最后修改:2019 年 03 月 23 日 11 : 56 AM
如果觉得我的文章对你有用,请随意赞赏

2 条评论

  1. 紫书海

    写的很好,很喜欢

  2. 左岸

    说到考研就有点头疼,我去学习了

发表评论