题目列表
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;}
};