2022.03.23 华为机试Problem 3解题思路

问题简述

M个面试官,会的语言各不相同
N个受试者,参与某种语言的面试
每个受试者需要2个面试官去面
每个面试官最多面k次
判断是否能够安排好面试?

输入:

4 6 4  (M,N,k)
java c py  (面试官1会的3种语言)
py
c java
py
java (受试者前来面试的语言)
py
c
py
c
java

解决方案:dfs深度优先搜索

1.首先构建一个mat矩阵,存放面试官与受试者语言匹配关系,第m位面试官会第n位受试者的语言,则mat[m][n]=1,否则设为0
(这一步比较关键,如果能想到构建这种关系的话,应该就知道怎么解题了)
    对上述情况例子,mat结果应为:
    [1, 1, 1, 1, 1, 1]
    [0, 1, 0, 1, 0, 0]
    [1, 0, 1, 0, 1, 1]
    [0, 1, 0, 1, 0, 0]

2.再初始化res矩阵,表示面试官与受试者是否要去匹配。在dfs中会对该矩阵的值进行更新:
        若mat[m][n]=0,则由于不匹配,res[m][n]===0(恒为0)    
        否则res[m][n]可通过设置0/1表示 不匹配/匹配。
    例如第1行所有mat为1,则res第1行的每个格点,要么设为1表示组队面试,要么设为0表示不组队

3.dfs的深入方式:如果遇到mat格点为1,则设置res为0/1并进入下一格点,否则直接进入下一格点
        dfs结束条件:格点越过右下角最后一格,此时需要判断本次遍历是否匹配成功
        判断成功条件:条件1:各行不能大于k  条件2:各列必须等于2

4.上述例子的结果
    [1, 0, 1, 0, 1, 1]
    [0, 1, 0, 1, 0, 0]
    [1, 0, 1, 0, 1, 1]
    [0, 1, 0, 1, 0, 0]

注:

今晚做题时没做出来,前两题花了1.5h,剩半小时,这个题刚读完就想到这个思路了,
奈何感觉光写scanner就得花十多分钟,再加上脑子炸了,就放弃本题了。。。
考完冷静下来,花了快1h才写出来,还不确定对不对,测试用例反正是没问题。
写的代码太难看,我已经受不了了,不打算再改了,欢迎各位大佬补充或更改,或指出错误的地方!!!

代码+运行结果:

import java.util.*;

public class Main {
    //分别为面试官数、受试者数、面试最高次数
    static int M,N,k;
    //存放是否匹配的变量
    static boolean flag;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        M = sc.nextInt();
        N = sc.nextInt();
        k = sc.nextInt();
        sc.nextLine();
        //list存放第m位面试官会的语言,如list.get(0)存放第1位面试官的语言,String[]数组存放,长度不定
        ArrayList<String[]> list = new ArrayList<>();
        //mat矩阵存放面试官与受试者语言匹配关系,第m位面试官会第n位受试者的语言,则mat[m][n]=1,否则设为0
        int[][] mat = new int[M][N];
        //res为面试官与受试者是否要去匹配的矩阵。在递归中会对该矩阵的值进行更新
        // 若mat[m][n]=0,则由于不匹配,res[m][n]===0,
        // 否则res[m][n]可通过设置0/1表示 不匹配/匹配。
        int[][] res = new int[M][N];

        //读取面试官会的语言
        for(int i=0;i<M;i++){
            list.add(sc.nextLine().split(" "));
        }
        //下面代码边读取第i位受试者边填充第i列mat矩阵,遇到可以匹配的面试官就将值设为1
        for (int i = 0; i < N; i++) {
            String lg = sc.nextLine();  //读取i号受试者会的语言
            for(int j=0;j<M;j++){
                for(String str:list.get(j)){    //遍历当前面试官语言
                    if(str.equals(lg)){
                        mat[j][i] = 1;
                    }
                }
            }
        }
        //递归操作  递归方案为:遇到mat值为1的格子,对应res设置0或1,否则设置为0
        //当遍历过最后一个节点后,判断res是否满足  条件1:各行不能大于k  条件2:各列必须等于2
        //满足则输出该res矩阵并将flag设为true,否则返回。
        tracbrack(res,mat,0); //block指的是当前遍历到的格点位置,遍历方式:从左到右+1,到达最右端换行
        if(!flag) System.out.println(false);
    }
    public static void tracbrack(int[][] res, int[][] mat, int block){
        //结束条件,当block越过右下角最后一个格点时判断遍历结果
        if(block>=M*N){
            //判断各行和是否大于k
            for (int i = 0; i < M; i++) {
                int sum=0;
                for (int j = 0; j < N; j++) {
                    sum+=res[i][j];
                }
                if(sum>k) return;
            }
            //判断各列和是否等于2
            for (int j = 0; j < N; j++) {
                int sum=0;
                for (int i = 0; i < M; i++) {
                    sum+=res[i][j];
                }
                if(sum!=2) return;
            }
            //上述判断若无返回,说明本次遍历已成功,输出res并返回flag=true
            flag = true;
            System.out.println(true);
            for (int i = 0; i < M; i++) {
                System.out.println(Arrays.toString(res[i]));
            }
            return;
        }
        //计算格点下标,若M=4、N=6,则block=21对应(3,3)
        int x=block/N;
        int y=block%N;
        //如果当前mat=1,则对面试or不面试,即 res=0&nbs***bsp;1 分别进行两次递归
        if(mat[x][y]==1){
            res[x][y] = 0;
            tracbrack(res,mat,block+1);
            res[x][y] = 1;
            tracbrack(res,mat,block+1);
        }
        //如果当前mat=0,直接进入下一格
        else{
            tracbrack(res,mat,block+1);
        }
    }
}

 



#华为机试##华为##笔经#
全部评论
我是按贪心写的,会的越少语言的面试官越先选择面试者,但是只过了35%
4 回复 分享
发布于 2022-03-24 20:40
最大二部图匹配变种?
1 回复 分享
发布于 2022-03-24 11:13
感觉第三题dfs的考频还是很大的。dfs经常就代码量大,还有一些细节多。如果不是拿到就有思路,感觉很难在一定时间内写出来。
1 回复 分享
发布于 2022-03-24 19:52
看到有人说dfs爆搜超时,那我这份代码,是不是也寄了。 可以在中间加一些剪枝优化,但是代码量就上去了
点赞 回复 分享
发布于 2022-03-24 02:53
这是春招笔试还是实习生笔试
点赞 回复 分享
发布于 2022-03-24 04:40
感觉是状态压缩
点赞 回复 分享
发布于 2022-03-24 12:59
我就这么写的,会超时间
点赞 回复 分享
发布于 2022-03-24 17:18
lz有出结果了吗,我第三道也没做出来
点赞 回复 分享
发布于 2022-03-24 17:19
话说机试后大概多久会安排测评和面试呢
点赞 回复 分享
发布于 2022-03-25 11:37
想问下机试可以带书吗
点赞 回复 分享
发布于 2022-03-25 11:43
网络流可以做,不知道有没有更优的解法
点赞 回复 分享
发布于 2022-03-30 00:50
匈牙利算法可以做
点赞 回复 分享
发布于 2022-03-30 16:46
求前两题题目
点赞 回复 分享
发布于 2022-03-31 21:36
暴力回溯 能过多少?
点赞 回复 分享
发布于 2022-05-11 22:01

相关推荐

头像
11-21 11:39
四川大学 Java
是红鸢啊:忘了还没结束,还有字节的5k 违约金
点赞 评论 收藏
分享
19 88 评论
分享
牛客网
牛客企业服务