第 334 场周赛
Date: 2023-02-26
A 左右元素和的差值
直接暴力
复杂度分析
- 时间复杂度:
- 空间复杂度:
B 找出字符串的可整除数组
根据模数的性质,
复杂度分析
- 时间复杂度:
- 空间复杂度:
C 求出最多标记下标
首先对所有数字排个序,然后考虑到最终答案不会超过
而答案又具有二分性质,因此我们可以先二分一个答案
更进一步的,可以直接简化为从
复杂度分析
- 时间复杂度:
。 - 空间复杂度:
。
本题也有
复杂度分析
- 时间复杂度:
。 - 空间复杂度:
。
D 在网格图中访问一个格子的最少时间
比较裸的 dij 模版题,特殊点是需要计算一下奇偶性。
(赛后 rejudge 寄了,因为没有特判起点,例如:[[0,1,99],[3,99,99],[4,5,6]]
)
正确的做法是直接在一开始就特判起点。
class Solution {
public:
using TP = tuple<int, int, int>;
int minimumTime(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
if (grid[0][1] > 1 && grid[1][0] > 1) {
return -1;
}
vector<vector<int>> d(n, vector<int>(m, -1));
priority_queue<TP, vector<TP>, greater<TP>> q;
d[0][0] = 0;
q.push(make_tuple(0, 0, 0));
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
while(q.size()) {
auto [dis, x, y] = q.top();q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0], ny = y + dir[i][1];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (d[nx][ny] != -1) continue;
if (grid[nx][ny] <= d[x][y] + 1) {
d[nx][ny] = d[x][y] + 1;
q.push(make_tuple(d[nx][ny], nx, ny));
} else {
d[nx][ny] = d[x][y] + 1 + (grid[nx][ny] - (d[x][y] + 1)) + (grid[nx][ny] - (d[x][y] + 1)) % 2;
q.push(make_tuple(d[nx][ny], nx, ny));
}
}
}
return d[n - 1][m - 1];
}
};
复杂度分析
- 时间复杂度:
- 空间复杂度: