LeetCode Contest 410

欢迎大家加QQ群：623375442。

100393. Snake in Matrix

大小为 n x n 的矩阵 grid 中有一条蛇。蛇可以朝 四个可能的方向 移动。矩阵中的每个单元格都使用位置进行标识： grid[i][j] = (i * n) + j。

蛇从单元格 0 开始，并遵循一系列命令移动。

给你一个整数 n 表示 grid 的大小，另给你一个字符串数组 commands，其中包括 "UP"、"RIGHT"、"DOWN" 和 "LEFT"。题目测评数据保证蛇在整个移动过程中将始终位于 grid 边界内。

返回执行 commands 后蛇所停留的最终单元格的位置。

测试样例：

输入：n = 2, commands = ["RIGHT","DOWN"]

输出：3

解答：按照题意，暴力模拟。

class Solution {
    public int finalPositionOfSnake(int n, List<String> commands) {
        int x = 0, y = 0;
        for (String c : commands) {
            if (c.equals("LEFT")) {
                y -= 1;
            } else if (c.equals("RIGHT")) {
                y += 1;
            } else if (c.equals("UP")) {
                x -= 1;
            } else {
                x += 1;
            }
        }
        return x * n + y;
    }
}

100354. Count the Number of Good Nodes

现有一棵 无向 树，树中包含 n 个节点，按从 0 到 n - 1 标记。树的根节点是节点 0 。给你一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ai, bi] 表示树中节点 ai 与节点 bi 之间存在一条边。

如果一个节点的所有子节点为根的 子树 包含的节点数相同，则认为该节点是一个 好节点。

返回给定树中 好节点 的数量。

子树 指的是一个节点以及它所有后代节点构成的一棵树。

测试样例：

输入：edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]

输出：7

解释：树的所有节点都是好节点。

解答：dfs一下子树的节点数，然后判断当前节点是不是好节点。这里我就偷懒，直接用HashSet来记录节点数情况了。

class Solution {
    public int countGoodNodes(int[][] _edges) {
        List<Integer>[] edges = new List[_edges.length + 1];
        for (int i = 0; i < edges.length; ++i) {
            edges[i] = new ArrayList<>();
        }
        for (int[] e : _edges) {
            edges[e[0]].add(e[1]);
            edges[e[1]].add(e[0]);
        }
        int[] res = {0};
        dfs(0, -1, edges, res);
        return res[0];
    }

    private int dfs(int cur, int last, List<Integer>[] edges, int[] res) {
        int sum = 0;
        Set<Integer> down = new HashSet<>();
        for (int n : edges[cur]) {
            if (n != last) {
                int tmp = dfs(n, cur, edges, res);
                sum += tmp;
                down.add(tmp);
            }
        }
        if (down.size() <= 1) {
            res[0] += 1;
        }
        return sum + 1;
    }
}

100396. Find the Count of Monotonic Pairs II

给你一个长度为 n 的 正 整数数组 nums 。

如果两个 非负 整数数组 (arr1, arr2) 满足以下条件，我们称它们是 单调 数组对：

• 两个数组的长度都是 n 。
• arr1 是单调 非递减 的，换句话说 arr1[0] <= arr1[1] <= ... <= arr1[n - 1] 。
• arr2 是单调 非递增 的，换句话说 arr2[0] >= arr2[1] >= ... >= arr2[n - 1] 。
• 对于所有的 0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。

请你返回所有 单调 数组对的数目。

由于答案可能很大，请你将它对 10^9 + 7 取余 后返回。

测试样例：

输入：nums = [2,3,2]

输出：4

解释：单调数组对包括：

1. ([0, 1, 1], [2, 2, 1])
2. ([0, 1, 2], [2, 2, 0])
3. ([0, 2, 2], [2, 1, 0])
4. ([1, 2, 2], [1, 1, 0])

解答：第三题和第四题一样，只是范围不同。第四题的范围其实也不大，nums.length <= 1000, 同时nums[i] <= 1000。直接双循环暴力动态规划不会超时。dp[i]，代表arr1 = i的时候，可能的对数。注意这时候还是需要满足arr2的条件的。利用前缀和可以减少搜索空间。

class Solution {
    private static final int mod = 1_000_000_007;

    public int countOfPairs(int[] nums) {
        int[] dp = new int[1001];
        boolean isFirst = true;
        int last = -1;
        for (int n : nums) {
            int[] nextDp = new int[n + 1];
            // 第一个数，无脑给所有可能的情况赋值1
            if (isFirst) {
                for (int i = 0; i <= n; ++i) {
                    nextDp[i] = 1;
                }
            } else {
                int sum = 0, st = 0;
                for (int i = 0; i <= n; ++i) {
                    int curArr2 = n - i;
                    // 需要满足arr2的条件，前缀和可以减少搜索空间。
                    while (st <= Math.min(i, last) && last - st >= curArr2) {
                        sum = (sum + dp[st]) % mod;
                        ++st;
                    }
                    nextDp[i] = sum;
                }
            }
            isFirst = false;
            dp = nextDp;
            last = n;
        }
        int res = 0;
        for (int n : dp) {
            res = (res + n) % mod;
        }
        return res;
    }
}