leetcode第300场周赛:逆向思维的思想

  |  

摘要: 本文是 leetcode 第 300 周赛的记录。主要涉及的算法包括哈希表、模拟、逆向思维、动态规划。

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


总览

这是 leetcode 第 300 场周赛,本场比赛由蔚来赞助,前 1000 名可获得简历内推,力度还是很大的。

本场比赛主要涉及到的算法是哈希表、模拟、逆向思维、动态规划。这次的题目相对比较简单,其中第 3 题算是比较有亮点,考察了逆向思维。第 4 题如果对动态规划比较熟的话,可以秒做。成绩如下:

4 道题涉及到的算法点,以及参考链接如下:

周赛历史记录: 【连载】leetcode周赛


A题

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

  1. 使用 key 中 26 个英文小写字母第一次出现的顺序作为替换表中的字母 顺序 。
  2. 将替换表与普通英文字母表对齐,形成对照表。
  3. 按照对照表 替换 message 中的每个字母。
  4. 空格 ‘ ‘ 保持不变。

例如,key = “happy boy”(实际的加密密钥会包含字母表中每个字母 至少一次),据此,可以得到部分对照表(’h’ -> ‘a’、’a’ -> ‘b’、’p’ -> ‘c’、’y’ -> ‘d’、’b’ -> ‘e’、’o’ -> ‘f’)。

返回解密后的消息。

1
2
3
4
5
6
提示:
26 <= key.length <= 2000
key 由小写英文字母及 ' ' 组成
key 包含英文字母表中每个字符('a' 到 'z')至少一次
1 <= message.length <= 2000
message 由小写英文字母和 ' ' 组成

示例 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 的数组,下标分别代表 a ~ z 这 26 个小写字母,数组的值表示对应的解密后的字母。遍历 key 的每个字符,如果该字符在数组中没有更新过,则更新,否则就跳过。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
string decodeMessage(string key, string message) {
vector<char> mapping(26, '#');
char i = 'a';
for(const char &ch: key)
{
if(ch == ' ')
continue;
if(mapping[ch - 'a'] != '#')
continue;
mapping[ch - 'a'] = i++;
}
string result = message;
int n = result.size();
for(int i = 0; i < n; ++i)
{
if(message[i] == ' ')
continue;
result[i] = mapping[message[i] - 'a'];
}
return result;
}
};

B题

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

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

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

返回生成的矩阵。

1
2
3
4
5
提示:
1 <= m, n <= 1e5
1 <= m * n <= 1e5
链表中节点数目在范围 [1, m * n] 内
0 <= Node.val <= 1000

示例 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 填充。

算法: 模拟

本题是螺旋矩阵这个系列的题目,要按要求进行打印,属于模拟题。

打印过程是从外到内一圈一圈进行的,对于某一圈打印的过程,横纵坐标的最大值最小值是用于判断边界关键信息。当一圈打印结束,需要更新横纵坐标的最大值最小值这个关键信息。

代码(C++)

dx 和 dy 中各个数值的顺序需要注意,代码中的顺序正好是向右,向下,向左,向上这个顺序,当判断出界需要该方向的时候,直接 d++ 就可以了,详见代码。

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
class Solution {
public:
vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
vector<vector<int>> result(m, vector<int>(n, -1));
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
// 范围
int up = 0, down = m - 1, left = 0, right = n - 1;
int d = 0;
int x = 0, y = 0;
ListNode *node = head;
while(node != nullptr)
{
result[x][y] = node -> val;
if(x + dx[d] == up && y + dy[d] == left)
{
d = 0;
++up;
--down;
++left;
--right;
}
else if(x + dx[d] < up || x + dx[d] > down || y + dy[d] < left || y + dy[d] > right)
{
d++;
}
x = x + dx[d];
y = y + dy[d];
node = node -> next;
}
return result;
}
};

C题

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

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

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

1
2
3
提示:
2 <= n <= 1000
1 <= delay < forget <= n

