力扣周赛
力扣周赛
第200场周赛
5475.统计好三元组
leetcode
给你一个整数数组 arr ，以及 a、b 、c 三个整数。请你统计其中好三元组的数量。
如果三元组 (arr[i], arr[j], arr[k]) 满足下列全部条件，则认为它是一个 好三元组 。1
2
3
4
50 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c
其中 |x| 表示 x 的绝对值。
返回 好三元组的数量 。
解题思路
- 暴力就完事了,在
i < j < k统计满足条件的次数1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
int n = arr.size();
int cnt = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
for (int k = j + 1; k < n; ++k) {
if (abs(arr[i] - arr[j]) <= a &&
abs(arr[j] - arr[k]) <= b &&
abs(arr[i] - arr[k]) <= c)
cnt++;
}
}
}
return cnt;
}
5476.找出数组游戏的赢家
leetcode
给你一个由 不同 整数组成的整数数组 arr 和一个整数 k 。
每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的胜利并保留在位置 0 ，较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的 赢家 。
返回赢得比赛的整数。
题目数据 保证 游戏存在赢家。
示例：
1 | |
解题思路
- 取第一个数为当前值，统计当前值之后有多少个数小于它，如果正好有k个就返回它
- 一旦后面有一个数大于当前值，就重新更新次数和当前值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15int getWinner(vector<int>& arr, int k) {
int num = arr[0];
int cnt = 0;
for (int i = 1; i < arr.size(); ++i) {
if (num > arr[i]) {
cnt++;
} else {
num = arr[i];
cnt = 1;
}
if (cnt == k) break;
}
return num;
} - 双向队列模拟操作
- 先判断如果k值过大，可以直接返回数组中的最大值
- 定义一个记录每个数连胜次数的cnt数组
- 每次操作先取出队列的第一个数作为当前值，如果此时的队列头部元素小于当前值就pop出push到尾部
当前值得连胜记录cnt++,如果满足k就返回当前值 - 如果队列头部元素大于当前值，就将当前值push到队尾，同时将头部元素的连胜记录更新为1，更新当前元素。
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
26int getWinner(vector<int>& arr, int k) {
if (k > arr.size()) {
sort(arr.begin(), arr.end());
return arr[arr.size() - 1];
}
deque<int> que;
que.assign(arr.begin(), arr.end());
int cur = que.front();
int* cnt = (int*)malloc(sizeof(int) * 1000000);
memset(cnt, 0, sizeof(int) * 1000000);
while (1) {
que.pop_front();
while (cur > que.front()) {
++cnt[cur];
if (cnt[cur] == k) return cur;
que.push_back(que.front());
que.pop_front();
}
que.push_back(cur);
cnt[que.front()] = 1;
cur = que.front();
if (k == 1) return cur;
}
return -1;
}
5477.排布二进制网格的最少交换次数
leetcode
给你一个 n x n 的二进制网格 grid，每一次操作中，你可以选择网格的 相邻两行 进行交换。
一个符合要求的网格需要满足主对角线以上的格子全部都是 0 。
请你返回使网格满足要求的最少操作次数，如果无法使网格符合要求，请你返回 -1 。
主对角线指的是从 (1, 1) 到 (n, n) 的这些格子。
示例
1 | |
解题思路
- 统计行末尾连续出现0的次数，然后进行排序，从上到下每行至少应该满足
col - 1 - i个0 - 然后使用贪心思想来模拟交换的过程，统计需要交换行的次数
- 遍历每行，检查当前行末尾0个数是否满足条件，满足就跳过
- 如果不满足，就从当前行以下找满足条件的行的下标。如果找到了就开始往上交换，顺便统计次数，如果发现遍历到最后一行都没有发现满足条件的就返回-1没有找到。
1 | |
