leetcode contest 300

题目质量还不错，第三题经典的动态规划，第四题感觉过于简单了。

6108. 解密消息

题目

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

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

示例 1：

输入：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" 中每个字母的首次出现可以得到替换表。

示例 2：

输入：key = "eljuxhpwnyrdgtqkviszcfmabo", message = "zwx hnfx lqantp mnoeius ycgk vcnjrdb"
输出："the five boxing wizards jump quickly"
解释：对照表如上图所示。
提取 "eljuxhpwnyrdgtqkviszcfmabo" 中每个字母的首次出现可以得到替换表。

提示：

• 26 <= key.length <= 2000
• key 由小写英文字母及 ‘ ‘ 组成
• key 包含英文字母表中每个字符（'a' 到 'z'）至少一次
• 1 <= message.length <= 2000
• message 由小写英文字母和 ‘ ‘ 组成

地址

https://leetcode.cn/contest/weekly-contest-300/problems/decode-the-message/

题意

直接遍历

思路

1. 按照题意首先将key中的字典序隐射表，然后将message 中的每个字符映射回来即可。
2. 复杂度分析：

• 时间复杂度：$O(n + m))$, 其中 $n$ 为字符串 key 的长度， m 为字符串 message 的长度。
• 空间复杂度：$O(|\Sigma|)$，字符集的大小为 $26$。

代码

class Solution {
public:
    string decodeMessage(string key, string message) {
        vector<char> dict(26, 0);
        int j = 0;
        for (int i = 0; i < key.size(); i++) {
            if (islower(key[i])) {
                if (dict[key[i] - 'a'] > 0) continue;
                dict[key[i] - 'a'] = j + 'a';
                j++;
            }
        }
        string res;
        for (int i = 0; i < message.size(); i++) {
            if (islower(message[i])) {
                res.push_back(dict[message[i] - 'a']);
            } else {
                res.push_back(message[i]);
            }
        }
        return res;
    }
};

6111. 螺旋矩阵 IV

题目

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

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

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

返回生成的矩阵。

示例 1：

输入：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：

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

提示：

• 1 <= m, n <= 105
• 1 <= m * n <= 105
• 链表中节点数目在范围 [1, m * n] 内
• 0 <= Node.val <= 1000

地址

https://leetcode.cn/contest/weekly-contest-299/problems/count-number-of-ways-to-place-houses/

题意

矩阵层次遍历问题

思路

1. 经典的矩阵按照层次遍历问题，可以参考「54. 螺旋矩阵」相关解法，我们将数组中的值依次按照矩阵的层次遍历，将链表中的每一项按照顺序填写进去即可。
2. 复杂度分析：

• 时间复杂度：$O(m \times n)$，其中 $m,n$ 为矩阵的行数与列数。
• 空间复杂度：$O(1)$。

代码

class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> matrix(m, vector<int>(n, -1));
        int rows = m, columns = n;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        while (left <= right && top <= bottom && head) {
            for (int column = left; column <= right && head; column++) {
                matrix[top][column] = head->val;
                head = head->next;
            }
            for (int row = top + 1; row <= bottom && head; row++) {
                matrix[row][right] = head->val;
                head = head->next;
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left && head; column--) {
                    matrix[bottom][column] = head->val;
                    head = head->next;
                }
                for (int row = bottom; row > top && head; row--) {
                    matrix[row][left] = head->val;
                    head = head->next;
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return matrix;
    }
};

6109. 知道秘密的人数

题目

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

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

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

示例 1：

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

示例 2：

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

提示：

• 2 <= n <= 1000
• 1 <= delay < forget <= n

地址

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

题意

动态规划

思路

1. 这个题目的动态规划比较有意思的，还是稍微不好思考，有多种解法可以满足要求，有多种解法：

