Leetcode - 周赛410
目录一，3248. 矩阵中的蛇
二，3249. 统计好节点的数目
三，3250. 单调数组对的数目 I
dfs影象化
dfs影象化1：1改递推
四，3251. 单调数组对的数目 II
一，3248. 矩阵中的蛇
https://i-blog.csdnimg.cn/direct/fb098923db924345be6d678984cf2b78.png
本题就是一道纯模拟题，只需要模拟蛇移动后的下标（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. 统计好节点的数目
https://i-blog.csdnimg.cn/direct/39f68fbeed8249aea1c83baf6a8a55be.png
本题就是一道关于树的标题，画个图理解一下：
https://i-blog.csdnimg.cn/direct/06907333c4bb4562be272aae7bb052e7.png
可以使用dfs从下往上不停求出每颗子树的节点数，同时判断对于每一个节点，它的子树的节点数是否雷同，雷同加一，求出答案。
代码如下：
class Solution {
public int countGoodNodes(int[][] edges) {
int n = edges.length + 1;
List<Integer>[] g = new ArrayList;
Arrays.setAll(g, e->new ArrayList<>());
for(int[] e : edges){
g].add(e);
g].add(e);
}
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){
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
https://i-blog.csdnimg.cn/direct/188a0cda01d54d8c93b83ce89700e205.png
https://i-blog.csdnimg.cn/direct/9331d5905ee94111af8be8e67040f01d.png
dfs影象化
此时我们需要界说dfs，起首肯定有一个参数 i 表现下标，同时标题要求arr1数组递增，arr2数组递减，所以我们需要知道arr1，arr2数组的前一个数X，Y，但是标题告诉我们X+Y=nums，所以只需要知道X，Y其中一个就行，这里用的是X。界说dfs(i，X)：arr1 = X，arr2 = nums - X时，nums数组在 所能组成的单调数组对。
代码如下：
class Solution {
int MOD = (int)1e9 + 7;
public int countOfPairs(int[] nums) {
memo = new int;
for(int i=0; i<nums.length; i++)
Arrays.fill(memo, -1);
int ans = 0;
for(int x=0; x<=nums; 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 != -1) return memo;
int res = 0;
int y = nums - x;
//y >= nums - j <= arr2数组是递减的
//nums - x >= nums - j
//j >= nums - nums + x
//j >= x <= arr1数组是递增的
for(int j=Math.max(x, nums - nums + x); j<=nums; j++){
res = (res + dfs(i+1, j, nums)) % MOD;
}
return memo = res;
}
} dfs影象化1：1改递推
class Solution {
int MOD = (int)1e9 + 7;
public int countOfPairs(int[] nums) {
int n = nums.length;
int[][] f = new int;
Arrays.fill(f, 1);
for(int i=n-1; i>0; i--){
for(int x=0; x<=nums; x++){
int y = nums - x;
int res = 0;
for(int j=Math.max(x, nums - nums + x); j<=nums; j++){
res = (res + f) % MOD;
}
f = res;
}
}
int ans = 0;
for(int x=0; x<=nums; x++){
ans = (ans + f)%MOD;
}
return ans;
}
} 对比
https://i-blog.csdnimg.cn/direct/c2abdf2ec7d7471c889dd78a944886ab.png
四，3251. 单调数组对的数目 II
https://i-blog.csdnimg.cn/direct/78e44e21eea343b58f20216825b8bfb6.png
本题和上一题一样，只不过范围变大了，所以需要进一步优化：
https://i-blog.csdnimg.cn/direct/b05c4db17a98446cb5938641ddbaa269.png
代码如下：
class Solution {
int MOD = (int)1e9 + 7;
public int countOfPairs(int[] nums) {
int n = nums.length;
int[][] f = new int;
Arrays.fill(f, 1);
for(int i=n-1; i>0; i--){
int[] s = new int+1];
s = f;
for(int j=1; j<=nums; j++)
s = (s + f)%MOD;
for(int x=0; x<=nums; x++){
int y = nums - x;
//int res = 0;
// for(int j=Math.max(x, nums - nums + x); j<=nums; j++){
// res = (res + f) % MOD;
// }
int t = Math.max(x, nums - nums + x)-1;
int res = (s] - (t>=0 && t <= nums ? s : 0) + MOD)%MOD;
f = res;
}
}
int ans = 0;
for(int x=0; x<=nums; x++){
ans = (ans + f)%MOD;
}
return ans;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]