第一次参加了周赛，侥幸碰到了比较简单的一场，离大佬们还有很大差距，以后尽量每周都来写写代码。每次打完比赛后都分享一下自己的思路吧，很可能不是最优的思路，还希望谅解。
找出转圈游戏输家
题目链接：6430. 找出转圈游戏输家
思路：模拟题，题目说任意玩家第二次接到球游戏就结束，于是可以创一个set来表存历史位置，如果当前位置已经出现过，游戏结束。开始寻找未出现在set中的位置。
时间复杂度：$$O(n)$$
空间复杂度：$$O(n)$$
代码：
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
|
class Solution {
public:
vector<int> circularGameLosers(int n, int k) {
unordered_set<int> get_ball;
int pos = 0;
int round = 1;
auto next_pos = [&](int pos) {
return (pos + round * k) % n;
};
get_ball.insert(0);
while (true) {
pos = next_pos(pos);
if (get_ball.count(pos)) {
break;
}
get_ball.insert(pos);
round++;
}
vector<int> ans;
for (int i = 0; i < n; i++) {
if (!get_ball.count(i))
ans.emplace_back(i + 1);
}
return ans;
}
};
|
相邻值的按位异或
题目链接：6431. 相邻值的按位异或
思路：这道题反而是最后来看的，因为我对位运算或者数字规律有点不太行，后续得加强一下。这道题拿到在纸上画了画，异或比较常用的性质是：
$$a⊕b=c$$
$$a⊕c=b$$
$$b⊕c=a$$
然而这道题用不上这个，我一开始画了画发现算不出来，于是往找规律上面靠。我们可以发现其实中间的数字是无所谓的，因为异或是“同0异1”，对于中间的数字我们总是可以构造出来符合的数字。我们可以假设原数组第一个数字是0，通过derived的值可以知道0和1的翻转情况，比如derived[0]是1，说明第二个数字和第一个不相同，那么原数组第二个数字就是1，以此类推，遍历数组。最后看我们得到的原数组的最后一个数字和第一个数字的值是否满足derived[n - 1]，如果满足则可以构建，不满足则无法构建。
时间复杂度：$$O(n)$$
空间复杂度：$$O(1)$$
代码：
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
bool doesValidArrayExist(vector<int>& derived) {
int n = derived.size();
bool last = (accumulate(derived.begin(), derived.end(), 0) - derived[n - 1]) % 2;
if (derived[n - 1] == 0) {
return !last;
} else {
return last;
}
}
};
|
矩阵中移动的最大次数
题目链接：6433. 矩阵中移动的最大次数
思路：下意识写了个搜索，发现过不了，于是加上记忆化，即保存历史走过当前点的步数，如果现在走到那一格的步数还没有之前高就不继续了，还是超时。于是放弃搜索，开始动规。结果发现这道题就是常规的动规，先走列，再走行，中途还可以利用上之前说到的记忆化及时剪枝。
时间复杂度：$$O(n)$$
空间复杂度：$$O(n)$$
代码：
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
|
class Solution {
public:
int ans;
int m, n;
vector<vector<int>> dp;
const vector<pair<int, int>> direction = {
{-1, 1},
{0, 1},
{1, 1},
};
inline bool valid(int x, int y) {
return (x >= 0 && x < m && y >= 0 && y < n);
}
int maxMoves(vector<vector<int>>& grid) {
ans = 0;
m = grid.size();
n = grid[0].size();
dp.resize(m, vector<int>(n, 0));
for (int j = 0; j < n - 1; j++) {
for (int i = 0; i < m; i++) {
if (j != 0 && dp[i][j] == 0)
continue;
for (auto [dx, dy] : direction) {
int x = i + dx;
int y = j + dy;
if (valid(x, y) && grid[x][y] > grid[i][j]) {
dp[x][y] = max(dp[x][y], dp[i][j] + 1);
ans = max(ans, dp[x][y]);
}
}
}
}
return ans;
}
};
|
统计完全连通分量的数量
题目链接：6432. 统计完全连通分量的数量
思路：先把整个图的连通分量找出来，保存起来。然后检查每个连通分量中的点的边数是否等于连通分量点的个数，如果都相等则是完全连通分量。
时间复杂度：$$O(n)$$
空间复杂度：$$O(n)$$
代码：
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
|
class Solution {
public:
int countCompleteComponents(int n, vector<vector<int>>& edges) {
vector<vector<int>> graph(n);
for (auto edge : edges) {
graph[edge[0]].emplace_back(edge[1]);
graph[edge[1]].emplace_back(edge[0]);
}
vector<bool> visited(n, false);
int ans = 0;
vector<vector<int>> components;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
vector<int> component;
queue<int> q;
q.push(i);
component.emplace_back(i);
visited[i] = true;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto next : graph[cur]) {
if (!visited[next]) {
q.push(next);
visited[next] = true;
component.emplace_back(next);
}
}
}
components.emplace_back(component);
}
}
for (auto component : components) {
bool is_complete = true;
for (auto node : component) {
if (graph[node].size() != component.size() - 1) {
is_complete = false;
break;
}
}
if (is_complete) {
ans++;
}
}
return ans;
}
};
|