作者：
指针不指南吗
专栏：
Acwing 蓝桥集训每日一题
🐾或许会很慢，但是不可以停下🐾
1.字符串删减
给定一个由 n 个小写字母构成的字符串。
现在，需要删掉其中的一些字母，使得字符串中不存在
连续
三个或三个以上的
x
。请问，最少需要删掉多少个字母？
如果字符串本来就不存在
连续的
三个或三个以上
x
，则无需删掉任何字母。
输入格式
第一行包含整数 n。
第二行包含一个长度为 n 的由小写字母构成的字符串。
输出格式
输出最少需要删掉的字母个数。
数据范围
3≤n≤100
输入样例1:
6 xxxiii
输出样例1：
1
输入样例2：
5 xxoxx
输出样例2：
0
输入样例3：
10 xxxxxxxxxx
输出样例3：
8
方法一
-
思路
枚举 i ，遇到
x
,进入循环计
x
的个数，超过 2 个，答案
ans++
-
代码实现
#include<bits/stdc++.h> using namespace std; int main() { int n; string s; cin>>n>>s; //读入数据 int cnt=0,ans=0; for(int i=0;i<n;i++){ while(s[i]=='x'){ //如果是 x 进入循环 cnt++; // x 在该循环中出现的个数 if(cnt>2) ans++; //ans累加 i++; //循环控制变量 } cnt=0; //进入下次循环之前，进行置零操作 } cout<<ans; return 0; }
方法二——双指针算法
-
思路
输出单词那道题很像
枚举 i 表示全是
x
区间的开头，j 表示
x
区间的最后，即 j 的下一个不是
x
,满足条件的答案 ans 累加
-
代码实践
#include<bits/stdc++.h> using namespace std; int main() { int n; string s; cin>>n>>s; int i=0,j=0,ans=0; for(int i=0;i<n;i++){ if(s[i]=='x') { // i 表示 x 区间的最左端开头 j=i; while(j<n&&s[j]=='x') j++; // j 表示 x 区间的最右端结尾 ans+=max(0,j-i-2); //j-i-2拆分：j-i+1(区间长度)-1(跳出循环之前多加了1)-2(题中条件从第三个开始数) i=j; // 令i 跳过这段已经计算过的区间，寻找下一个 } } cout<<ans; return 0; }
2.最长连续不重复子序列
给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数（均在 0∼105 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤105
输入样例：
5 1 2 2 3 5
输出样例：
3
-
思路
枚举 i 表示区间右端点的指针 , j 表示区间左端点的指针，
利用区间内数字出现的个数，来判断是否满足条件；
i 向前走一步，a [ i ] 所表示的数出现的次数多一次，用 s 数组把数字出现的次数存起来；
j 从 0 开始走，如果在 i 走的过程中 s [ a [ i ] ] > 1，则说明 i 现在表示的数与之前的重复了，
让 j 往前走，区间挤出去一个数，先 s [ a [ j ] ] –，再 j ++, 直到把重复的数挤出去，即 s [ a [ i ] ] <= 1;
i 每走一步，判断一下区间大小，是否做出最大值 res 更新；
-
代码实现
#include<bits/stdc++.h> using namespace std; const int N=100010; int n; int a[N],s[N]; //a表示原整数序列，s 表示区间内数字出现的次数 int main() { cin>>n; for(int i=0;i<n;i++) cin>>a[i]; //读入数据 int res=0,i=0,j=0; //res 表示最大的区间大小 for(i=0;i<n;i++){ s[a[i]]++; //i前进，区间内a[i]的出现次数增加 while(s[a[i]]>1){ //若出现重复元素则进入循环 s[a[j]]--; //j前进，a[j]出现次数减少一次 j++; } res=max(res,i-j+1); //更新最大值 } cout<<res; return 0; }
3.数组元素的目标和
给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。
数组下标从 0 开始。
请你求出满足 A[i]+B[j]=x 的数对 (i,j)。
数据保证有唯一解。
输入格式
第一行包含三个整数 n,m,x，分别表示 A 的长度，B 的长度以及目标值 x。
第二行包含 n 个整数，表示数组 A。
第三行包含 m 个整数，表示数组 B。
输出格式
共一行，包含两个整数 i 和 j。
数据范围
数组长度不超过 105。
同一数组内元素各不相同。
1≤数组元素≤109
输入样例：
4 5 6 1 2 4 7 3 4 6 8 9
输出样例：
1 1 -
思路
先想暴力做法
for(int i=0;i<n;i++) for(int j=m-1;j>=0;j--) if(a[i]+b[j]==k) cout<<i<<' '<<j<<endl;利用单调性优化后
枚举 i 从小到大，j 从大到小，找到 j 满足条件 a[i]+b[j]>k,说明符合题意的一定在 此时i的右边，j的左边
-
代码实现
#include<bits/stdc++.h> using namespace std; const int N=100010; int a[N],b[N]; int n,m,k; int main() { cin>>n>>m>>k; for(int i=0;i<n;i++) cin>>a[i]; for(int j=0;j<m;j++) cin>>b[j]; for(int i=0,j=m-1;i<n;i++){ //i从小到大枚举 while(j>=0&&a[i]+b[j]>k) j--; //j 从大到小 ，答案在i的右边，在j的左边 if(a[i]+b[j]==k){ cout<<i<<' '<<j<<endl; } } return 0; }