永康网站建设公司,数学很差能学计算机吗,网站建设外包注意事项,seo优化对网店的推广的作用为题目列表
3248. 矩阵中的蛇
3249. 统计好节点的数目
3250. 单调数组对的数目 I
3251. 单调数组对的数目 II
一、矩阵中的蛇 只要按照题目要求模拟即可#xff0c;代码如下
class Solution {
public:int finalPositionOfSnake(int n, vectorstring commands…题目列表
3248. 矩阵中的蛇
3249. 统计好节点的数目
3250. 单调数组对的数目 I
3251. 单调数组对的数目 II
一、矩阵中的蛇 只要按照题目要求模拟即可代码如下
class Solution {
public:int finalPositionOfSnake(int n, vectorstring 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(vectorvectorint edges) {int n edges.size() 1;// 建树vectorvectorint 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 相关的语句就是一个求树的结点个数的代码functionint(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(vectorint nums) {int n nums.size(), m ranges::max(nums);vectorvectorint f(n, vectorint(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(vectorint nums) {int n nums.size(), m ranges::max(nums);vectorvectorint f(n, vectorint(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;}
};
