2020.3.12 美团实习（小白）

自己是一个小白，第一次参加笔试，以为会有选择填空的，结果直接怼了5道编程题。一脸懵逼。

自己的代码能力也是有限。请大佬们指点一下。

第一题。求有障碍道路的路径个数问题，感觉是dp。但用例过不去。只过了18%

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int n = scanner.nextInt();
            char[][] a = new char[2][n]; //存数据
            for(int i = 0;i < 2;i++){
                String s = scanner.next();
                for(int j = 0;j < n;j++){
                    a[i][j] = s.charAt(j);
                }
            }
           // System.out.println(a);
            int[][] dp = new int[2][n];
            if(a[0][n - 2] != 'X'){
                dp[0][n - 2] = 1;
            }else {
                dp[0][n - 2] = 0;
            }
            if(a[1][n - 2] != 'X'){
                dp[1][n - 2] = 1;
            }else {
                dp[1][n - 2] = 0;
            }

            for(int i = 1;i >=0;i--){
                for(int j = n - 3;j >=0;j--){
                    if(a[i][j] == 'X'){
                        dp[i][j] = 0;
                    }else {
                        if(i == 1){
                            dp[i][j] = dp[i][j + 1] + dp[i - 1][j + 1];
                        }else {
                            dp[i][j] = dp[i][j + 1] + dp[i + 1][j + 1];
                        }
                    }
                }
            }
            if(dp[0][0] == 0){
                System.out.println(-1);
            }else {
                System.out.print(dp[0][0]);
            }
        }
    }

第二题

第二题不懂什么意思。我以为的是一个数可以一直或运算，但是感觉实现不了，就找出数据中原本的众数去或运算，如果

得到的值原数组中存在的话，就找这个值的次数返回。好像只过了18%

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int n = scanner.nextInt();
            int x = scanner.nextInt();
            int[] a = new int[n];
            for(int i = 0;i < n;i++){
                a[i] = scanner.nextInt();
            }
            HashMap<Integer,Integer> map = new HashMap<>();
            for(int i = 0;i < n;i++){
                if(map.containsKey(a[i])){
                    map.put(a[i],map.get(a[i]) + 1);
                }else {
                    map.put(a[i],1);
                }
            }
            int max = 0;
            int maxV = 0;
            for(int i = 0;i < n;i++){
                if(map.get(a[i]) > max){
                    max = map.get(a[i]);
                    maxV = a[i];
                }
            }
            int count = 0;
            if(map.containsKey(maxV ^ x)){
                count = map.get(maxV ^ x);
            }
            max += count;
            System.out.println(max);
        }
    }

第三题

这个完全没思路，直接略过了

第四题

其实是有思路的，但是到写代码的时候不知道怎么构建图，也不知道怎么找全各个材料。有可能我的数据存放有

问题。

public static void main(String[] args) {
        class Chang{
            int id; //厂编号
            int yId; //长产原材料编号
            public Chang(int id,int yId){
                this.id = id;
                this.yId = yId;
            }
        }
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int n = scanner.nextInt(); //厂数
            int m = scanner.nextInt(); //道路数
            int k = scanner.nextInt(); //原材料数
            ArrayList<Chang> arrayList = new ArrayList<>();
            for(int i = 1;i <= n;i++){
                int temp = scanner.nextInt();
                Chang chang = new Chang(i,temp);
                arrayList.add(chang);
            }
            Chang[][] t = new Chang[2][m]; //存关系
            for(int i = 0;i < m;i++){
                int a = scanner.nextInt();
                int b = scanner.nextInt();
                t[0][i] = arrayList.get(a - 1);
                t[1][i] = arrayList.get(b - 1);
            }
            for(int i = 0;i < m;i++){
                int a = t[0][i].yId;
                int b = t[1][i].yId;
            }
        }
    }

第五题

没见过这样的题，逆元公式不会构建。。

看了大佬们的答案。有个 mod - 2 也不理解。