友人C

北邮2014年计院机试(上午)
Problem A. 众数题目描述题目链接给定一个长度为N的非降数列,求数列中出现次数最多的数。如果答案不唯一,输...
扫描右侧二维码阅读全文
01
2019/03

北邮2014年计院机试(上午)

Problem A. 众数

题目描述

题目链接

给定一个长度为N的非降数列,求数列中出现次数最多的数。如果答案不唯一,输出其中最小的数。

输入格式

输入数据第一行是一个整数T(1≤T≤100),表示测试数据的组数。对于每组测试数据:
第一行是一个正整数N(1≤N≤100),表示数列长度。
第二行有N个整数,整数之间用空格隔开,所有的整数都不超过105,表示这个数列。

输出格式

对于每组测试数据,输出一个整数。

输入样例

2
4
1 1 1 2
5
1 1 2 2 3

题目思路

  • 用java里面的Map数据结构,统计每一个数字出现的次数。
  • 然后对Map进行排序。
Map 排序

利用map的entrySet()(返回键值对的set集合)将map转换成list,然后对list进行排序。

List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(arrayMap.entrySet());

AC代码

import java.io.IOException;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {


        Scanner scanner = new Scanner(System.in);

        int arrayNum = scanner.nextInt();
        for (int i = 0;i < arrayNum;i++){
            //input
            int num = scanner.nextInt();
            List<Integer> array = new ArrayList<Integer>();
            Map<Integer, Integer> arrayMap = new HashMap<Integer, Integer>();

            for (int j = 0; j < num; j++){
                int in = scanner.nextInt();
                array.add(in);
                if (arrayMap.containsKey(in)){
                    arrayMap.put(in,arrayMap.get(in)+1);
                }else {
                    arrayMap.put(in,1);
                }
            }

            //from small to big by number of appearance
            List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(arrayMap.entrySet());
            Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
                @Override
                public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                    if (o1.getValue() < o2.getValue()){
                        return 1;
                    }else if (o1.getValue() > o2.getValue()){
                        return -1;
                    }
                    else {
                        if (o1.getKey() > o2.getKey()){
                            return 1;
                        }else if (o1.getKey() < o2.getKey()){
                            return -1;
                        }else {
                            return 0;
                        }
                    }
                }
            });

            System.out.println(list.get(0).getKey());
        }

        scanner.close();
    }
}

Problem B. 旋转图像

题目描述

题目链接

在图形学中,我们经常需要对具体的图像进行一些处理。在这个问题中,你的任务是将一幅只包含01像素点的图片进行顺时针旋转。旋转的角度仅包含0度,90度,180度和270度。

输入格式

输入的第行是一个整数T (T≤50),表示输入的数据组数。
每组测试数据的第一.行是两个整数N和M(1≤N,M≤50),表示图片的高度和宽度。
接下来N行,每行是一个长度为M的01串,表示图片的像素点。最后一行是一个整数angle,表示旋转的角度。

输出格式

对于每组测试数据,输出旋转后得到的图片。请注意不要输出多余的空格或空行。

输入样例

2
2 3
111
000
90
3 3
111
101
111
180

输出样例

01
01
01
111
101
111

思路解析

  • 对字符串进行按位拆分,用到string.toCharArray() 拆分成字符数组。
  • 对旋转90,180,270分别写一个函数。(不要忘记对旋转0时候要原封不对的输出)

可以自己写一个例子,比如

123
456
789

然后分别旋转90,180,270找规律,不难看出字符输出的规律。(就是换个方式输出原数组而已)

AC代码

