记录一道笔试题

下午做了网易的笔试题，还是有一定难度的。

单选、多选涉及了OSI模型、HTTP协议的幂等方法、完全二叉树、Mysql不同锁的兼容性、Linux用户空间和内核空间的关系、进程线程和协程、Docker资源隔离、二叉树的先序遍历和中序遍历、旧接口兼容设计模式。

简答题问了负载均衡和数据库分片的定义、算法与应用场景。

编程题第二题描述如下：

甲和乙在一个地图里相约汇合，假如两人1秒走一格，求他们汇合所需的最短时间。地图是一个二进制矩阵，矩阵元素为0表示此点不可走，为1表示此点可以走。

输入样例：[[1, 1], [1, 1]] 0 0 1 1 输出样例：1

说明：输入[[1, 1], [1, 1]]表示地图是一个2x2的矩阵，0 0表示甲的出生地，1 1表示乙的出生地。输出1说明在1秒后双方可以相遇。

这题目就是个图的最短路径问题。找到双方的最短路径格数，除以2之后向上取整即可。

使用广度优先搜索（Breadth-First Search，BFS）或深度优先搜索（Depth-First-Search，DFS）。

用迪杰斯特拉（Dijkstra）算法就可以搞定，它是广度优先搜索算法。

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] matrix = {{1, 1}, {1, 1}};
        int shortest = s.getEstTime(matrix, 0, 0, 1, 1);
        System.out.println("最短汇合时间为：" + shortest);
    }
}

class Solution {
    public static int MaxValue = 100000;

    public int getEstTime(int[][] map, int a_x, int a_y, int b_x, int b_y) {
        int[][] matrix = getMatrix(map);
        int s = dijstra(matrix, a_x * map.length + a_y, b_x * map.length + b_y);
        if (s % 2 == 1) {
            s++;
        }
        return s / 2;
    }

    public static int[][] getMatrix(int[][] map) {
        int l = map.length;
        int[][] matrix = new int[l * l][l * l];
        int t;
        for (int i = 0; i < l * l; i++) {
            for (int j = 0; j < l * l; j++) {
                matrix[i][j] = MaxValue;
            }
        }
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < l; j++) {
                if (map[i][j] == 0) {
                    continue;
                }
                if (i - 1 >= 0 && map[i - 1][j] == 1) {
                    t = i * l + j;
                    matrix[t - l][t] = 1;
                    matrix[t][t - l] = 1;
                }
                if (i + 1 < l && map[i + 1][j] == 1) {
                    t = i * l + j;
                    matrix[t + l][t] = 1;
                    matrix[t][t + l] = 1;
                }
                if (j + 1 < l && map[i][j + 1] == 1) {
                    t = i * l + j;
                    matrix[t + 1][t] = 1;
                    matrix[t][t + 1] = 1;
                }
                if (j - 1 >= 0 && map[i][j - 1] == 1) {
                    t = i * l + j;
                    matrix[t - 1][t] = 1;
                    matrix[t][t - 1] = 1;
                }
            }
        }

        return matrix;
    }

    public static int dijstra(int[][] matrix, int source, int dest) {
        //最短路径长度
        int[] shortest = new int[matrix.length];
        //判断该点的最短路径是否求出
        int[] visited = new int[matrix.length];

        //初始化源节点
        shortest[source] = 0;
        visited[source] = 1;

        for (int i = 1; i < matrix.length; i++) {
            int min = Integer.MAX_VALUE;
            int index = -1;

            for (int j = 0; j < matrix.length; j++) {
                if (visited[j] == 0 && matrix[source][j] < min) {
                    min = matrix[source][j];
                    index = j;
                }
            }

            // 更新最短路径
            shortest[index] = min;
            visited[index] = 1;

            // 更新从index跳到其它节点的较短路径
            for (int m = 0; m < matrix.length; m++) {
                if (visited[m] == 0 && matrix[source][index] + matrix[index][m] < matrix[source][m]) {
                    matrix[source][m] = matrix[source][index] + matrix[index][m];
                }
            }
        }

        if (shortest[dest] == MaxValue) {
            return -1;
        } else {
            return shortest[dest];
        }
    }
}