3-15 字节笔试题解析

1. 用户模型文件去重

题目描述：

简单来说就是给定N行数据，数据格式为：<UserType, ModelFile>

现在要让就相同ModelFile的用户类型进行一个归类，并将每个ModelFile对应的UserType按照字母表的顺序打印出来

思路：

拿到这个题的第一反应是：使用一个HashMap来存储，以ModelFile作为Key，使用一个Set（去重）作为Value存储以ModelFile作为模型文件的UserType，最终遍历HashMap并将Value的Set进行排序输出。但是按照该思路，写出来之后通过率却只有50%，有点迷。有大佬指点一下么？

代码如下：

/**
 * Created by Legolas on 2020/3/15.
 */
public class _First {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int lineNum = sc.nextInt();sc.nextLine();

        // ModelFile作为Key, Set作为Value，用于存储UserType
        Map<String, Set<String>> map = new HashMap<>();
        for(int i=0;i<lineNum;i++){
            String[] line = sc.nextLine().trim().split(" ");
            if(map.containsKey(line[1])){
                map.get(line[1]).add(line[0]);
            }else{
                Set<String> set = new HashSet<>();
                set.add(line[0]);
                map.put(line[1],set);
            }
        }

        for(Map.Entry<String, Set<String>> entry : map.entrySet()){
            // 后来思考了一下，如果上面使用的是TreeSet这里就不用再将UserType导出来排序了
            Set<String> set = entry.getValue();
            List<String> strings = new ArrayList<>(set);
            Collections.sort(strings);

            System.out.print(entry.getKey()+" ");
            for(String s:strings) System.out.print(s+" ");
            System.out.println();
        }
    }
}

2. 贪心算法，补给饮用水

题目描述：

假设你要从0点开始沙漠旅行到终点D，总共D个站点，从一个站点到另一个站点需要消耗1L的水，初始携带的水量为W，但是在路途中是可以补给到一些水的，这些站点的位置在pos数组中给出，在sup数组的对应位置给出了在站点能获得的水量多少。即：在pos[i] 站点能获得的水量为sup[i]，现在要求最少需要加多少次水，如果在路途中会被渴死，直接返回-1

思路：

我觉得我的思路比较容易理解，你现在有携带的水量为W，当前位置为curPos，那么你携带的水能够支撑你走到curPos+W位置，走到该位置之后你再考虑去该位置（如果有）及之前的水站加水（可能在该位置之前有多个水站），此外，为了保证最少的加水次数，应该到能加到最多水的水站加水，而且加完水之后应该给这个水站加一个标记（used数组），以后不能再到该水站取水。

public static int solve(int D, int W, int[] pos, int[] sup){
    int res = 0;

    // 用来指示在特定的水站有没有取过水，一个水站只能取一次水
    boolean[] used = new boolean[pos.length];

    // 旅行者现在所在的位置
    int curPos = 0;

    while (curPos<D){
        // 每次直接跳到能够着的最大位置，携带的水也会被喝光
        curPos+=W;
        W = 0;
        // 如果已经到达终点，则直接返回加了多少次水
        if(curPos>=D) return res;

        // 标记一下能获得最多水的水站在pos中的下标
        int maxIndex = -1;

        for(int i=0;i<pos.length;i++){
            // 当前还没到指定的水站，则不能从这些水站取水，直接break
            if(pos[i]>curPos) break;
            // 如果还没从该水站取水，则会看在这里取水能否得到最大的水量
            if(!used[i] && sup[i]>W) {
                W = sup[i]; maxIndex = i;
            }
        }

        // 没水了，而且也没有水站可以取水，可能在路途上被渴死
        if(maxIndex==-1) return -1;

        used[maxIndex] = true;
        res++;
    }
    return res;
}

3. 带有传送门的迷宫

题目描述：

给定一个用数字表示的迷宫矩阵，其中-2是入口，-3是出口，-1是障碍物，0表示道路，>0的表示传送门，处于传送门的位置可以像道路一样从上下左右走，相比道路传送门可以一步就传送到另外一个传送门的位置。比如上面的例子：第一行的1可以直接跳到行末的1

思路：

这道题的主要思路就是使用BFS（因为是让求最短路径的长度，而不是具体的路径），每次遍历一层，不断的向外扩展（扩展当当前位置的上下左右），不过需要注意的一点就是可以从传送门到达一个非邻近的位置。

但是如果题目的要求是找出所有从迷宫入口到迷宫的出口的所有路径，那么我们就需要使用DFS，这道题如果使用DFS来求解也是可以的，但是复杂度会非常高，需要找到所有入口到出口的路径，求最短路径的长度。

按照BFS的思路可以写出如下的代码：