• 解法一: 设 $dp[i]$ 标识第 $i$ 天新增的人数，此时我们可以知道第 $i$ 天新增的数目为 $dp[i] = \sum_{j=i-forget+1}^{i-delay}dp[j]$，第 $i$ 天的总人数为 $\sum_{i=n-forget+1}^{n}dp[i]$。用前缀和的解法，可以优化到 $O(n)$ 的时间复杂度。
• 解法二: 设 $dp[i][j]$ 标识当前第 $i$ 天时已经知道消息时长为 $j$ 的人数。此时我们可以知道如下推理：
  $$
  dp[i][j] = dp[i-1][j-1] \
  dp[i][0] = \sum_{k=delay}^{forget} dp[i][k]
  $$
  第 $i-1$ 天且发现秘密为 $j$ 天的为 $dp[i-1][j]$, 当经过一天之后，总共有 $dp[i-1][j]$ 个人发现秘密的时间变为 $j+1$ 天，此时 $dp[i][j+1] = dp[i-1][j$，同时新的传播且发现秘密的人数需要统计所有大于等 $delay$ 的天数即可，此时 $dp[i][0] = \sum_{j=delay-1}^{forget-2}dp[i-1][j]$。

2. 复杂度分析：

• 时间复杂度：$O(n^2)$, $n$ 表示给定的天数，可以优化到 $O(n)$ 的时间复杂度。
• 空间复杂度：$O(n)$，$n$ 表示给定的天数。

代码

• 解法一:

  class Solution { public: int peopleAwareOfSecret(int n, int delay, int forget) { long long mod = 1e9 + 7; long long ans = 0; vector<long long> sum(n + 1); vector<long long> dp(n + 1); dp[1] = 1; sum[1] = 1; for (int i = 2; i <= n; i++) { int start = max(0, i - forget); int end = max(0, i - delay); dp[i] = (sum[end] - sum[start] + mod) % mod; sum[i] = sum[i - 1] + dp[i]; } return (sum[n] - sum[max(0, n - forget)] + mod) % mod; } };

• 解法二:

  class Solution { public: int peopleAwareOfSecret(int n, int delay, int forget) { vector<long long> dp(forget); long long mod = 1e9 + 7; dp[0] = 1; for (int i = 2; i <= n; i++) { for (int j = forget - 1; j >= 1; j--) { dp[j] = dp[j - 1]; } dp[0] = 0; for (int j = delay; j < forget; j++) { dp[0] = (dp[0] + dp[j]) % mod; } } long long ans = 0; for (int i = 0; i < forget; i++) { ans = (ans + dp[i]) % mod; } return ans; } };

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

题目

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

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

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

示例 1：

输入：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：

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

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 1000
• 1 <= m * n <= 105
• 1 <= grid[i][j] <= 105

地址

https://leetcode.cn/contest/weekly-contest-300/problems/number-of-increasing-paths-in-a-grid/

题意

动态规划

思路

1. 非常简单的动态规划，题目要求严格递增，首先我们想到的就是将矩阵中的数字按照大小进行排列，设 $dp[i][j]$ 表示 以 $(i,j)$ 为结尾且严格递增的路径数目，此时我们可以知道如下递推关系:
   $$
   dp[i][j] = (dp[i][j] + dp[i][j-1]) \quad if(grid[i][j] > grid[i][j-1])\
   dp[i][j] = (dp[i][j] + dp[i-1][j]) \quad if(grid[i][j] > grid[i-1][j])\
   dp[i][j] = (dp[i][j] + dp[i][j+1]) \quad if(grid[i][j] > grid[i][j+1])\
   dp[i][j] = (dp[i][j] + dp[i+1][j]) \quad if(grid[i][j] > grid[i+1][j])\
   $$
   由于满足了严格的大小关系，所以所有严格小于 $dp[i][j]$ 的序列数目已经确定。
2. 只需要满足严格递增即可，感觉就非常简单了，不过可以稍微修改一点增加难度，比如非严格递增怎么解决？
3. 复杂度分析：

• 时间复杂度：$m \times n$， $m, n$ 表示矩阵的行数与列数。
• 空间复杂度：$m \times n$, $m, n$ 表示矩阵的行数与列数。

代码

class Solution {
public:
    int countPaths(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        long long mod = 1e9 + 7;
        vector<pair<int,int>> arr;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                arr.emplace_back(grid[i][j], i * n + j);
            }
        }
        sort(arr.begin(), arr.end(), [&](const pair<int,int> a, const pair<int,int> &b) {
            return a.first < b.first;
        });
        int tot = m * n;
        vector<vector<long long>> dp(m, vector<long long>(n, 1));
        int dir[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
        for (int i = 0; i < m * n; i++) {
            int cx = arr[i].second / n;
            int cy = arr[i].second % n;
            for (int j = 0; j < 4; j++) {
                int nx = cx + dir[j][0];
                int ny = cy + dir[j][1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    if (grid[cx][cy] > grid[nx][ny]) {
                        dp[cx][cy] = (dp[cx][cy] + dp[nx][ny]) % mod;
                    }
                }
            }
        }
        long long ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = (ans + dp[i][j]) % mod;
            }
        }
        return ans;
    }
};

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://mikemeng.org/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