刷题日记3
2025.1.14
1838. 最高频元素的频数
1838. 最高频元素的频数 - 力扣（LeetCode）
class Solution {
public:
int maxFrequency(vector<int>& nums, int k) {
//排序
//有很多数字，不知道要哪个为基准，遍历，轮流
//r遍历数组，以r为基准看前面的是否能在限制范围内，变成基准数字
//超过总和了，就l遍历，删除前面的
sort(nums.begin(),nums.end());
int l=0,r=0,res=0;
long long sum=0;
while(r<nums.size()){
sum+=nums[r];
//窗口长度*基准>sum+k 太多了，实际总和达不到
while((long long)nums[r]*(r-l+1)>sum+k){
sum-=nums[l];
l++;
}
res=max(res,r-l+1);
r++;
}
return res;
}
};思路：1。有很多数字，不知道以哪个为基准进行变换，那肯定每个都要试，遍历。r进行遍历。2.我们的k不一定能用完，每次使用k后都要更新res,往模板上靠，那么二层循环呢？我们不一定要从头开始和后面的基准对齐，很可能不够，因此，需要排序，需要l在左侧在k不够加的时候减掉前面的。
2516. 每种字符至少取 K 个
2516. 每种字符至少取 K 个 - 力扣（LeetCode）
class Solution {
public:
int takeCharacters(string s, int k) {
//先统计a,b,c的个数，不到2个的直接return -1
//r遍历，再次计数a,b,c 的值，如果>规定值,(num-k)，l遍历消减
int l=0,r=0,res=0,num[3]={0};
int cnta=0,cntb=0,cntc=0;
for(int i=0;i<s.size();i++)num[s[i]-'a']++;
for(int i=0;i<3;i++){
if(num[i]<k) return -1;
num[i]-=k;
}
while(r<s.size()){
if(s[r]=='a')cnta++;
else if(s[r]=='b')cntb++;
else cntc++;
while(cnta>num[0]||cntb>num[1]||cntc>num[2]){
if(s[l]=='a')cnta--;
else if(s[l]=='b')cntb--;
else cntc--;
l++;
}
res=max(res,r-l+1);
r++;
}
return s.size()-res;
}
};思考：1。先统计a.b.c的个数，不到k的话直接return -1。
2。r遍历，统计a,b,c的个数，个数如果超过规定值（统计值－k），进入二层while，l遍历，消减值。
3。更新最长的长度，return 字符串长度-res。
2831. 找出最长等值子数组
2831. 找出最长等值子数组 - 力扣（LeetCode）
class Solution {
public:
int longestEqualSubarray(vector<int>& nums, int k) {
//直接在原数组上进行滑窗不行，可以用数组分别统计不同值的坐标
//然后在不同数组上进行滑窗
vector<vector<int>>vecs(nums.size()+1);//值从1开始
for(int i=0;i<nums.size();i++){
int x=nums[i];
vecs[x].push_back(i);
}
int res=0;
for(auto& vec:vecs){
int l=0,r=0;
while(r<vec.size()){
//当超过能删除的目标值时，l开始遍历
while(vec[r]-vec[l]-(r-l)>k){
l++;
}
res=max(res,r-l+1);//最长相同子数组长度
r++;
}
}
return res;
}
};思考：1。直接在原数组上进行滑窗不行，没有思路。
2。可以用不同数组统计出不同的值的数组坐标，然后在相应的统计数组中，进行滑窗。
3。vec[r]-vec[l]+1－(r-l+1)是需要删除的长度。前者是原数组中相同值的长度（中间可能包括其他值），后者是相同值的个数。如果两者之差>k，l开始遍历。
2024.1.16
209. 长度最小的子数组
209. 长度最小的子数组 - 力扣（LeetCode）
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int l=0,r=0,sum=0,res=nums.size()+1;
while(r<nums.size()){
sum+=nums[r];
while(sum>=target){
res=min(res,r-l+1);
sum-=nums[l];
l++;
}
r++;
}
if(res==nums.size()+1) return 0;
else return res;
}
};思考：我不是太理解，这个算法的时间复杂度。