欢迎大家加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
解释：单调数组对包括：
- ([0, 1, 1], [2, 2, 1])
- ([0, 1, 2], [2, 2, 0])
- ([0, 2, 2], [2, 1, 0])
- ([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;
}
}