网易有道笔试（2022.3.5）

• Q1：n个顶点的双向图，从start到end是否存在有效路径。
• Q2：三个正整数，之间加减乘除任意组合，组合运算结果能否为24。
• Q3：M*N区域的地图存在K个价值不等的宝藏，只能向下和向右，两人离开地图后，最多获取价值。
• Q4：上下电梯，从A到B至少要按几次按钮。

Q1（并查集，AC）

public class Solution1 {
    public boolean validPath(int n, ArrayList<ArrayList<Integer>> sides, int start, int end) {
        // write code here
        UF uf = new UF(n);
        for (ArrayList<Integer> side : sides) {
            uf.union(side.get(0), side.get(1));
        }
        return uf.connected(start, end);
    }

    // 并查集 数据结构
    class UF {
        private int count;
        private final int[] parent;
        // 记录每一个数组记录树的“重量”
        private final int[] size;

        public UF(int n) {
            this.count = n;
            parent = new int[n];
            // 最初每棵树只有一个节点
            // 重量全部初始化为1
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        // 将p和q连接起来
        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) {
                return;
            }
            // 把小一些的树 接到 大一些的树下面
            if (size[rootP] > size[rootQ]) {
                parent[rootQ] = rootP;
                size[rootP] = size[rootQ];
            } else {
                parent[rootP] = rootQ;
                size[rootP] = size[rootP];
            }
            count--;
        }

        // 找到x所属的根节点
        private int find(int x) {
            while (parent[x] != x) {
                // 进行路径压缩
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        // 判断p和q是否连接
        public boolean connected(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            return rootP == rootQ;
        }

        // 返回图中有多少连接分量
        public int count() {
            return this.count;
        }
    }
}

Q2（暴力，87.5%）

public class Solution2 {
    public boolean compute24(int[] inputNumbers) {
        // write code here
        char[] ops = new char[]{'+', '-', '*', '/'};
        List<Integer[]> list = permutation(inputNumbers);
        for (Integer[] integers : list) {
            for (int i = 0; i < 4; i++) {
                if (i == 3 && Math.abs(integers[1]) == 0) {
                    break;
                }
                if (i == 3 && (integers[0] % integers[1] != 0 || integers[1] % integers[0] != 0)) {
                    break;
                }
                float res12 = getNum(integers[0], integers[1], ops[i]);
                for (int j = 0; j < 4; j++) {
                    if (i == 3 && integers[2] == 0) {
                        break;
                    }
                    if (j == 3 && (res12 % integers[2] != 0 || integers[2] % res12 != 0)) {
                        break;
                    }
                    float res123 = getNum(res12, integers[2], ops[j]);
                    if (res123 == 24) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    // 全排列
    private List<Integer[]> permutation(int[] nums) {
        List<Integer[]> list = new LinkedList<>();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i == j) {
                    continue;
                }
                for (int k = 0; k < 3; k++) {
                    if (k == i || k == j) {
                        continue;
                    }
                    list.add(new Integer[]{nums[i], nums[j], nums[k]});
                }
            }
        }
        return list;
    }

    // 计算结果
    private float getNum(float a, float b, char ch) {
        if (ch == '+') {
            return a + b;
        } else if (ch == '-') {
            return a - b;
        } else if (ch == '*') {
            return a * b;
        } else if (ch == '/') {
            return a / b;
        }
        return 0;
    }
}

Q3（动态规划，AC）

public class Solution3 {
    void getMaxVal(int[][] map, int m, int n, int n_x, int n_y, int[] ans, int now) {
        if (n_x == m && n_y == n) {
            int tmp = dp(map, m, n);
            ans[0] = Math.max(ans[0], now + tmp);
        }
        if (n_x + 1 <= m) {
            now += map[n_x + 1][n_y];
            int t = map[n_x + 1][n_y];
            map[n_x + 1][n_y] = 0;
            getMaxVal(map, m, n, n_x + 1, n_y, ans, now);
            now -= t;
            map[n_x + 1][n_y] = t;
        }
        if (n_y + 1 <= n) {
            now += map[n_x][n_y + 1];
            int t = map[n_x][n_y + 1];
            map[n_x][n_y + 1] = 0;
            getMaxVal(map, m, n, n_x, n_y + 1, ans, now);
            now -= t;
            map[n_x][n_y + 1] = t;
        }
    }

    int dp(int[][] map, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = map[i][j];
                dp[i][j] += Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[][] map = new int[m + 1][n + 1];
        while (k-- > 0) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int z = scanner.nextInt();
            map[x][y] = z;
        }
        int[] ans = new int[]{0};
        new Solution3().getMaxVal(map, m, n, 1, 1, ans, 0);
        System.out.println(ans[0]);
    }
}

Q4（bfs，90%）

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;


int search(int n, int a, int b, const vector<int>& k)
{
    queue<int> q;
    vector<bool> vis(n, false);

    q.push(a);
    vis[a - 1] = true;
    int step = 1;
    while (!q.empty()) {
        int size = q.size();
        for (int i=0; i<size; i++) {
            int cur = q.front();
            q.pop();
            int up = cur + k[cur - 1];
            int down = cur - k[cur - 1];
            if (up == b || down == b) {
                return step;
            }
            if (up <= n && !vis[up - 1]) {
                q.push(up);
                vis[up - 1] = true;
            }
            if (down >= 1 && !vis[down - 1]) {
                q.push(down);
                vis[down - 1] = true;
            }
        }
        step++;
    }
    return -1;
}

int main()
{
    int n, a, b;
    cin >> n >> a >> b;
    vector<int> k(n);
    for (int i=0; i<n; i++) {
        cin >> k[i];
    }
    cout << search(n, a, b, k) << endl;
    return 0;
}