LeetCode --- 410周赛

题目列表

3248. 矩阵中的蛇

3249. 统计好节点的数目

3250. 单调数组对的数目 I

3251. 单调数组对的数目 II

一、矩阵中的蛇

只要按照题目要求模拟即可，代码如下

class Solution {
public:int finalPositionOfSnake(int n, vector<string>& commands) {int i = 0, j = 0;for(auto s:commands){switch(s[0]){case 'U': i--; break; // switch 语法：记得加break，不然后面的case语句也会被执行case 'D': i++; break;case 'R': j++; break;case 'L': j--; break;}}return i * n + j;}
};

 二、统计好结点的数目

这题考多叉树的遍历，主要看对递归的理解。计算树中满足其子树结点个数相同的结点个数，本质还是求结点个数，只不过多了一些限制条件，只要在求结点个数的dfs代码中进行修改即可，代码如下

class Solution {
public:int countGoodNodes(vector<vector<int>>& edges) {int n = edges.size() + 1;// 建树vector<vector<int>> g(n);for(auto e:edges){g[e[0]].push_back(e[1]);g[e[1]].push_back(e[0]);}int ans = 0;// 下面的 dfs函数 抛开 flag 相关的语句，就是一个求树的结点个数的代码function<int(int,int)>dfs = [&](int x,int fa)->int{bool flag = true;int pre = -1;int res = 1;for(int y:g[x]){if(y != fa){int sz = dfs(y, x);res += sz;if(pre == -1) pre = sz;else if(flag) flag &= (pre == sz);}}ans += flag;return res;};dfs(0, -1);return ans;}
};

三、单调数组对的数目 I & II

这种算合法方案数的题目，一般都是用动态规划解题 ( 最重要的一点是去尝试定义状态，当然做多了题目会有感觉，具体如何定义状态还要结合题目具体问题具体分析 ) 这题的状态定义如下：

• 状态定义：f[i][j] 表示 第 i 个数为 j 时，有多少个合法的方案数(单调数组对)
• 状态转移方程：f[i][j] = sum(f[i-1][k])，其中 k <= min(j, nums[i-1]) && nums[i] - j <= nums[i-1] - k ，等价于 k <= min(j, nums[i-1], j + nums[i-1] - nums[i])
  表示第 i 个数填 j 时的合法方案由第 i - 1 个数填 k 时的合法方案数之和，其中 k 需要满足题目的要求
• 状态初始化：当 i = 0 时，可以填任何数，都算作一种合法的方案，即 f[0][j] = 1

代码如下

class Solution {const int MOD = 1e9 + 7;
public:int countOfPairs(vector<int>& nums) {int n = nums.size(), m = ranges::max(nums);vector<vector<int>> f(n, vector<int>(m + 1, 1));// f[i][j] 表示 第 i 个数填 j 时，所有可能的方案数// f[0][j] 第 0 个数 可以任意取，都算作一个合法方案，初始化为 1// f[i][j] = sum(f[i-1][k]) // 满足 k <= min(j, nums[i-1]) && nums[i] - j <= nums[i-1] - k// 等价于 k <= min(j, nums[i-1], j + nums[i-1] - nums[i])for(int i = 1; i < n; i++){for(int j = 0; j <= nums[i]; j++){int res = 0;for(int k = 0; k <= min({j, nums[i-1],j + nums[i-1] - nums[i]}); k++){res = (res + f[i-1][k])%MOD;}f[i][j] = res;}}int ans = 0;for(int i = 0; i <= nums.back(); i++)ans = (ans + f[n-1][i])%MOD;return ans;}
};

如何优化？

这里其实显而易见，我们在计算 f[i][j] 时，最内层对 k 的循环遍历，本质就是在求前缀和，我们可以提前预处理得到，这样就能在O(1) 的时间内计算出 f[i][j]，代码如下

class Solution {const int MOD = 1e9 + 7;
public:int countOfPairs(vector<int>& nums) {int n = nums.size(), m = ranges::max(nums);vector<vector<int>> f(n, vector<int>(m + 1, 1));// f[i][j] 表示 第 i 个数为 j 时，所有可能的方案数// f[0][j] 第 0 个数 可以任意取，都算作一个合法方案，初始化为 1// f[i][j] = sum(f[i-1][k]) // 满足 k <= min(j, nums[i-1]) & nums[i] - j <= nums[i-1] - k// 等价于 k <= min(j, nums[i-1], j + nums[i-1] - nums[i])for(int i = 1; i < n; i++){// 预处理前缀和int pre[nums[i-1]+1]; pre[0] = f[i-1][0];for(int j = 1; j <= nums[i-1]; j++){pre[j] = (pre[j-1] + f[i-1][j])%MOD;}for(int j = 0; j <= nums[i]; j++){// int res = 0;// for(int k = 0; k <= min({j, nums[i-1],j + nums[i-1] - nums[i]}); k++){//     res = (res + f[i-1][k])%MOD;// }// f[i][j] = res;int x = min({j, nums[i-1],j + nums[i-1] - nums[i]});if(x < 0) f[i][j] = 0;else f[i][j] = pre[x];}}int ans = 0;for(int i = 0; i <= nums.back(); i++)ans = (ans + f[n-1][i])%MOD;return ans;}
};