leetcode weekly contest 331
leetcode weekly contest 331
后面两题还算是不错的题目。
2558. 从数量最多的堆取走礼物
给你一个整数数组 gifts ，表示各堆礼物的数量。每一秒，你需要执行以下操作：
- 选择礼物数量最多的那一堆。
- 如果不止一堆都符合礼物数量最多，从中选择任一堆即可。
- 选中的那一堆留下平方根数量的礼物（向下取整），取走其他的礼物。
返回在 k 秒后剩下的礼物数量。
示例 1：
1 | |
示例 2：
1 | |
提示：
1 <= gifts.length <= 1031 <= gifts[i] <= 1091 <= k <= 103
地址
https://leetcode.cn/contest/weekly-contest-330/problems/count-distinct-numbers-on-board/
题意
堆
思路
- 简单题目直接模拟即可，每次从堆中取出最大的元素 $x$，然后将 $\sqrt{x}$ 放入队列，重复 $k$ 次后，我们求队列中所有元素的和；
- 复杂度分析：
- 时间复杂度：$O(n + k \log n)$，其中 $n$ 为数组的长度，$k$ 为取出的次数。
- 空间复杂度：$O(n)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
long long pickGifts(vector<int>& gifts, int k) {
priority_queue<int, vector<int>, less<int>> pq;
for (auto v : gifts) {
pq.emplace(v);
}
long long res = 0;
for (int i = 0; i < k; i++) {
int x = pq.top();
pq.pop();
pq.emplace(sqrt(x));
}
while (!pq.empty()) {
res += pq.top();
pq.pop();
}
return res;
}
};
2559. 统计范围内的元音字符串数
给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。
每个查询 queries[i] = [li, ri] 会要求我们统计在 words 中下标在 li 到 ri 范围内（包含 这两个值）并且以元音开头和结尾的字符串的数目。
返回一个整数数组，其中数组的第 i 个元素对应第 i 个查询的答案。
注意：元音字母是 'a'、'e'、'i'、'o' 和 'u' 。
示例 1：
1 | |
示例 2：
1 | |
提示：
1 <= words.length <= 1051 <= words[i].length <= 40words[i]仅由小写英文字母组成sum(words[i].length) <= 3 * 1051 <= queries.length <= 1050 <= queries[j][0] <= queries[j][1] < words.length
地址
https://leetcode.cn/contest/biweekly-contest-96/problems/minimum-operations-to-make-array-equal-ii/
题意
前缀和
思路
- 我们直接统计前 $i$ 个字符中的元音字符统计次数的前缀和，此时查询时 $[l,r]$ 时，我们直接利用前缀和 $presum[r] - presum[l-1]$ 即可求得区间 $[l,r]$ 内的元音字母统计次数。
- 复杂度分析：
- 时间复杂度：$O(n)$，其中 $n$ 为数组的长度。
- 空间复杂度：$O(1)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
int n = words.size();
vector<int> arr(n);
unordered_set<char> cnt({'a', 'e', 'i', 'o', 'u'});
for (int i = 0; i < n; i++) {
if (cnt.count(words[i][0]) && cnt.count(words[i].back())) {
arr[i] = 1;
}
}
vector<int> presum(n + 1);
for (int i = 0; i < n; i++) {
presum[i + 1] = presum[i] + arr[i];
}
vector<int> res;
for (auto v : queries) {
int l = v[0], r = v[1];
res.emplace_back(presum[r + 1] - presum[l]);
}
return res;
}
};
2560. 打家劫舍 IV
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。
另给你一个整数数组 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。
返回小偷的 最小 窃取能力。
示例 1：
1 | |
示例 2：
1 | |
提示：
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= k <= (nums.length + 1)/2
地址
https://leetcode.cn/contest/weekly-contest-331/problems/house-robber-iv/
题意
二分查找、贪心
思路
- 题目本身比较简单，根据题目的提示即可知道本题需要用到二分查找 $1 \le nums[i] \le 10^9$。此时我们二分枚举可能的最小值 $x$。我们如何检测 $x$ 合法？由于题目只要求不能抢劫相邻的房屋，此时我们只需要依次从左向右取数据即可，若要保证每次取时间隔大于 $1$，我们应当尽可能的取左侧的数据，只需要保证每次取时相邻的数据间隔大于 $1$ 即可。
- 复杂度分析
- 时间复杂度：时间复杂度为 $O(n \log U)$，$n$ 表示数组的长度，$U$ 表示数组中最大的数字。
- 空间复杂度：时间复杂度为 $O(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
25class Solution {
public:
int minCapability(vector<int>& nums, int k) {
int n = nums.size();
int l = 0, r = *max_element(nums.begin(), nums.end());
int res = 0;
while (l <= r) {
int mid = l + (r - l) / 2;
int pre = -2, tot = 0;
for (int i = 0; i < n; i++) {
if (nums[i] <= mid && i - pre > 1) {
pre = i;
tot++;
}
}
if (tot >= k) {
res = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return res;
}
};
2561. 重排水果
你有两个果篮，每个果篮中有 n 个水果。给你两个下标从 0 开始的整数数组 basket1 和 basket2 ，用以表示两个果篮中每个水果的成本。
你希望两个果篮相等。为此，可以根据需要多次执行下述操作：
- 选中两个下标
i和j，并交换basket1中的第i个水果和basket2中的第j个水果。 - 交换的成本是
min(basket1i,basket2j)。
根据果篮中水果的成本进行排序，如果排序后结果完全相同，则认为两个果篮相等。
返回使两个果篮相等的最小交换成本，如果无法使两个果篮相等，则返回 -1 。
示例 1：
1 | |
示例 2：
1 | |
提示：
basket1.length == bakste2.length1 <= basket1.length <= 1051 <= basket1i,basket2i <= 109
地址
https://leetcode.cn/contest/weekly-contest-331/problems/rearranging-fruits/
题意
思维题目 + 贪心
思路
- 本身替换的思路确实难了一些，首先我们自然而然的想到，将两个数组中相同的元素全部剔除掉，相同的元素则不用交换，我们只交换不同的元素。我们假设将 $basket1$ 中相同的元素剔除掉后剩余的元素组成的数组为 $arr1$，将 $basket2$ 中相同的元素剔除掉后剩余的元素组成的数组为 $arr2$，此时我们知道一定包含下面的处理:
- 两个数组的长度一定相等，如果不相等无论如何都无法完成交换相等；
- 两个数组的长度一定都是偶数，且其中每个元素出现的次数都为偶数次，为什么每个元素出现的次数都为偶数次，因为我们假设交换了 $(x,y), x \neq y$，此时 $arr1$ 中多了一个 $y$ 少了一个 $x$，此时 $arr2$ 中多了一个 $x$ 少了一个 $y$，此时交换之前的 $arr1$ 一定至少含有 $2$ 个 $x$，交换之前的 $arr2$ 一定至少含有 $2$ 个 $y$，否则两个数组仍然不相等，交换则没有任何意义；
- 假设 $arr1$ 的数组长度为 $m$，则我们此时最多只需要交换 $\frac{m}{2}$ 次即可，每次交换时我们尽量取两个数组中剩余元素较小的值进行交换；
- 假设 $a$ 为两个数组中都已经共有的元素，此时如果要交换 $(x,y)$，我们可以将 $arr1$ 中的 $x$ 与 $arr2$ 中的 $a$ 交换，将 $arr1$ 中的 $a$ 与 $arr2$ 中的 $y$ 交换，这样交换的代价则为 $2a$；
- 综上我们每次交换时要么选择二者已经拥有的共同元素的最小值的元素 $minVal$ 交换两次，代价为 $2 * minVal$；要么选择二者非共同元素的最小值进行交换，交换的代价为 $\min(arr1, arr2)$；
- 每次交换完成后 $(x,y)$ 则为两个数组共同拥有的元素，此时我们可以同时更新 $minVal$；
- 复杂度分析：
- 时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度。
- 空间复杂度：$O(n)$。
代码
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74class Solution {
public:
bool check(vector<int> &arr) {
if (arr.size() % 2) {
return false;
}
for (int i = 0; i < arr.size(); i += 2) {
if (arr[i] != arr[i + 1]) {
return false;
}
}
return true;
}
long long minCost(vector<int>& basket1, vector<int>& basket2) {
sort(basket1.begin(), basket1.end());
sort(basket2.begin(), basket2.end());
int n = basket1.size();
vector<int> arr1, arr2;
vector<int> arr;
int i = 0, j = 0;
while(i < n && j < n) {
if (basket1[i] == basket2[j]) {
arr.emplace_back(basket1[i]);
i++, j++;
} else if (basket1[i] < basket2[j]) {
arr1.emplace_back(basket1[i]);
i++;
} else {
arr2.emplace_back(basket2[j]);
j++;
}
}
while (i < n) {
arr1.emplace_back(basket1[i++]);
}
while (j < n) {
arr2.emplace_back(basket2[j++]);
}
if (arr1.size() != arr2.size()) {
return -1;
}
if (!check(arr1) || !check(arr2)) {
return -1;
}
long long ans = 0;
int minVal = max(basket1[n - 1], basket2[n - 1]);
if (arr.size() > 0) {
minVal = min(arr[0], minVal);
}
int l1 = 0, l2 = 0;
int m = arr1.size() / 2;
for (int i = 0; i < m; i++) {
if (arr1[l1] < arr2[l2]) {
if (2 * minVal < arr1[l1]) {
ans += 2 * minVal;
} else {
ans += arr1[l1];
}
minVal = min(minVal, arr1[l1]);
l1 += 2;
} else {
if (2 * minVal < arr2[l2]) {
ans += 2 * minVal;
} else {
ans += arr2[l2];
}
minVal = min(minVal, arr2[l2]);
l2 += 2;
}
}
return ans;
}
};
欢迎关注和打赏，感谢支持！
- 关注我的博客: http://whistle-wind.com/
- 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
- 关注我的微信公众号: 公务程序猿
leetcode weekly contest 331
http://example.com/2026/09/08/力扣周赛题解/99/