【蓝桥集训】第四天——双指针

  • Post author:
  • Post category:其他


作者:

指针不指南吗


专栏:

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;
    }
    

    Alt



版权声明:本文为qq_73659829原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。