题目整体难度不是很大,但是刷掉了很多自认为稳出三题的选手(包括我qwq)
T1,T2比较水,主要靠手速. T3的思路不太好想,但是一旦想通之后实现很简单
T4据说是21年的原题,我没刷到过,看了眼没思路就弃了.
T1 统计字符串
2586. 统计范围内的元音字符串数
给你一个下标从 0 开始的字符串数组 words 和两个整数：left 和 right 。
如果字符串以元音字母开头并以元音字母结尾，那么该字符串就是一个 元音字符串 ，其中元音字母是 'a'、'e'、'i'、'o'、'u' 。
返回 words[i] 是元音字符串的数目，其中 i 在闭区间 [left, right] 内。
示例 1：
输入：words = [“are”,”amy”,”u”], left = 0, right = 2
输出：2
解释：
- “are” 是一个元音字符串，因为它以 ‘a’ 开头并以 ‘e’ 结尾。
- “amy” 不是元音字符串，因为它没有以元音字母结尾。
- “u” 是一个元音字符串，因为它以 ‘u’ 开头并以 ‘u’ 结尾。
在上述范围中的元音字符串数目为 2 。
解法:模拟
很水,一看就能明白而且没什么坑点的T1,4分钟轻松拿下
class Solution {
public:
int vowelStrings(vector<string>& words, int left, int right) {
int count = 0;
int cur = 0;
string a = "aeiou";
for(auto i: words)
{
if(cur>=left&&cur<=right)
{
auto beg = i[0];
auto end = i[i.size()-1];
bool begf = false;
bool endf = false;
for(auto c:a)
{
if(beg == c){
begf = true;
}
if(end==c){
endf = true;
}
}
if(begf&&endf)
count++;
}
cur++;
}
return count;
}
};
T2 重排数组
2587. 重排数组以得到最大前缀分数
给你一个下标从 0 开始的整数数组 nums 。你可以将 nums 中的元素按 任意顺序 重排（包括给定顺序）。
令 prefix 为一个数组，它包含了 nums 重新排列后的前缀和。换句话说，prefix[i] 是 nums 重新排列后下标从 0 到 i 的元素之和。nums 的 分数 是 prefix 数组中正整数的个数。
返回可以得到的最大分数。
示例 1：
输入：nums = [2,-1,0,1,-3,3,-3]
输出：6
解释：数组重排为 nums = [2,3,1,-1,-3,0,-3] 。
prefix = [2,5,6,5,2,2,-1] ，分数为 6 。
可以证明 6 是能够得到的最大分数。
解法:逆推
做过的T2里最简单的,一直在想是不是把题意看漏了,或者数据量太大需要特殊处理,结果直接AC了
数组从小到大排序,累加求后缀和(如果从大到小排序就是前缀和)
统计后缀和为正整数的次数
class Solution {
public:
int maxScore(vector<int>& nums) {
sort(nums.begin(),nums.end());
long long int sum = 0;
int score = 0;
for(int i = nums.size()-1;i>=0;i--)
{
sum+= nums[i];
if(sum>0)
score++;
}
return score;
}
};
T3 美丽子数组
2588. 统计美丽子数组数目
给你一个下标从 0 开始的整数数组nums 。每次操作中，你可以：
- 选择两个满足
0 <= i, j < nums.length的不同下标i和j。 - 选择一个非负整数
k，满足nums[i]和nums[j]在二进制下的第k位（下标编号从 0 开始）是1。 - 将
nums[i]和nums[j]都减去2k。
如果一个子数组内执行上述操作若干次后，该子数组可以变成一个全为 0 的数组，那么我们称它是一个 美丽 的子数组。
请你返回数组 nums 中 美丽子数组 的数目。
子数组是一个数组中一段连续 非空 的元素序列。
示例 1：
输入：nums = [4,3,1,2,4]
输出：2
解释：nums 中有 2 个美丽子数组：[4,3,1,2,4] 和 [4,3,1,2,4] 。
- 按照下述步骤，我们可以将子数组 [3,1,2] 中所有元素变成 0 ：
- 选择 [3, 1, 2] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [1, 1, 0] 。
- 选择 [1, 1, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 0, 0] 。
- 按照下述步骤，我们可以将子数组 [4,3,1,2,4] 中所有元素变成 0 ：
- 选择 [4, 3, 1, 2, 4] 和 k = 2 。将 2 个数字都减去 22 ，子数组变成 [0, 3, 1, 2, 0] 。
- 选择 [0, 3, 1, 2, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 2, 0, 2, 0] 。
- 选择 [0, 2, 0, 2, 0] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [0, 0, 0, 0, 0] 。
解法:异或
一开始想的是直接模拟,做的时候发现计算量太大.于是想到可以用异或和为0的性质来判断是否为美丽子数组,于是构造了一个二重循环来判断每一个子数组是否符合要求
但是题目的数据量是10^6, 两次循环的计算量会达到10^12,必然超时
标准解法是空间换时间, 使用unordered_map来存储每一个异或和出现的次数, 这样只需要循环一次就可以求出所有子数组
#### from Hongrock
class Solution {
public:
long long beautifulSubarrays(vector<int>& nums) {
long long ret = 0;
unordered_map<int, int> cnt;
int s = 0;
cnt[s] = 1;
for(int v : nums){
s ^= v;
ret += cnt[s];
++cnt[s];
}
return ret;
}
};
T4 完成任务的最少时间
2589. 完成所有任务的最少时间
难度困难19
你有一台电脑，它可以 同时 运行无数个任务。给你一个二维整数数组 tasks ，其中 tasks[i] = [starti, endi, durationi] 表示第 i 个任务需要在 闭区间 时间段 [starti, endi] 内运行 durationi 个整数时间点（但不需要连续）。
当电脑需要运行任务时，你可以打开电脑，如果空闲时，你可以将电脑关闭。
请你返回完成所有任务的情况下，电脑最少需要运行多少秒。
示例 1：
输入：tasks = [[2,3,1],[4,5,1],[1,5,2]]
输出：2
解释：
- 第一个任务在闭区间 [2, 2] 运行。
- 第二个任务在闭区间 [5, 5] 运行。
- 第三个任务在闭区间 [2, 2] 和 [5, 5] 运行。
电脑总共运行 2 个整数时间点。
解法 贪心+暴力
知道是贪心,但是想不出来
首先按照右端点排序。
对于 tasks[i] 来说，它右侧的任务要么和它没有交集，要么包含它的区间后缀。
遍历排序后的任务，先统计区间内的已有的电脑运行时间点，如果个数小于duration，则需要新增时间点。根据提示 2，尽量把新增的时间点安排在区间 [start,end],[start,end] 的后缀上，这样下一个区间就能统计到更多已有的时间点。
class Solution {
bool run[2001];
public:
int findMinimumTime(vector<vector<int>> &tasks) {
sort(tasks.begin(), tasks.end(), [](auto &a, auto &b) {
return a[1] < b[1];
});
int ans = 0;
for (auto &t : tasks) {
int start = t[0], end = t[1], d = t[2];
for (int i = start; i <= end; ++i)
d -= run[i]; // 去掉运行中的时间点
for (int i = end; d > 0; --i) // 剩余的 d 填充区间后缀
if (!run[i]) {
run[i] = true;
--d;
++ans;
}
}
return ans;
}
};