1. 我们使用一个Map来存储传送门的位置，以传送门的值为key，比如上面的1作为key，以1的所有位置的集合作为value（虽然可能传送门是成对存在的，但是我当时不确定题目所说的成对是两个，还是说成偶数存在，比如可能存在4个1，8个1这样，所以我使用了一个List来存储
2. 上面的Map也可以存储入口的位置，一个迷宫可能有多个入口，所以我们也可以使用Map把这些入口存储下来

备注：

实际上我是下来才意识到自己这一块是不熟练的，我在遇到这道题时一上来就想着能不能使用记忆化DFS的方式去处理，后来代码越写越复杂，导致在这一道题上耽误了很长的时间，最后还没写出来（有点尴尬），所以DFS和BFS，这些基本功还是要多多的加以训练，其实在我搞懂了BFS之后我才发现原来这道题还是蛮简单的。（还好字节有3次笔试机会:-)）

/**
 * Created by Legolas on 2020/3/15.
 */
public class _Third {
    /**
     * test:
4 3
1 0 -1 1
-2 0 -1 -3
2 2 0 0
     */

      // 存储位置
    static class Pos{
        int x;
        int y;
        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    private static final int INF = 2000*2000;
    // 右，左，下，上
    private static int[][] move = new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};
    private static Map<Integer, ArrayList<Pos>> map;

    public static void main(String[] args) {
                // 这是我自己封装的读矩阵的函数，会先读入行和列，再按照行和列读入矩阵
          // 在写笔试的时候可以把一些经常用到的读取函数提前写好，
        // 可以节省很多处理输入的时间(写笔试的一点小Trick)
        int[][] matrix = Read.readMatrix(false);
        map = new HashMap<>();
        int row = matrix.length;
        int col = matrix[0].length;

        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                                // 主要是为了存储传送门，顺道把入口的位置也都存了
                if(map.containsKey(matrix[i][j])){
                    map.get(matrix[i][j]).add(new Pos(i,j));
                }else{
                    ArrayList<Pos> poss = new ArrayList<>();
                    poss.add(new Pos(i,j));
                    map.put(matrix[i][j],poss);
                }
            }
        }
                // 找到所有的入口
        ArrayList<Pos> poss = map.get(-2);
        int min = INF;
        // BFS的做法，遍历入口，找到到达出口的最短距离
        for(Pos pos:poss){
            min = Math.min(min, searchGate(matrix, pos.x, pos.y));
        }
        System.out.println(min);
    }

    // BFS的做法，i,j是迷宫入口位置
    public static int searchGate(int[][] matrix, int i ,int j){
        int res = 0;
        Queue<Pos> queue = new LinkedList<>();
        int row = matrix.length;
        int col = matrix[0].length;
          // 用于标记一个位置是否被遍历过
        boolean[][] visited = new boolean[row][col];
        queue.offer(new Pos(i, j));
        visited[i][j] = true;

        while (!queue.isEmpty()) {
            int size = queue.size();
            // 处理下一层
            for (int k = 0; k < size; k++) {
                Pos pos = queue.poll();
                if (matrix[pos.x][pos.y] == -3) return res;
                // 处理上下左右的情况
                for (int[] m : move) {
                    int x = pos.x + m[0];
                    int y = pos.y + m[1];
                    // 检测是否到边界，以及有没有遇到障碍，有没有被遍历过
                    if (x >= 0 && x < row && y >= 0 && y < col 
                        && !visited[x][y] && matrix[x][y] != -1) {
                        // 添加到队列中以便下次遍历
                        queue.offer(new Pos(x, y));
                        visited[x][y] = true;
                    }
                }
                // 处理传送门的情况
                if (matrix[pos.x][pos.y] > 0) {
                    // 多个传送门出口，map存储的是传送门的ID和对应的位置
                    ArrayList<Pos> poss = map.get(matrix[pos.x][pos.y]);
                    for (Pos p : poss) {
                        // 遍历到自己，或者传送门已经被遍历过都不会再通过传送门
                        if (p.x == pos.x && p.y == pos.y) continue;
                        if (visited[p.x][p.y]) continue;

                        // 将传送门封锁
                        queue.offer(new Pos(p.x, p.y));
                        visited[p.x][p.y] = true;
                    }
                }
            }
            res++;
        }
        return -1;
    }
}

4. 消消乐

题目描述：

给定一个消消乐乐矩阵，空格用'.'表示，物体用大写字母来表示。接着输入位置（, ）和（, ）判断这两个位置的物体能不能消掉。

两个物体能不能消掉主要有两个限制：

1. 两个位置的物体应该是一样的，比如A和A才能消，而A和B则不能消
2. （, ）和（, ）最多只能用三条水平或者垂直的直线相连

求解思路：

