Leetcode - 周赛410

目录
一，3248. 矩阵中的蛇
二，3249. 统计好节点的数目
三，3250. 单调数组对的数目 I
dfs影象化
dfs影象化1：1改递推
四，3251. 单调数组对的数目 II

---

一，3248. 矩阵中的蛇

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

1. class Solution {
2.     public int finalPositionOfSnake(int n, List<String> commands) {
3.         int i = 0, j = 0;
4.         for(String x : commands){
5.             if("UP".equals(x)){
6.                 i--;
7.             }else if("RIGHT".equals(x)){
8.                 j++;
9.             }else if("DOWN".equals(x)){
10.                 i++;
11.             }else if("LEFT".equals(x)){
12.                 j--;
13.             }
14.         }
15.         return (i * n) + j;
16.     }
17. }

复制代码

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

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

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

1. class Solution {
2.     public int countGoodNodes(int[][] edges) {
3.         int n = edges.length + 1;
4.         List<Integer>[] g = new ArrayList[n];
5.         Arrays.setAll(g, e->new ArrayList<>());
6.         for(int[] e : edges){
7.             g[e[0]].add(e[1]);
8.             g[e[1]].add(e[0]);
9.         }
10.         dfs(0, -1, g);
11.         return ans;
12.     }
13.     int ans = 0;
14.     int dfs(int x, int fa, List<Integer>[] g){
15.         int t = -1;
16.         boolean flg = true;
17.         int sum = 1;
18.         for(int y : g[x]){
19.             if(y != fa){//防止遍历已经遍历过的节点
20.                 int size = dfs(y, x, g) + 1;//记录x的子树节点是数量
21.                 sum += size;
22.                
23.                 //判断x的子树节点数量是否相同
24.                 if(t == -1) t = size;
25.                 else if(t != size) flg = false;
26.             }
27.         }
28.         if(flg) ans++;//如果相同，加一
29.         return sum;
30.     }
31. }

复制代码

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

dfs影象化

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

1. class Solution {
2.     int MOD = (int)1e9 + 7;
3.     public int countOfPairs(int[] nums) {
4.         memo = new int[nums.length][51];
5.         for(int i=0; i<nums.length; i++)
6.             Arrays.fill(memo[i], -1);
7.         int ans = 0;
8.         for(int x=0; x<=nums[0]; x++){
9.             ans = (ans + dfs(1, x, nums))%MOD;
10.         }
11.         return ans;
12.     }
13.     int[][] memo;
14.     int dfs(int i, int x, int[] nums){
15.         if(i == nums.length) return 1;
16.         if(memo[i][x] != -1) return memo[i][x];
17.         int res = 0;
18.         int y = nums[i-1] - x;
19.         //y >= nums[i] - j <= arr2数组是递减的
20.         //nums[i-1] - x >= nums[i] - j
21.         //j >= nums[i] - nums[i-1] + x
22.         //j >= x <= arr1数组是递增的
23.         for(int j=Math.max(x, nums[i] - nums[i-1] + x); j<=nums[i]; j++){
24.             res = (res + dfs(i+1, j, nums)) % MOD;
25.         }
26.         return memo[i][x] = res;
27.     }
28. }

复制代码

dfs影象化1：1改递推

1. class Solution {
2.     int MOD = (int)1e9 + 7;
3.     public int countOfPairs(int[] nums) {
4.         int n = nums.length;
5.         int[][] f = new int[n+1][51];
6.         Arrays.fill(f[n], 1);
7.         for(int i=n-1; i>0; i--){
8.             for(int x=0; x<=nums[i]; x++){
9.                 int y = nums[i-1] - x;
10.                 int res = 0;
11.                 for(int j=Math.max(x, nums[i] - nums[i-1] + x); j<=nums[i]; j++){
12.                     res = (res + f[i+1][j]) % MOD;
13.                 }
14.                 f[i][x] = res;
15.             }
16.         }
17.         int ans = 0;
18.         for(int x=0; x<=nums[0]; x++){
19.             ans = (ans + f[1][x])%MOD;
20.         }
21.         return ans;
22.     }
23. }

复制代码

对比

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

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

 
代码如下：

1. class Solution {
2.     int MOD = (int)1e9 + 7;
3.     public int countOfPairs(int[] nums) {
4.         int n = nums.length;
5.         int[][] f = new int[n+1][1001];
6.         Arrays.fill(f[n], 1);
7.         for(int i=n-1; i>0; i--){
8.             int[] s = new int[nums[i]+1];
9.             s[0] = f[i+1][0];
10.             for(int j=1; j<=nums[i]; j++)
11.                 s[j] = (s[j-1] + f[i+1][j])%MOD;
12.             for(int x=0; x<=nums[i]; x++){
13.                 int y = nums[i-1] - x;
14.                 //int res = 0;
15.                 // for(int j=Math.max(x, nums[i] - nums[i-1] + x); j<=nums[i]; j++){
16.                 //     res = (res + f[i+1][j]) % MOD;
17.                 // }
18.                 int t = Math.max(x, nums[i] - nums[i-1] + x)-1;
19.                 int res = (s[nums[i]] - (t>=0 && t <= nums[i] ? s[t] : 0) + MOD)%MOD;
20.                 f[i][x] = res;
21.             }
22.         }
23.         int ans = 0;
24.         for(int x=0; x<=nums[0]; x++){
25.             ans = (ans + f[1][x])%MOD;
26.         }
27.         return ans;
28.     }
29. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。