米哈游3.19后端笔试

1. 红绿色盲，用了两次dfs，没来得及封装方法，过了

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();
        char[][] chessboard = new char[n][m];
        for (int i = 0; i < n; i++) {
            chessboard[i] = sc.nextLine().toCharArray();
        }
        int[][] used = new int[n][m];
        int trueNum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (used[i][j] == 1) {
                    continue;
                }
                trueNum++;
                dfs(chessboard, used, chessboard[i][j], i, j);
            }
        }
        int falseNum = 0;
        int[][] used2 = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (used2[i][j] == 1) {
                    continue;
                }
                falseNum++;
                dfs2(chessboard, used2, chessboard[i][j], i, j);
            }
        }
        System.out.println(trueNum - falseNum);
    }

    static int[][] directions = {
        {-1, 0}, {1, 0}, {0, -1}, {0, 1}
    };
    public static void dfs(char[][] chessboard, int[][] used, char color, int row, int col) {
        used[row][col] = 1;
        for (int[] direction : directions) {
            int newRow = row + direction[0];
            int newCol = col + direction[1];
            if (newRow < 0 || newRow >= chessboard.length || newCol < 0 || newCol >= chessboard[0].length ||
                used[newRow][newCol] == 1 || chessboard[newRow][newCol] != color) {
                continue;
            }
            dfs(chessboard, used, color, newRow, newCol);
        }
    }


    public static void dfs2(char[][] chessboard, int[][] used, char color, int row, int col) {
        used[row][col] = 1;
        for (int[] direction : directions) {
            int newRow = row + direction[0];
            int newCol = col + direction[1];
            if (newRow < 0 || newRow >= chessboard.length || newCol < 0 || newCol >= chessboard[0].length ||
                    used[newRow][newCol] == 1) {
                continue;
            }
            if (color == 'R' && chessboard[newRow][newCol] != color) {
                continue;
            }
            if (color != 'R' && (chessboard[newRow][newCol] == 'R')) {
                continue;
            }
            dfs2(chessboard, used, color, newRow, newCol);
        }
    }
}

2 删除或添加'mhy'任意次，使得字符串s转为t，mhy是子序列，所以可以在不同地方删除或增加，比如 mabshy -> abs
将两个字符串中的字符非为mhy和非mhy两类，要想转换成功，二者的非mhy类字符一定要相同且出现次数相等，而mhy三个字符出现的次数之差要相等

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        for (int i = 0; i < n; i++) {
            char[] s = sc.nextLine().toCharArray();
            char[] t = sc.nextLine().toCharArray();
            boolean flag = judge(s, t);
            if (flag) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

    public static boolean judge(char[] s, char[] t) {
        Map<Character, Integer> records = new HashMap<>();
        records.put('m', 0);
        records.put('h', 0);
        records.put('y', 0);
        for (int i = 0; i < s.length; i++) {
            Integer count = records.getOrDefault(s[i], 0);
            count++;
            records.put(s[i], count);
        }
        for (int i = 0; i < t.length; i++) {
            if (records.containsKey(t[i])) {
                Integer count = records.get(t[i]);
                count--;
                if (count == 0) {
                    records.remove(t[i]);
                } else {
                    records.put(t[i], count);
                }
            } else {
                // 非 m h y字符没有在另外一个字符串中出现过 肯定不能转换
                return false;
            }
        }
        // s中有多的非mhy字符 不能转换
        for (Character key : records.keySet()) {
            if (key != 'm' && key != 'h' && key != 'y') {
                return false;
            }
        }
        // m h y 三个字符的相差数必须相等
        return records.get('m').equals(records.get('h')) && records.get('h').equals(records.get('y'))
                && records.get('m').equals(records.get('y'));
    }
}