力扣周赛_第300场 - Touale Cula's Blog

力扣周赛_第300场

招式

发布于：2022年7月9日

招力扣周赛第300场

第一题 解密

给你字符串 key 和 message ，分别表示一个加密密钥和一段加密消息。解密 message 的步骤如下：

使用 key 中 26 个英文小写字母第一次出现的顺序作为替换表中的字母 顺序 。
将替换表与普通英文字母表对齐，形成对照表。
按照对照表 替换 message 中的每个字母。
空格 ‘ ‘ 保持不变。
例如，key = “happy boy”（实际的加密密钥会包含字母表中每个字母 至少一次），据此，可以得到部分对照表（’h’ -> ‘a’、’a’ -> ‘b’、’p’ -> ‘c’、’y’ -> ‘d’、’b’ -> ‘e’、’o’ -> ‘f’）。
返回解密后的消息。

1
2
3
4
输入：key = "the quick brown fox jumps over the lazy dog", message = "vkbs bs t suepuv"
输出："this is a secret"
解释：对照表如上图所示。
提取 "the quick brown fox jumps over the lazy dog" 中每个字母的首次出现可以得到替换表。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string decodeMessage(string key, string message) {
        unordered_map<char,char> cmap;
        char current = 'a';
        for(auto k:key){
            if(!cmap.count(k) && k!=' ')cmap[k] = current++;
        }

        string res="";
        for(auto k:message){
            res+= k == ' ' ? k:cmap[k];
        }
        return res;       
    }
};

结果

1
2
3
4
5
6
7
8
9
10
执行用时：
4 ms
, 在所有 C++ 提交中击败了
72.56%
的用户
内存消耗：
6.7 MB
, 在所有 C++ 提交中击败了
67.12%
的用

第二题 螺旋矩阵 IV

给你两个整数：m 和 n ，表示矩阵的维数。

另给你一个整数链表的头节点 head 。

请你生成一个大小为 m x n 的螺旋矩阵，矩阵包含链表中的所有整数。链表中的整数从矩阵 左上角 开始、顺时针 按 螺旋 顺序填充。如果还存在剩余的空格，则用 -1 填充。

返回生成的矩阵。

?

示例 1：

1
2
3
4
5
![](img/2022-07-09-17-24-56.png)
输入：m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
输出：[[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
解释：上图展示了链表中的整数在矩阵中是如何排布的。
注意，矩阵中剩下的空格用 -1 填充。

示例 2：

1
2
3
4
输入：m = 1, n = 4, head = [0,1,2]
输出：[[0,1,2,-1]]
解释：上图展示了链表中的整数在矩阵中是如何从左到右排布的。 
注意，矩阵中剩下的空格用 -1 填充。

解法

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};
        vector<vector<int>> res(m,vector<int>(n,-1));
        int x = 0,y = 0,model = 0;

        while(head){
            res[y][x] = head->val;
            int a = x + dx[model],b = y + dy[model];
            if(a<0 || a>=n || b>=m || b <0 ||res[b][a] != -1) model = (model+1)%4;
            
            x += dx[model];
            y += dy[model];
            head = head->next;
        }
        return res;       
    }
};

结果

1
2
3
4
5
6
7
8
9
10
11
12
执行用时：
196 ms
, 在所有 C++ 提交中击败了
74.75%
的用户
内存消耗：
125 MB
, 在所有 C++ 提交中击败了
25.78%
的用户
通过测试用例：
49 / 49

第三题 知道秘密的人数

在第 1 天，有一个人发现了一个秘密。

给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天 给一个新的人 分享 秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会 忘记 这个秘密。一个人 不能 在忘记秘密那一天及之后的日子里分享秘密。

给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 109 + 7 取余 后返回。

 

示例 1：

1
2
输入：n = 6, delay = 2, forget = 4
输出：5

解释：

1
2
3
4
5
6
第 1 天：假设第一个人叫 A 。（一个人知道秘密）
第 2 天：A 是唯一一个知道秘密的人。（一个人知道秘密）
第 3 天：A 把秘密分享给 B 。（两个人知道秘密）
第 4 天：A 把秘密分享给一个新的人 C 。（三个人知道秘密）
第 5 天：A 忘记了秘密，B 把秘密分享给一个新的人 D 。（三个人知道秘密）
第 6 天：B 把秘密分享给 E，C 把秘密分享给 F 。（五个人知道秘密）

示例 2：

1
2
3
4
5
6
7
输入：n = 4, delay = 1, forget = 3
输出：6
解释：
第 1 天：第一个知道秘密的人为 A 。（一个人知道秘密）
第 2 天：A 把秘密分享给 B 。（两个人知道秘密）
第 3 天：A 和 B 把秘密分享给 2 个新的人 C 和 D 。（四个人知道秘密）
第 4 天：A 忘记了秘密，B、C、D 分别分享给 3 个新的人。（六个人知道秘密）