示例 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 个新的人。(六个人知道秘密)

算法: 逆向思维

一个人如果在第 x 天知道秘密,则第 [x + delay, x + forgot - 1] 天这个范围此人会分享该秘密。

如果采用逆向思维,那么在第 i 天时,第 [i - delay, i - forgot + 1] 天知道的人会在当前的第 i 天分享,同时第 i - forgot 天知道秘密的人会在当前的第 i 天忘掉。

这样的话,我们就可以知道第 i 天这一天会增加多少新知道秘密的人,这个数再加上第 1 ~ i-1 天知道秘密且尚未忘记的人数,即为第 i 天时知道秘密的人数。

第 1 天,有一个人知道。

从第二天开始,[2, n] 中的每一天我们都判断一次有多少人在这一天发生分享。

假设当前进行到第 i 天,我们只需要判断 [i - delay, i - forgot + 1] 中的每一天各有多少新增知道的人即可,这些数目的总和就是当天新知道秘密的人数。同时,i - forget 这一天知道秘密的人会遗忘,因此人数要清空。

代码(C++)

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
class Solution {
public:
int peopleAwareOfSecret(int n, int delay, int forget) {
const int MOD = 1e9 + 7;
using ll = long long;
vector<int> additional(n);
additional[0] = 1;
for(int i = 1; i < n; ++i)
{
if(i - forget >= 0)
additional[i - forget] = 0;
int left = i - forget + 1;
int right = i - delay;
if(right < 0)
continue;
for(int j = max(left, 0); j <= right; ++j)
{
additional[i] = ((ll)additional[i] + additional[j]) % MOD;
}
}

int ans = 0;
for(int x: additional)
ans = ((ll)ans + x) % MOD;
return ans;
}
};

D题

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

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

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

1
2
3
4
5
6
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 1e5
1 <= grid[i][j] <= 1e5

示例 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 。

算法: 动态规划

本题的思路与 329. 矩阵中的最长递增路径 几乎一样,都是在矩阵中找递增路径,那个题是求最长的递增路径,本题是求递增路径个数。

对矩阵中的每一个位置,我们求一次以该位置结尾的递增路径有多少条,将所有位置的结果加起来就得到最终的递增路径条数。

对于任意位置,首先它自己构成一个长度为 1 的递增路径。然后就要看四个方向中有没有比该位置的值小的,如果有,则可以从对应的方向走到当前位置形成递增路径。

综上,动态规划算法那如下:

1
2
3
4
5
6
7
8
9
10
11
12
状态定义:
dp[i][j] := 以 (i, j) 为结尾的递增路径条数。

答案:
sum(dp)

初始化:
如果四个方向都没有比当前元素值小的,则 dp[i][j] = 1

状态转移:
dp[i][j] = 1 + sum(dp[x][y])
其中 (x, y) 是 (i, j) 的相邻点,且 grid[x][y] < grid[i][j]

代码(C++)

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 countPaths(vector<vector<int>>& grid) {
n = grid.size();
m = grid[0].size();
// dp[i][j] := 以 (i, j) 为终点的严格递增路径条数
dp = vector<vector<int>>(n, vector<int>(m, -1));
int ans = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
ans = ((ll)ans + dfs(i, j, grid)) % MOD;
return ans;
}

int n, m;
vector<vector<int>> dp;
using ll = long long;
const int MOD = 1e9 + 7;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int dfs(int i, int j, const vector<vector<int>>& grid)
{
if(dp[i][j] != -1)
return dp[i][j];
dp[i][j] = 1;
for(int d = 0; d < 4; ++d)
{
int x = i + dx[d];
int y = j + dy[d];
if(x < 0 || x >= n || y < 0 || y >= m)
continue;
if(grid[x][y] >= grid[i][j])
continue;
dp[i][j] = ((ll)dp[i][j] + dfs(x, y, grid)) % MOD;
}
return dp[i][j];
}
};

Share