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;
    }
};