华为笔试 第三题 采用回溯 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;
    }

}