2022.03.23 华为机试Problem 3解题思路
问题简述:
M个面试官,会的语言各不相同
N个受试者,参与某种语言的面试
每个受试者需要2个面试官去面
每个面试官最多面k次
判断是否能够安排好面试?
输入:
4 6 4 (M,N,k)
java c py (面试官1会的3种语言)
java c py (面试官1会的3种语言)
py
c java
py
java (受试者前来面试的语言)
py
c
py
c
java
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表示 不匹配/匹配。
若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]
[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); } } }