在家照顾即将生产的媳妇以及全职学习已经有一段时间了,每天除了技术学习以外算法也不能落下,但是理论学的再多也不如实践一次,于是乎,决定参加一下面试检验下学习成果,Boss放开简历,立刻就有几个华为OD的来约,遂参加机试,分享题目如下:

日期:2022/08/10

批次:2022/Q2


全程用时大概一小时50分钟,前两道100分的题总耗时不到半小时(练习时做到原题了,属实幸运),后面那道200分的题因为不熟悉二维数组控制台输入,白白耗费了半小时(真是菜鸡本鸡,一个控制台输入卡了半个多小时)

和力扣的自动输入不同,大家一定一定一定要提前熟悉牛客的手动输入模式,否则就会像我一样,白白耗费大量时间

另外:需要手动导包!!!

第一题:查找众数及中位数(100分)

  • 众数是指一组数据中出现次数量多的那个数,众数可以是多个
  • 中位数是指把一组数据从小到大排列,最中间的那个数,如果这组数据的个数是奇数,那最中间那个就是中位数,如果这组数据的个数为偶数,那就把中间的两个数之和除以2,所得的结果就是中位数
  • 查找整型数组中元素的众数并组成一个新的数组,求新数组的中位数
  • 输入描述:
  • 输入一个一维整型数组,数组大小取值范围 0<N<1000,数组中每个元素取值范围 0<E<1000
  • 输出描述:
  • 输出众数组成的新数组的中位数

示例1:
输入
10 11 21 19 21 17 21 16 21 18 15
输出
21

示例2:
输入
2 1 5 4 3 3 9 2 7 4 6 2 15 4 2 4
输出
3

示例3:
输入
5 1 5 3 5 2 5 5 7 6 7 3 7 11 7 55 7 9 98 9 17 9 15 9 9 1 39
输出
7

10分钟AC,这是一道非常常见的题,力扣和牛客题库中都有,但凡认真刷过题的小伙伴肯定做过原题,没啥说的
直接贴上我的答案:

public class 查找众数及中位数 {    public static void main(String[] args) {        Scanner in = new Scanner(System.in);        HashMap<Integer, Integer> map = new HashMap<>();        int max = 0;        List<Integer> list =new ArrayList<>();        while (in.hasNextInt()) {            int num = in.nextInt();            map.merge(num,1,(a,b)->a+b);            if (map.get(num)>max){                list.clear();                list.add(num);                max = map.get(num);            }else if (map.get(num)==max){                list.add(num);            }        }        list.sort(Integer::compare);        int n = list.size();        if (n%2==0){            System.out.print((list.get(n/2)+list.get(n/2-1))/2);        }else{            System.out.print(list.get(n/2));        }    }}

第二题:判断字符串子序列(100分)

  • 给定字符串 target和 source, 判断 target 是否为 source 的子序列。
  • 你可以认为 target 和 source 中仅包含英文小写字母。字符串 source可能会很长(长度 ~= 500,000),而 target 是个短字符串(长度 <=100)。
  • 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,”abc”是”aebycd”的一个子序列,而”ayb”不是)。
  • 请找出最后一个子序列的起始位置。
  • 输入描述:
  • 第一行为target,短字符串(长度 <=100)
  • 第二行为source,长字符串(长度 ~= 500,000)
  • 输出描述:
  • 最后一个子序列的起始位置, 即最后一个子序列首字母的下标
  • 示例1
  • 输入
  • abc
  • abcaybec
  • 输出
  • 3
  • 说明
  • 这里有两个abc的子序列满足,取下标较大的,故返回3
  • 备注:
  • 若在source中找不到target,则输出-1

也是我做过的原题(哈哈大笑,两题都做过,白送200分)10分钟AC

public class 判断字符串子序列 {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        char[] tChars = scanner.nextLine().toCharArray();        char[] sChars = scanner.nextLine().toCharArray();        LinkedHashMap<Character, Integer> characterIntegerLinkedHashMap = new LinkedHashMap<Character, Integer>();        int des=sChars.length;        if (tChars.length>0&&sChars.length>0) {            for (int j = tChars.length - 1; j >= 0; j--) {                for (int i = sChars.length - 1; i >= 0; i--) {                    if (tChars[j] == sChars[i] & des > i) {                        des = i;                        characterIntegerLinkedHashMap.put(tChars[j], i);                        break;                    }                }            }            int ros = 0;            for (int j = tChars.length - 1; j >= 0; j--) {                if (!characterIntegerLinkedHashMap.containsKey(tChars[j])) {                    ros = -1;                    break;                }            }            if (ros != -1) {                System.out.println(characterIntegerLinkedHashMap.get(tChars[0]));            } else {                System.out.println(ros);            }        }else {            System.out.println(-1);        }    }}

第三题:广播服务器(200分)

服务器连接方式包括直接相连,间接连接。A和B直接连接,B和C直接连接,则A和C间接连接。
直接遵接和间接连接都可以发送广播。
给出一个NN数组,代表N个服务器,matrix[i][j]=1,则代表i和j直接连接;不等于1时,代表i和j不直接连接。matrix[i][j]==1, 即自己和自已直接连接。
计算初始需要给几合服务器广播,才可以使每个服务器都收到广播。
输入描述:
输入为N行,每行有N个数字,为0成1,由空格分隔,构成N
N的数组,N的范围为1<=N<=40
输出描述:
输出一个数字,为需要广播的服务器的数量

这题因为输入的二维数组不确定边界以及大小,加上不熟悉手动控制台输入,导致我在处理输入的地方就卡了半个多小时
思路就是典型的dfs搜索

public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int size = 0, num = 0;        List<Integer> list = new ArrayList<>();        while(sc.hasNextLine()){            String[] s = sc.nextLine().split(" ");//获取每行的数据            size = s.length;//一行有几列            num++;//记录二维数组有几行            for(int i=0;i<size;i++){                list.add(Integer.valueOf(s[i]));            }        }        int[][] gbs = new int[num][size];        for(int i=0;i<num;i++){            for(int j=0;j<size;j++){                gbs[i][j] = list.get(i*size+j);//将数据保存至二维数组            }        }        System.out.println(find(gbs));    }    public static int find(int[][] gbs) {        int length = gbs.length;        boolean[] visited = new boolean[length];        int count = 0;        for (int i = 0; i < length; i++) {            if (!visited[i]) {                dfs(gbs, visited, i);                count++;            }        }        return count;    }    public static void dfs(int[][] gbs, boolean[] visited, int i) {        for (int j = 0; j < gbs.length; j++) {            if (gbs[i][j] == 1 && !visited[j]) {                visited[j] = true;                dfs(gbs, visited, j);            }        }    }}