主要就是三种情况：

1. 直连

   如果 则检查两个坐标之间的位置是否全是空格，如果不是则不能直连

2. 需要转一次折，用两条线相连

   这个可以转化成直连的情况，比如在上面的例子中：

   我们可以转化为（, ）和 （, ） 的直连与上（, ）和 （, ）的直连，不过还需要判断一下

   也可以转化为（, ）和 （, ） 的直连与上（, ）和 （, ）的直连，不过还需要判断一下

   只要这两种情况中的其中一种可行，那么（, ）和（, ）位置上的物体就是可以消的

3. 需要转两次折，用三条线相连

   这种情况可以转化为两条线相连的情况

   比如第一行的两个A，左边的A可以向上面探测位置（0，1），并试探上位置（0，1）和右边的A是不是可以用两条线相连

   再比如第一行的B和第三行的B，第一行的B可以探测左边的位置（1，2），并试探位置（1，2）和第三行的B（位置（3，1））是否能用两条线相连

   从上面我们可以看出，对于三条线相连的，我们要从四个方向上不断去试探，直到遇到障碍（其他物体）或者边界，再或者遇到能消除的情况，才会停下来

上面的三种情况，只要满足任意一种，都是可以消除的，根据上面的思路，可以写出如下的代码：

/**
 * Created by Legolas on 2020/3/15.
 */
public class _Forth {

    //最外面要包一层。
    //直连  A .... A
    public static boolean direct(char[][] matrix, int x1, int y1, int x2, int y2) {
        if(x1 != x2 && y1 != y2)
            return false;
        if(x1 == x2) {
            for(int j = Math.min(y1, y2)+1; j < Math.max(y1, y2); j++)
                if(matrix[x1][j] != '.')
                    return false;
        }
        if(y1 == y2) {
            for(int i = Math.min(x1, x2)+1; i < Math.max(x1, x2); i++)
                if(matrix[i][y1] != '.')
                    return false;
        }
        return true;
    }

    // 一折     A ....
    //          .... A
    public static boolean one(char[][] matrix, int x1, int y1, int x2, int y2) {
        if(x1 == x2 || y1 == y2)
            return false;

        if(direct(matrix, x1, y1, x1, y2) && matrix[x1][y2]=='.' && direct(matrix, x1, y2, x2, y2)  // 经过x1，y2
                || direct(matrix, x1, y1, x2, y1) && matrix[x2][y1] == '.' && direct(matrix, x2, y1, x2, y2 )  ) {  //经过 x2, y1
            return true;
        }
        return false;
    }

    // 两折
    //         A ... B ....
    //         ......C.....A
    public static boolean two(char[][] matrix, int x1, int y1, int x2, int y2) {
        // 往下走，看能不能消
        for(int i = x1; i < matrix.length && matrix[i][y1] == '.'; i++) {
            if(one(matrix, i, y1, x2, y2)){
                return true;
            }
        }
        // 往下走，看能不能消
        for(int i = x1; i >= 0 && matrix[i][y1] == '.'; i--) {
            if(one(matrix, i, y1, x2, y2)) {
                return true;
            }
        }
        // 往右走，看能不能消
        for(int j = y1; j <= matrix[0].length && matrix[x1][j] == '.'; j++) {
            if(one(matrix, x1, j, x2, y2))
            {
                return true;
            }
        }
        // 往左走，看能不能消
        for(int j = y1; j >= 0 && matrix[x1][j] == '.'; j--) {
            if(one(matrix, x1, j, x2, y2))
            {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int col = sc.nextInt();
        int row = sc.nextInt();sc.nextLine();

        // 在外面包裹一层'.'
        char[][] matrix = new char[row+2][col+2];
        Arrays.fill(matrix[0],'.');
        Arrays.fill(matrix[row+1],'.');
        for(int i=1;i<=row;i++){
            matrix[i][0] = '.';
            char[] tmp = sc.nextLine().toCharArray();
            for(int j=1;j<=col;j++){
                matrix[i][j] = tmp[j-1];
            }
            matrix[i][col+1]='.';
        }

        // 步数
        int testNum = sc.nextInt();
        boolean[] res = new boolean[testNum];

        for(int i=0;i<testNum;i++){
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            res[i] = (matrix[x1][y1]==matrix[x2][y2]) && (direct(matrix, x1, y1, x2, y2)
                         || one(matrix, x1, y1, x2, y2) || two(matrix, x1, y1, x2, y2));
            if(res[i]){ // 如果消掉
                matrix[x1][y1]='.';
                matrix[x2][y2]='.';
            }
        }
        for(int i=0;i<testNum;i++) {
            if(res[i]) System.out.println("YES");
            else System.out.println("NO");
        }

    }

}