解法一

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
class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {


        /**
        dp[i][j] 第i天知道了j天秘密
        dp[i][1] = dp[i-1][delay]....+dp[i-1][forget]
        dp[i][j] == dp[i-1][j-1]
        **/


        vector<vector<int>> dp(n+1,vector<int>(n+1,0));
        const int MOD = 1e9+7;
        int res=0;
        dp[1][1]=1;
        //for (int i = 1; i <= n; i ++ ) dp[1][i] = 1;
        for(int i=2;i<=n;i++)
            for(int j = 1;j<=n;j++){
                if(j==1){
                    int current = delay;
                    while(current < forget){
                        dp[i][j] = (dp[i][j] +dp[i-1][current])%MOD;
                        current++;
                    }
                    //cout<<"第"<<i<<"天"<<"知道了"<<j<<"天"<< dp[i][j]<<endl;

                }else{
                    dp[i][j] = dp[i-1][j-1] % MOD;
                    //cout<<"第"<<i<<"天"<<"知道了"<<j<<"天"<< dp[i][j]<<endl;
                }
            }
        for(int i = 1;i<=forget;i++){
            res = (res + dp[n][i]) % MOD;
        }
       
        return res;
    }
};

结果

1
2
3
4
5
6
7
8
9
10
执行用时：
396 ms
, 在所有 C++ 提交中击败了
5.04%
的用户
内存消耗：
138.4 MB
, 在所有 C++ 提交中击败了
5.02%
的用户

优化

修改为前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        vector<vector<int>> dp(n+1,vector<int>(n+1));
        const int MOD = 1e9+7;
        for (int i = 1; i <= forget; i ++ ) dp[1][i] = 1;
        for(int i=2;i<=n;i++)
            for(int j = 1;j<=n;j++){
                if(j==1) dp[i][j] = (dp[i-1][forget-1] - dp[i-1][delay-1])%MOD;
                else dp[i][j] = (dp[i-1][j-1] - dp[i-1][j-2]) % MOD;
                dp[i][j] =  (dp[i][j] + dp[i][j-1]) % MOD;
            }
        return (dp[n][forget] + MOD) % MOD;
    }
};

第四题 网格图中递增路径的数目

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

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

如果两条路径中访问过的格子不是完全相同的，那么它们视为两条不同的路径。

 

示例 1：

1
2
3
4
5
6
7
输入：grid = [[1,1],[3,4]]
输出：8
解释：严格递增路径包括：
- 长度为 1 的路径：[1]，[1]，[3]，[4] 。
- 长度为 2 的路径：[1 -> 3]，[1 -> 4]，[3 -> 4] 。
- 长度为 3 的路径：[1 -> 3 -> 4] 。
路径数目为 4 + 3 + 1 = 8 。

示例 2：

1
2
3
4
5
6
输入：grid = [[1],[2]]
输出：3
解释：严格递增路径包括：
- 长度为 1 的路径：[1]，[2] 。
- 长度为 2 的路径：[1 -> 2] 。
路径数目为 2 + 1 = 3 。

提示：

1
2
3
4
5
m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 105
1 <= grid[i][j] <= 105

解法 记忆搜索

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
class Solution {
public:
    vector<vector<int>> g;
    int visited[1010][1010];
    int n,m;
    const int MOD = 1e9 + 7;

    int dp(int x,int y){
        int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
        if(visited[x][y] != -1) return visited[x][y];

        visited[x][y] = 1;
        for(int i = 0;i < 4;i++){
            int a = x + dx[i],b = y + dy[i];
            if(a >= 0 && a< n && b >= 0 && b < m && g[a][b] > g[x][y])
                visited[x][y] = (visited[x][y] + dp(a,b)) % MOD;
        }
        return visited[x][y];
    }

    int countPaths(vector<vector<int>>& grid) {
        n = grid.size();
        m = grid[0].size();
        g = grid;
        for(int i = 0;i<n;i++)
            for(int j = 0;j<m;j++){
                visited[i][j] = -1;
            }
        
        int res = 0;

        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                res = (res + dp(i,j)) % MOD;
            }
        }
        
        return res;
        
    }
};

结果

1
2
3
4
5
6
7
8
9
10
执行用时：
204 ms
, 在所有 C++ 提交中击败了
84.86%
的用户
内存消耗：
46.8 MB
, 在所有 C++ 提交中击败了
50.50%
的用户

感谢您的观看哦！

本文永久链接是：https://touale.github.io/2022/07/09/%E5%8A%9B%E6%89%A3/%E6%8B%9B%E5%BC%8F_%E5%8A%9B%E6%89%A3%E5%91%A8%E8%B5%9B%E7%AC%AC300%E5%9C%BA/

更新于：2022年7月10日

算法

力扣