import java.io.IOException;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

    private static List<char[]> imageRow = new ArrayList<char[]>();

    public static  void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int arrayNum = scanner.nextInt();
        for (int i = 0;i < arrayNum; i++){
            int row = scanner.nextInt();
            int column = scanner.nextInt();
            imageRow.clear();
            List<Integer> imageColumn = new ArrayList<Integer>();
            for (int j = 0;j<row;j++){//input colum data
                String number = scanner.next();
                char[] columnArray =  number.toCharArray();
                imageRow.add(columnArray);
            }
            switch (scanner.nextInt()){
                case 0:
                    for (int k = 0; k<row; k++){
                        for (int m = 0;m < column;m++){
                            System.out.print(imageRow.get(k)[m]);
                        }
                        System.out.println();
                    }
                    break;
                case 90:
                    rotate90(row,column);
                    break;
                case 180:
                    rotate180(row,column);
                    break;
                case 270:
                    rotate270(row,column);
                    break;
            }
        }
    }


    private static void rotate90(int row,int column){
        for (int j = 0; j<column;j++){
            for (int i = row -1;i>=0; i--){
                System.out.print(imageRow.get(i)[j]);
            }
            System.out.println();
        }
    }


    private static void rotate180(int row,int column){
        for (int i = row -1; i>=0;i--){
            for (int j = column-1;j>=0;j-- ){
                System.out.print(imageRow.get(i)[j]);
            }
            System.out.println();
        }
    }


    private static void rotate270(int row,int column){
        for (int j = column - 1; j>= 0 ;j--){
            for (int i = 0 ;i < row; i++ ){
                System.out.print(imageRow.get(i)[j]);
            }
            System.out.println();
        }
    }

}

Problem C. 网络的核

题目描述

题目链接

给定一个无向网络G,网络中共有N个节点(从1编号到N), M条边,求网络的核。
网络的核: 到网络中其他节点的距离之和最小的节点。且对于不连通的两点,它们之间的距离为N。
如果有多组解,输出编号最小的节点。

输入格式

输入的第一行是一个整数T(T≤25),表示输入的数据组数。
对于每组测试数据:

