本题链接:7.子串简写 - 蓝桥云课 (lanqiao.cn)
方法一:前缀和
用一个c数组记录当前位置c1的个数,只要找到c2,看c2是否>= k ,如果大于就看他的前面有多少个c1就是有多少个串,即res += c[i - k + 1],
注意:
- res要开long long
- strlen(s + 1)必须要另外赋值,否则多次计算会扣点
- 因为使用到了前缀和,str应该从1开始存储,cin >> str + 1,和 strlen(str + 1)
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int k;
const int N = 500010;
char str[N];
char a, b;
long long res = 0;
int c[N];
int main() {
cin >> k >> (str + 1) >> a >> b;
int l = strlen(str + 1);
for (int i = 1; i <= l; i++) {
if (str[i] == a) c[i] ++;
c[i] += c[i - 1];
if (i >= k && str[i] == b)
res += c[i - k + 1];
}
cout << res;
return 0;
}
方法二:滑动窗口
滑动窗口理解:
两个指针,一个begin,一个end,都 = 0,然后end往后走,自己一直自加,直到满足/不满足条件时(根据check函数设计),进行处理,然后begin+1,之后end再往后走,重复。
int begin = 0,end = 0;
while(end > n){
while(check(begin,end)){
操作...
begin++;
}
end++;
}
代码:
#include <bits/stdc++.h>
using namespace std;
int K;
long long ans=0,c1_sum=0;
string S;
char c1,c2;
int main(){
cin>>K>>S>>c1>>c2;
for(int i=K-1,j=0;i<S.length();i++,j++){
if(S[j]==c1) c1_sum++;
if(S[i]==c2) ans+=c1_sum;
}
cout<<ans;
return 0;
}
不过我感觉这题不太适合滑动窗口,有点难理解。以下是其他滑动窗口练习题:
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int len = nums.size();
if(len == 0) return 0;
int begin = 0,end = 0,sum = 0,ans = 1000010;
while(end < len){
sum += nums[end];
while(sum >= target){
ans = min(ans,end - begin + 1);
sum -= nums[begin];
begin++;
}
end++;
}
if(ans == 1000010) return 0;
else return ans;
}
};
以上是本文全部内容,如果对你有帮助点个赞再走吧~ ₍˄·͈༝·͈˄*₎◞ ̑̑