LeetCode周赛301

发表于 | 分类于 |
字数统计: 809 | 阅读时长 ≈ 3

前言

开一个新坑，记录一下每周的周赛情况
把每周不会的题尽可能地补一下 作为补充
锻炼思维的同时，提升写代码的速度和准度

C. 知道秘密的人数

链接: https://leetcode.cn/problems/number-of-people-aware-of-a-secret/

题意

在第 1 天，有一个人发现了一个秘密。
给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。
给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 109 + 7 取余 后返回。

解法

比赛的时候当天赶时间，甚至第三题都没做出来
签了两题就溜了
晚上睡觉的时候一直在想到底是哪里出了问题
用一个remb数组记录第i天有多少人开始传播，fort数组记录第i天有多少人忘记秘密
spread记录当天可以传播秘密的人数，num表示当天知道秘密的人
然后维护一下各个值就好了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef long long ll;
class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        vector<ll> remb(2020), fort(2020);
        long long num = 1, spread = 0, mod = 1e9 + 7;
        remb[1 + delay] = 1;
        fort[1 + forget] = 1;
        for (int i = 2; i <= n; i++) {
            spread += remb[i] % mod;
            spread -= fort[i] % mod;
            num += spread % mod;
            num -= fort[i] % mod;
            remb[i + delay] = spread;
            fort[i + forget] = spread;
        }
        return num % mod;
    }
};

D. 网格图中递增路径的数目

链接: https://leetcode.cn/problems/number-of-increasing-paths-in-a-grid/

题意

给你一个 m x n 的整数网格图 grid ，你可以从一个格子移动到 4 个方向相邻的任意一个格子。

请你返回在网格图中从 任意 格子出发，达到 任意 格子，且路径中的数字是 严格递增 的路径数目。由于答案可能会很大，请将结果对 1e9 + 7 取余 后返回。

解法

周赛的时候看这题
好像不难 但没什么感觉 没做出来
赛后发现就一个dfs 记忆化一下就可以

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
typedef long long ll;
class Solution {
public:
    vector<vector<ll>> dp;
    ll mod = 1e9 + 7;
    ll dfs(int x, int y, vector<vector<int>>& grid) {
        int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
        int m = grid.size(), n = grid[0].size();
        if (dp[x][y]) return dp[x][y];
        ll temp = 1;
        for (int i = 0; i < 4; i++) {
            int px = x + dx[i], py = y + dy[i];
            if (px >= 0 && px < m && py >= 0 && py < n) {
                if (grid[px][py] > grid[x][y]) {
                    temp += dfs(px, py, grid);
                    temp %= mod;
                }
            }
        }
        return dp[x][y] = temp;
    }
    int countPaths(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        ll ans = 0;
        dp.resize(m);
        for (auto &item: dp) {
            item.resize(n);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!dp[i][j]) {
                    ans += dfs(i, j, grid);
                }
                else {
                    ans += dp[i][j];
                    ans %= mod;
                }
            }
        }
        return ans;

    }
};