第一行有两个整数N,M(1≤N≤50, 0≤M≤N*(N-1),表示网络中有N个点,M条边。
接下来M行,每行两个整数u,v(1≤u,v≤N, u≠v),表示点u和点v之间有一条距离为1的边。任意两个点之间最多只会有一条边相连。

输出格式

对于每组测试数据,输出网络的核。

输入样例

2
3 3
1 2
1 3
2 3
4 2
1 2
2 3

输出样例

1
2

思路解析

  • 正确理解核。即图中的某个点到其他所有点距离之后最小的顶点。显然是最短路径。比较简单方法是弗洛伊德(把每个顶点i作为中间点,用三重循环,将 A[j,k] 距离 与 A[j,i] + A [i,k] 距离之和比较,并判断是否需要修改)
  • 图数据结构的表示,简单的写法是二维矩阵表示(一般OJ题用顺序存储结构用时更少),或者用顶点链表,每个顶点后面跟着该顶点的边的集合。

AC代码

import java.io.IOException;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException{
        Main core = new Main();
        core.handle();
    }

    private void handle(){
        Scanner scanner = new Scanner(System.in);
        int arrayNum = scanner.nextInt();
        for (int x =0 ;x < arrayNum;x++){
            MGraph mGraph = new MGraph();
            mGraph.setVertexNum(scanner.nextInt());
            mGraph.setEdgeNum(scanner.nextInt());
            for (int j = 0; j < mGraph.getEdgeNum(); j++){//input edges data
                int vertex1 = scanner.nextInt();
                int vertex2 = scanner.nextInt();
                mGraph.edges[vertex1][vertex2] = 1;
                mGraph.edges[vertex2][vertex1] = 1;
            }
            //use floyd to calculate A[]
            mGraph.initA_array();

            for (int k = 1;k<= mGraph.getVertexNum(); k++){// circle each vertex as an intermediate point
                for (int l=1;l <= mGraph.getVertexNum();l++){
                    for (int m = 1;m <= mGraph.getVertexNum();m++){
                        if (mGraph.A[l][m] > mGraph.A[l][k] + mGraph.A[k][m]){
                            mGraph.A[l][m] = mGraph.A[l][k] + mGraph.A[m][k];
                        }
                    }
                }
            }
            //
            Map<Integer, Integer> arrayMap = new HashMap<Integer, Integer>();

            for (int i = 1; i <= mGraph.getVertexNum();i++){
                int distanceToOtherVertexes = 0;
                for (int j = 1; j <= mGraph.getVertexNum();j++){
                    distanceToOtherVertexes += mGraph.A[i][j];
                }
                arrayMap.put(i,distanceToOtherVertexes);
            }

            //sort and print the vertex which has the shortest distance to other vertexes
            List<Map.Entry<Integer,Integer>> sortList = new ArrayList<Map.Entry<Integer,Integer>>(arrayMap.entrySet());
            Collections.sort(sortList, new Comparator<Map.Entry<Integer, Integer>>() {
                @Override
                public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                    if (o2.getValue() < o1.getValue()){
                        return 1;
                    }else if (o2.getValue() > o1.getValue()){
                        return  -1;
                    }else {
                        if (o2.getKey() <o1.getKey()){
                            return 1;
                        }else if (o2.getKey() > o1.getKey()){
                            return -1;
                        }else {
                            return 0;
                        }
                    }
                }
            });
            System.out.println(sortList.get(0).getKey());
        }
    }


    class MGraph{
        int vertexNum;
        int edgeNum;

        int edges[][] = new int[51][51];
        int A[][] = new int[51][51];//distance

        public MGraph() {
            for (int i = 0;i<51;i++){
                for (int j = 0; j< 51;j++){
                    edges[i][j] = -1;//init edges array
                }
            }
        }

        public void initA_array(){
            for (int i = 1;i<=this.getVertexNum();i++){
                for (int j = 1;j<=this.getVertexNum();j++){
                    if (edges[i][j] == -1){//not have edges between the two vexes
                        A[i][j] = this.getVertexNum();
                    }else {
                        A[i][j] = edges[i][j];//because not have weight of edges,so it is a fixed value 1
                    }
                }
            }
        }

        public int getVertexNum() {
            return vertexNum;
        }

        public void setVertexNum(int vertexNum) {
            this.vertexNum = vertexNum;
        }

        public int getEdgeNum() {
            return edgeNum;
        }

        public void setEdgeNum(int edgeNum) {
            this.edgeNum = edgeNum;
        }

        public int[][] getEdges() {
            return edges;
        }

        public void setEdges(int[][] edges) {
            this.edges = edges;
        }
    }
}

Problem D. Python List

题目描述

[题目链接](https://vpn.bupt.edu.cn/http/10.105.242.80/problem/p/273/
)

在Python中,List (列表)是一种非常重要的数据结构。它与C/C++/Java中的数组有些类似,但支持添加新元素时的动态扩展。在这个问题中,你需要处理如下的几种对List的操作。

L=[]: 将名字为L的List清空。在这里,List 的名字是长度为1到10之间
的字符串(只包括大小写字母)。如果L原来不存在,这个语句相当于定义了一个名字为L的空列表。
L.append(x):向L的末端插入元素x。为方便起见,这里的x只会是[0, 65536]之间的整数。
L.sort():将L中的元素按升序排序。
L[id]:返回L中下标为id(id≥0)的值。下标是从0开始计数的。
给定若干Python语句,你的任务是对于每个形如L[id]的语句,输出它返回的值。

输入格式

输入数据包含多组测试数据。请注意各组测试数据之间是相互独立的。输入的第一行是一个整数T(T≤100),表示测试数据的组数。
每组测试数据第一行是语句的数量N (N≤100)。接下来N行,每行一个python语句。测试数据保证只会出现上述四种语句,语句中间不会出现空格。一个List在被使用前一定会被先定义。

输出格式

对于每个查询,输出查找的L[id]的值。如果id超出了当前List 的下标范围,;输出一行ERROR。

样例输入

