华为笔试 第三题 采用回溯 leetcode698思想
华为笔试第三题 采用回溯 leetcode698思想 包看包会 前面输入部分采用了牛客一个兄弟的,这里突然找不到了... import java.util.ArrayList; import java.util.Scanner; public class Main{ static int M, N, k; 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; } } } } int NN = N; boolean flag = backTrack(res, mat, NN,0, 0, 2); //block指的是当前遍历到的格点位置,遍历方式:从左到右+1,到达最右端换行 System.out.println(flag); if(flag){ for(int i = 0;i<res.length;i++){ for(int j = 0;j<res[0].length;j++){ System.out.print(res[i][j]+","); } System.out.println(); } } } //n代表在对哪一个学生进行判断,为0结束(第N-n位);count表示当前学生面试数量; start表示对哪一位老师进行检测 public static boolean backTrack(int[][]res, int[][]mat, int n, int count, int start, int target){ if(n==0){ return true; } if(count==target) return backTrack(res, mat, n-1, 0, 0, target); for(int i = start; i < M; i++){ if(mat[i][N-n]!=1) continue; if(!check(res,i)) continue; System.out.println("i:"+i+",N-n:"+(N-n)); res[i][N-n] = 1; if(backTrack(res, mat, n, count+1, i+1, target)) return true; res[i][N-n] = 0; } return false; } //检验老师是否已经面试了k个学生了 private static boolean check(int[][] res, int row) { int count = 0; for(int j = 0;j<N;j++){ count += res[row][j]; } return count<k; } }
#华为##笔试题目#