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);
}
}
}