2
5
a=[]
a.append(0)
a.append(1)
a[0]
a[1]
8
lista=[]
lista.append(123)
lista.append(65)
lista[0]
lista.sort()
lista[0]
listb=[]
listb[0]

样例输出

0
1
123
65
ERROR

思路解析

  • 对输入的操作语句进行分离。这里用到JAVA里面string.split([正则表达式])或者是Pattern p = Pattern.compile([正则表达式]) p.split(string)两种方法都可以。前者更简单一点。
  • 使用IDEA注意输入a.append(0)不能直接手敲进去,而是要复制粘贴过去,否则这个0会变成特殊字符,而导致输入错误

AC代码

import com.sun.org.apache.xalan.internal.lib.ExsltStrings;

import java.io.IOException;
import java.util.*;
import java.util.regex.Pattern;

public class Main {
    public static void main(String[] args)throws IOException{
        Main list = new Main();
        list.handle();
    }

    private void handle(){
        Scanner scanner = new Scanner(System.in);
        int arrayNum = scanner.nextInt();
        for (int i = 0; i < arrayNum;i++){
            int num = scanner.nextInt();
            PythonListList pythonListList = new PythonListList();
            for (int j = 0; j<num; j++){
                String input = scanner.next();
                Pattern p = Pattern.compile("\\.");
                String[] result = p.split(input);
                String arrayName;
                if (result.length == 1){
                    p = Pattern.compile("=");
                    String [] result2 = p.split(input);
                    if (result2.length == 1){//get value by index
                        //get the array name and query value
                        int pos = input.indexOf("[");//L[id]
                        arrayName = input.substring(0,pos);
                        int index = Integer.parseInt(input.substring(pos + 1,input.length()-1));
                        int listIndex = pythonListList.find(arrayName);
                        if (listIndex != -1){
                            if (index <= pythonListList.pythonLists.get(listIndex).list.size() -1){
                                System.out.println(pythonListList.pythonLists.get(listIndex).list.get(index));
                            }else {// index is greater than the maximum of the array
                                System.out.println("ERROR");
                            }
                        }else {// not have the array
                            System.out.println("ERROR");
                        }

                    }else if (result2.length == 2){//clear or create array
                        arrayName = result2[0];
                        int x = pythonListList.find(arrayName);
                        if (x != -1){
                            //clear the array
                            pythonListList.pythonLists.get(x).list.clear();
                        }else {
                            //create new array
                            pythonListList.pythonLists.add(new PythonList(arrayName));
                        }
                    }
                }else if (result.length == 2){//append(x) or sort()
                    arrayName = result[0];
                    String lastString = result[1];
                    int arrayIndex = pythonListList.find(arrayName);
                    if (arrayIndex != -1){
                        //get operation name
                        int pos = lastString.indexOf("(");
                        String operation = lastString.substring(0,pos);
                        if (operation.equals("append")){
                            int value = Integer.parseInt(lastString.substring(pos + 1,lastString.length() - 1));
                            pythonListList.pythonLists.get(arrayIndex).list.add(value);
                        }else if (operation.equals("sort")){
                            Collections.sort(pythonListList.pythonLists.get(arrayIndex).list);

                        }
                    }else {// not have the array
                        System.out.println("ERROR");
                    }

                }
            }
        }
    }


    class PythonListList{
        List<PythonList> pythonLists = new ArrayList<PythonList>();

        int find(String name){
            for (int i =0;i < pythonLists.size();i++){
                if (name.equals(pythonLists.get(i).name)){
                    return i;//following operation is clear the array
                }
            }
            return -1;// following operation is create
        }

    }

    class PythonList{
        String name;
        List<Integer> list = new ArrayList<Integer>();

        PythonList() {
        }
        public PythonList(String name) {
            this.name = name;
        }
    }
}
c++ 版本可以参见 https://blog.csdn.net/TQCAI666/article/details/86767987
最后修改:2019 年 03 月 01 日 08 : 14 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论