当前位置：首页 > news >正文

Leetcode - 周赛410

news 来源：原创 2024/9/19 22:13:30

一，3248. 矩阵中的蛇

二，3249. 统计好节点的数目

三，3250. 单调数组对的数目 I

dfs记忆化

dfs记忆化1：1改递推

四，3251. 单调数组对的数目 II

一，3248. 矩阵中的蛇

本题就是一道纯模拟题，只需要模拟蛇移动后的下标（i，j），最终返回 i * n + j，代码如下：

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

二，3249. 统计好节点的数目

本题就是一道关于树的问题，画个图理解一下：

可以使用dfs从下往上不断求出每颗子树的节点数，同时判断对于每一个节点，它的子树的节点数是否相同，相同加一，求出答案。

代码如下：

class Solution {public int countGoodNodes(int[][] edges) {int n = edges.length + 1;List<Integer>[] g = new ArrayList[n];Arrays.setAll(g, e->new ArrayList<>());for(int[] e : edges){g[e[0]].add(e[1]);g[e[1]].add(e[0]);}dfs(0, -1, g);return ans;}int ans = 0;int dfs(int x, int fa, List<Integer>[] g){int t = -1;boolean flg = true;int sum = 1;for(int y : g[x]){if(y != fa){//防止遍历已经遍历过的节点int size = dfs(y, x, g) + 1;//记录x的子树节点是数量sum += size;//判断x的子树节点数量是否相同if(t == -1) t = size;else if(t != size) flg = false;}}if(flg) ans++;//如果相同，加一return sum;}
}

三，3250. 单调数组对的数目 I

dfs记忆化

此时我们需要定义dfs，首先一定有一个参数 i 表示下标，同时题目要求arr1数组递增，arr2数组递减，所以我们需要知道arr1，arr2数组的前一个数X，Y，但是题目告诉我们X+Y=nums[i]，所以只需要知道X，Y其中一个就行，这里用的是X。定义dfs(i，X)：arr1[i-1] = X，arr2[i-1] = nums[i-1] - X时，nums数组在 [i，n-1] 所能组成的单调数组对。

代码如下：

class Solution {int MOD = (int)1e9 + 7;public int countOfPairs(int[] nums) {memo = new int[nums.length][51];for(int i=0; i<nums.length; i++)Arrays.fill(memo[i], -1);int ans = 0;for(int x=0; x<=nums[0]; x++){ans = (ans + dfs(1, x, nums))%MOD; }return ans;}int[][] memo;int dfs(int i, int x, int[] nums){if(i == nums.length) return 1;if(memo[i][x] != -1) return memo[i][x];int res = 0;int y = nums[i-1] - x;//y >= nums[i] - j <= arr2数组是递减的//nums[i-1] - x >= nums[i] - j//j >= nums[i] - nums[i-1] + x//j >= x <= arr1数组是递增的for(int j=Math.max(x, nums[i] - nums[i-1] + x); j<=nums[i]; j++){res = (res + dfs(i+1, j, nums)) % MOD;}return memo[i][x] = res;}
}

dfs记忆化1：1改递推

class Solution {int MOD = (int)1e9 + 7;public int countOfPairs(int[] nums) {int n = nums.length;int[][] f = new int[n+1][51];Arrays.fill(f[n], 1);for(int i=n-1; i>0; i--){for(int x=0; x<=nums[i]; x++){int y = nums[i-1] - x;int res = 0;for(int j=Math.max(x, nums[i] - nums[i-1] + x); j<=nums[i]; j++){res = (res + f[i+1][j]) % MOD;}f[i][x] = res;}}int ans = 0;for(int x=0; x<=nums[0]; x++){ans = (ans + f[1][x])%MOD; }return ans;}
}

对比

四，3251. 单调数组对的数目 II

本题和上一题一样，只不过范围变大了，所以需要进一步优化：

代码如下：

class Solution {int MOD = (int)1e9 + 7;public int countOfPairs(int[] nums) {int n = nums.length;int[][] f = new int[n+1][1001];Arrays.fill(f[n], 1);for(int i=n-1; i>0; i--){int[] s = new int[nums[i]+1];s[0] = f[i+1][0];for(int j=1; j<=nums[i]; j++)s[j] = (s[j-1] + f[i+1][j])%MOD;for(int x=0; x<=nums[i]; x++){int y = nums[i-1] - x;//int res = 0;// for(int j=Math.max(x, nums[i] - nums[i-1] + x); j<=nums[i]; j++){//     res = (res + f[i+1][j]) % MOD;// }int t = Math.max(x, nums[i] - nums[i-1] + x)-1;int res = (s[nums[i]] - (t>=0 && t <= nums[i] ? s[t] : 0) + MOD)%MOD;f[i][x] = res;}}int ans = 0;for(int x=0; x<=nums[0]; x++){ans = (ans + f[1][x])%MOD; }return ans;}
}