dsfds' blog

学海无涯，回头是岸

0%

『leetcode』周赛 300

发表于 更新于 分类于 Valine：

周赛链接在此：第 300 场周赛 - 力扣（LeetCode）。

简单记录下 T2~T4 的答案。

螺旋矩阵IV

T2 from:3 to:10view raw
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
44
45
class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> ret(m, vector<int>(n, -1));
        int state = 0;
        int r = 0;
        int c = 0;
        ret[r][c] = head->val;
        head = head->next;
        while (head != nullptr) {
            if (state == 0) {
                if (c == n - 1 || ret[r][c+1] > -1) {
                    state = 1;
                    r++;
                } else {
                    c++;
                }
            } else if (state == 1) {
                if (r == m - 1 || ret[r+1][c] > -1) {
                    state = 2;
                    c--;
                } else {
                    r++;
                }
            } else if (state == 2) {
                if (c == 0 || ret[r][c-1] > -1) {
                    state = 3;
                    r--;
                } else {
                    c--;
                }
            } else {
                if (r == 0 || ret[r-1][c] > -1) {
                    state = 0;
                    c++;
                } else {
                    r--;
                }
            }
            ret[r][c] = head->val;
            head = head->next;
        }
        return ret;
    }
};

知道秘密的人数

T3view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        vector<long long> dp(n+1, 0);
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            // dp[i] = dp[i-1];
            // if (i > forget) dp[i] -= dp[i-forget];
            for (int j = delay; j < forget && i - j >= 1; j++)
                dp[i] += dp[i-j];
            dp[i] %= 1000000007;
        }
        long long res = 0;
        for (int i = n; i >= 1 && i > n - forget; --i)
            res = (res + dp[i]) % 1000000007;
        return res;
    }
};

网格图中递增路径的数目

T4view raw
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
class Solution {
public:
    long long mod = 1000000007;
    int xy[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int countPaths(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<long long>> dp(m, vector<long long>(n, 1));
        
        vector<vector<int>> vis(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j)
                dfs(i, j, vis, dp, grid);
        }
        
        long long res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                res += dp[i][j];
                res %= mod;
            }
        }
        return res;
    }
    
    long long dfs(int i , int j, vector<vector<int>>& vis, vector<vector<long long>>& dp, vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        if (vis[i][j] == 1) return dp[i][j];
        for (int k = 0; k < 4; ++k) {
            int nx = i + xy[k][0];
            int ny = j + xy[k][1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[i][j] > grid[nx][ny])
                dp[i][j] += dfs(nx, ny, vis, dp, grid);
            dp[i][j] %= mod;
        }
        vis[i][j] = 1;
        return dp[i][j];
    }
};