美团java后端实习 4.16笔试复盘

总的来说，之前没太熟悉这个编译器，牛客用的比较多吧。测试用例需要自己输入和处理，一些特殊情况的输出结果没有说明，以下代码时笔试时的代码，后续没有改进~~

说明：

请使用标准输入输出(System.in, System.out)；
勿使用图形、文件、网络、系统相关的操作，如java.lang.Process , javax.swing.JFrame , Runtime.getRuntime
不要自定义包名称，否则会报错，即不要添加package answer之类的语句；
您可以写很多个类，但是必须有一个类名为Main，并且为public属性，并且Main为唯一的public class
Main类的里面必须包含一个名字为'main'的静态方法（函数），这个方法是程序的入口

1、输出单科最优学生人数

n个学生，m个科目，现在学校要给优秀学生颁奖，评判标准是至少在一个科目上获得了最高分【并列第一的情况！！这个当时没考虑到】
输入：第一行两个参数，分别是n：学生人数；m：科目数；接着下面有n行m列数据，每行数据表示每个同学每一门科目的成绩

5 5
28 35 38 10 19
4 76 72 38 86
96 80 81 17 10

70 64 86 85 10
1 93 19 34 41

输出：学校为每门课成绩最好的同学评优，输出评优的人数（按照人计数，不按照人次计数）

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int kindClass = sc.nextInt();
		if (num <= 0 || kindClass<=0) {
			System.out.println(0);
			return;
		}
		int[][] scores = new int[num][kindClass];
		for (int i = 0; i < num; i++) {
			for (int j = 0; j < kindClass; j++) {
				scores[i][j] = sc.nextInt();
			}
		}
		Set<Integer> set = new HashSet<Integer>();
		for (int j = 0; j < kindClass; j++) {
			int max = 0,maxIndex=0;
			for (int i = 0; i < num; i++) {
				if (scores[i][j] > max) {
					max = scores[i][j];
					maxIndex = i;
				}
			}
			set.add(maxIndex);
		}
		System.out.println(set.size());
	}

2、输出循环结果的最小长度

给定四个数a,b,m,x 然后有个运算法则是x=(a*x+b)%m，因为是取余，所以x是重复的，把重循环长度打印出来

input a,b,m,x
while true:
x=(a*x+b)%m
print(x)
end while

输入：依次为a,b,m,x

2 1 5 2

输出：由于运算依次输出0,1,3,2,0,1,3,2,0,1,3,2....，循环的长度最小为4

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int m = sc.nextInt();
		int x = sc.nextInt();
		Queue<Integer> queue = new ArrayDeque<Integer>();
		for (int i = 0; ; i++) {
			x=(a*x+b)%m;
			if (queue.isEmpty()) {
				queue.add(x);
			}else {
				//判断该元素是否等于队首元素
				if (queue.peek().compareTo(x)==0) {
					//继续判断
					Queue<Integer> temp = new ArrayDeque<Integer>(queue);
					int count = 0;
					while (!temp.isEmpty()) {
						if (temp.poll().compareTo(x)==0) {
							count++;
							x=(a*x+b)%m;
						}else {
							break;
						}
					}
					if (temp.isEmpty()) {
						System.out.println(count);
						return;
					}
				}else {
					queue.add(x);
				}
			}
		}
	}

3、输出第k小的有序数对

第一行两个数n和k，n表示有多少个数字，k表示输出第k小的有序数对（m,n）。有序数对比较规则是第一个数大的大，第一个数相等则第二个数大的大。输出第k小的有序数对

输入：第一行依次为n，k；第二行有n个数

3 4
2 1 3

输出：2,1,3可以组成有序数对从小到大排序：（1,1）、（1,2）、（1,3）、（2,1），（2,2），（2,3），（3,1），（3,1），（3,3），第4晓得数对为（2,1）

(2,1)

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		if (n <= 0 || k <= 0) {
			return;
		}
		int[] nums = new int[n];
		for (int i = 0; i < n; i++) {
			nums[i] = sc.nextInt();
		}

		Arrays.sort(nums);

		// 看开头是什么
		int zhengshu = k / n, yushu = k % n;
		if (yushu == 0) {
			System.out.println("(" + nums[zhengshu - 1] + "," + nums[n - 1] + ")");
		}else {
			System.out.println("("+nums[zhengshu]+","+nums[yushu-1]+")");
		}
	}

4、伪中位数

第一行两个数n和k，n表示有多少个数字，k是伪中位数。伪中位数定义：第 |_（n+1）/2_| 个数，|__| 表示向下取整。输出为至少需要增加多少个数才能使伪中位数为k

输入：第一行依次为n，k；第二行有n个数

4 2
2 3 3 3
输出：要想使2,3,3,3的伪中位数为2，可以是1,1,2,3,3,3，这个数组的伪中位数就是12，因此至少要增加2个数
2

private static int count = 0;
    // 小根堆
    private static PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
    // 大根堆
    private static PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(50, new Comparator<Integer>() {
      @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    });

    public static void insert(Integer num) {
        if (count % 2 == 0) {
            maxHeap.offer(num);
            int max = maxHeap.poll();
            minHeap.offer(max);
        } else {
            minHeap.offer(num);
            int min = minHeap.poll();
            maxHeap.offer(min);
        }
        count++;
    }

    public static int getMid() {
        if (count % 2 == 0) {
            return maxHeap.peek();
        } else {
            return minHeap.peek();
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        if (n <= 0 || k <= 0) {
            return;
        }
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        for (int i = 0; i < nums.length; i++) {
            insert(nums[i]);
        }
        //System.out.println(count);
        while (true) {
            int temp = getMid();
            //System.out.println(temp);
            if (temp == k) {
                System.out.println(count - nums.length);
                return;
            } else if (temp > k) {
                insert(Integer.MIN_VALUE);
            } else {
                insert(Integer.MAX_VALUE);
            }
        }
    }