2022-08-10北京华为OD机试真题分享——满分

叁歲伎倆 2023-10-08 16:26 28阅读 0赞

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

## 日期：2022/08/10 ##

## 批次：2022/Q2 ##

![在这里插入图片描述][d19e352dff1f4ea59504f8bacc7c48f2.png]  
全程用时大概一小时50分钟，前两道100分的题总耗时不到半小时（练习时做到原题了，属实幸运），后面那道200分的题因为不熟悉二维数组控制台输入，白白耗费了半小时（真是菜鸡本鸡，一个控制台输入卡了半个多小时）  
![在这里插入图片描述][8c9bd042c7c04dc2a50b322b17146549.png]

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

另外：需要**手动导包**！！！

## 第一题：查找众数及中位数（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间接连接。  
直接遵接和间接连接都可以发送广播。  
给出一个N*N数组,代表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);
                }
            }
        }
    }

[d19e352dff1f4ea59504f8bacc7c48f2.png]: https://img-blog.csdnimg.cn/d19e352dff1f4ea59504f8bacc7c48f2.png
[8c9bd042c7c04dc2a50b322b17146549.png]: https://img-blog.csdnimg.cn/8c9bd042c7c04dc2a50b322b17146549.png