# # Leetcode 第300场周赛题解

## # Problem A - 解密消息 (opens new window)

### # 方法一：模拟

• 时间复杂度 $\mathcal{O}(|K|+|M|)$
• 空间复杂度 $\mathcal{O}(|\Sigma|+|M|)$

class Solution:
def decodeMessage(self, key: str, message: str) -> str:
d = dict()
for ki in key:
if 'a' <= ki <= 'z' and ki not in d:
d[ki] = chr(ord('a') + len(d))
return ''.join(d[mi] if 'a' <= mi <= 'z' else mi for mi in message)

1
2
3
4
5
6
7

## # Problem B - 螺旋矩阵 IV (opens new window)

### # 方法一：模拟

• 时间复杂度 $\mathcal{O}(MN)$
• 空间复杂度 $\mathcal{O}(MN)$

class Solution {
public:
vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
vector<vector<int>> ans(m, vector<int>(n, -1));
int l = 0, r = n - 1, u = 0, d = m - 1, i = 0, j = 0;
int dir = 0;

auto chdir = [&]() {
bool moved = false;
while (!moved) {
if (dir == 0) {
if (j + 1 <= r) {
moved = true;
j++;
}
else {
dir = 1;
u++;
}
} else if (dir == 1) {
if (i + 1 <= d) {
moved = true;
i++;
}
else {
dir = 2;
r--;
}
} else if (dir == 2) {
if (j - 1 >= l) {
moved = true;
j--;
}
else {
dir = 3;
l++;
}
} else {
if (i - 1 >= u) {
moved = true;
i--;
}
else {
dir = 0;
d--;
}
}
}
};

chdir();
}

return ans;
}
};

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

## # Problem C - 知道秘密的人数 (opens new window)

### # 方法一：动态规划

• 时间复杂度 $\mathcal{O}(N)$
• 空间复杂度 $\mathcal{O}(N)$

const int MOD = 1e9 + 7;

class Solution {
public:
int peopleAwareOfSecret(int n, int delay, int forget) {
vector<int> dp(n + 1);
dp[1] = 1;
int know = 0;
for (int i = 2; i <= n; ++i) {
if (i - forget >= 1)
know = (know + MOD - dp[i - forget]) % MOD;
if (i - delay >= 1)
know = (know + dp[i - delay]) % MOD;
dp[i] = know;
}

int ans = 0;
for (int i = max(1, n - forget + 1); i <= n; ++i)
ans = (ans + dp[i]) % MOD;

return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

## # Problem D - 网格图中递增路径的数目 (opens new window)

### # 方法一：拓扑排序 + 动态规划

• 时间复杂度 $\mathcal{O}(NM\log(NM))$
• 空间复杂度 $\mathcal{O}(NM)$

const int MOD = 1e9 + 7;
const int d[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

class Solution {
public:
int countPaths(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> dp(n, vector<int>(m));
vector<pair<int, int>> ord(n * m);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
ord[i * m + j] = make_pair(i, j);

sort(ord.begin(), ord.end(), [&](pair<int, int> &a, pair<int, int> &b) {
return grid[a.first][a.second] < grid[b.first][b.second];
});

int ans = 0;
for (auto [i, j] : ord) {
dp[i][j] = (dp[i][j] + 1) % MOD;
for (int k = 0; k < 4; ++k) {
int ni = i + d[k][0], nj = j + d[k][1];
if (ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] > grid[i][j])
dp[ni][nj] = (dp[ni][nj] + dp[i][j]) % MOD;
}
ans = (ans + dp[i][j]) % MOD;
}

return ans;
}
};

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