滑动窗口 + 算法复习
维护一个满足条件的窗口大小,然后进行双指针移动
1.最长子串
题目链接:1.最长子串 - 蓝桥云课
#include<bits/stdc++.h>
#define int long long
using namespace std;
string s;
int k;
signed main()
{
int max_len=0,left=0;
cin>>s>>k;
unordered_map<char,int>nums; //滑动窗口双指针
for(int right=0; right<s.size(); right++)
{
nums[s[right]]++;
while(nums[s[right]]>k) //如果某个字符的频率超过了 k,则缩小窗口
{
nums[s[left]]--;
left++;
}
max_len=max(max_len,right-left+1);
}
cout<<max_len<<endl;
return 0;
}
2.满足条件的子串个数
题目链接:6.满足条件的子串个数 - 蓝桥云课
#include<bits/stdc++.h>
#define int long long
using namespace std;
string s;
int k;
signed main()
{
int sum=0,left=0;
cin>>s>>k;
unordered_map<char,int>nums; //滑动窗口双指针
for(int right=0; right<s.size(); right++)
{
nums[s[right]]++;
while(nums[s[right]]>k) //如果某个字符的频率超过了 k,则缩小窗口
{
nums[s[left]]--;
left++;
}
sum+=(right-left+1); //以新right新形成的好串的数量
// abc
// a a 1
// ab b ab 2
// abc c bc abc 3
}
cout<<sum<<endl;
return 0;
}
3.区间平均值
题目链接:0区间平均值 - 蓝桥云课
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
signed main()
{
cin>>t;
while(t--)
{
int n,k;
int x[110],sum[110];
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x[i];
sum[i]=sum[i-1]+x[i];
}
cin>>k;
while(k--)
{
int l,r;
cin>>l>>r;
printf("%.2f\n",1.0*(sum[r]-sum[l-1])/(r-l+1));
}
}
return 0;
}