第 300 场周赛
文章目录- 解密消息
- 螺旋矩阵 IV
- 知道秘密的人数
- 网格图中递增路径的数目
题目
思路
- 模拟，打标记即可。
代码
class Solution {
public:
string decodeMessage(string key, string message) {
string res = "";
int n = key.size();
bool st[26] = {0};
map mp;
int now = 0;
for (int i = 0; i < n; i++) {
if(key[i] == ' ') continue;
if(!st[key[i] - 'a']) {
st[key[i] - 'a'] = true;
mp[key[i]] = now;
now ++;
}
}
for (int i = 0; i < message.size(); i++) {
if(message[i] == ' ') res += ' ';
else {
res += mp[message[i]] + 'a';
}
}
return res;
}
};
螺旋矩阵 IV
题目
思路
- 设定当前方向 n o w now now，（0、1、2、3）对应方向数组 w a l k walk walk。
- 设定上下左右（lx、rx、ly、ry）四个边界，在转向方向的时候进行调整。
代码
class Solution {
public:
vector> spiralMatrix(int m, int n, ListNode* head) {
vector> res(m, vector(n, -1));
ListNode *p = head;
if(p == nullptr) return res;
vector v;
while(p) { v.push_back(p->val); p = p->next; }
int x = 0, y = -1;
int walk[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
int now = 0;
int lx = 0, rx = m - 1, ly = 0, ry = n - 1;
for (int i = 0; i < v.size(); i++) {
int dx = x + walk[now][0], dy = y + walk[now][1];
if(dx > rx || dx < lx || dy > ry || dy < ly) {
if(now == 0) lx += 1;
if(now == 1) ry -= 1;
if(now == 2) rx -= 1;
if(now == 3) ly += 1;
now = (now + 1) % 4;
dx = x + walk[now][0], dy = y + walk[now][1];
}
res[dx][dy] = v[i];
x = dx, y = dy;
}
return res;
}
};
知道秘密的人数
题目
思路
-
一开始想的，就是直接拿个动态数组，模拟删人、加人这个过程。但是时间，空间开销必然很大。
-
对此需要进行优化：
- 发现对于第 i i i 天：当前集合中所有能分享秘密的人（ i > = x + d e l a y i>=x+delay i>=x+delay），加出来的新人，他们的状态（时间都是起始第 i i i 天、delay、forget）全部是一致的。（这里就等价于我们不需要将所有人一个一个都加入，而是直接用一个变量等价替换即可）
- 发现时间是单调递增，参数 d e l a y 、 f o r g e t delay、forget delay、forget 是固定的，那么后来者状态一定晚于前者。
-
这里我用 m a p < i n t , i n t > map
代码
class Solution {
public:
constexpr static int mod = 1e9 + 7;
int peopleAwareOfSecret(int n, int delay, int forget) {
map mp;
int res = 0;
mp[1] = 1;
for (int i = 2; i <= n; i++) {
int cnt = 0;
for (auto &x: mp) {
int a = x.first, b = x.second;
if(i >= a + forget) { mp.erase(a); continue; }
if (i >= a + delay) cnt = (cnt + b) % mod;
}
mp.insert({i, cnt});
}
for (auto &x: mp) res = (res + x.second) % mod;
return res % mod;
}
};
网格图中递增路径的数目
题目
思路
- 记忆化搜素
考虑样例图解
3->4：1
1->3、1->3->4： 2
相邻能抵达，状态转移 d p [ i ] [ j ] = d p [ x ] [ y ] + 1 dp[i][j] = dp[x][y] + 1 dp[i][j]=dp[x][y]+1。
代码
class Solution {
public:
constexpr static int mod = 1e9 + 7;
int n, m;
int walk[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
int dfs(int x, int y, vector>& grid, vector>& dp) {
int s = 0;
for (int i = 0; i < 4; i++) {
int dx = x + walk[i][0];
int dy = y + walk[i][1];
if(dx >= n || dx < 0 || dy >= m || dy < 0) continue;
if(grid[x][y] >= grid[dx][dy]) continue;
if(dp[dx][dy]) { s += dp[dx][dy] + 1; continue; }
s += dfs(dx, dy, grid, dp) + 1;
s %= mod;
}
dp[x][y] = (s + dp[x][y]) % mod;
return dp[x][y];
}
int countPaths(vector>& grid) {
n = grid.size(), m = grid[0].size();
vector> dp(n, vector(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(!dp[i][j]) {
dfs(i, j, grid, dp);
}
}
}
int res = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
res = (res + dp[i][j] + 1) % mod;
return res;
}
};
