基础算法之双指针

提前恭喜大家这是基础算法上篇的最后一个内容了，下面我们就将进入下篇的学习

UVA11572 唯一的雪花 Unique Snowflakes

1，题目

2，链接

https://www.luogu.com.cn/problem/UVA11572#idehttps://www.luogu.com.cn/problem/UVA11572#ide

3，解析

同向双指针：

发现：如果两层暴力，其实左右指针是不需要回退的

思考过程

1，初始化

left = 1,right = 1,mp<int,int> mp;//数字，次数

2，进窗口 mp[a[right]]++;

3，判断->出窗口 mp[a[right]]>1->mp[a[left]]--;left++;

4，更新结果 ret = max(ret,right-left+1;

4，代码

#include<iostream> #include<unordered_map> using namespace std; typedef long long ll; const int N = 1e6+8; int main(){ ll t; cin >> t; while(t--){ ll n; cin >> n; ll a[N]; for(ll i = 1;i <= n;i++) cin >> a[i]; unordered_map<ll,ll> mp; ll left = 1,right = 1; ll ret = 0; while(right<=n){ mp[a[right]]++; while(mp[a[right]]>1){ mp[a[left]]--; left++; } ret = max(ret,right-left+1); right++; } cout << ret; } return 0; }

P1638 逛画展

1，题目

2，链接

https://www.luogu.com.cn/problem/P1638#idehttps://www.luogu.com.cn/problem/P1638#ide
3，解析

首先想到暴力枚举：左指针不动，右指针向后移->当区间满足条件时，右指针再向后移一定不是最优解;当左指针向后移时，右指针不需要回退->因为我们已经有了左右区间

->

双指针：

1,进窗口：right后移一位：如果新增字符->记录一下

2,判断：字符个数符合要求，right停止右移，准备出窗口

3,出窗口：left所指位置的次数在哈希表中减1，若1->0记录一下

4,更新结果

4，代码

#include<iostream> using namespace std; const int N = 1e6+9; int a[N]; int n,m; int kind; int mp[N]; int main(){ cin >> n >> m; for(int i = 1;i <= n;i++) cin >> a[i]; int left = 1,right = 1; int ret = n,begin = 1; while(right <= n){ if(mp[a[right]]++ == 0) kind++; while(kind == m){ int len = right-left+1; if(len < ret){ ret = len; begin = left; } if(mp[a[left]]-- == 1) kind--; left++; } right++; } cout << begin <<" "<< begin+ret-1 << endl; return 0; }

字符串

1，题目

2，链接

字符串牛客竞赛是专业的编程比赛和算法训练平台，包括ACM校赛、ICPC、CCPC、信息学奥赛、NOIP、NOI等编程比赛提高训练营。适合初级小白编程入门训练，包含NOIP普及组提高组赛前集训、ACM区域赛前多校训练营。https://ac.nowcoder.com/acm/problem/18386

3，解析

双指针（可以直接练习）

4，代码

#include<iostream> using namespace std; int mp[30]; int kind;//窗口内种类 int main(){ string s; getline(cin,s); int n = s.size(); int ret = n; int left = 0,right = 0; while(right<n){ if(s[right]>='a'&&s[right]<='z'){ if(mp[s[right]-'a']==0) kind++; mp[s[right]-'a']++; } while(kind == 26){ ret = min(ret,right-left+1); if(mp[s[left]-'a']-- == 1) kind--; left++; } right++; } cout << ret << endl; return 0; }

丢手绢

1，题目

2，链接

丢手绢牛客竞赛是专业的编程比赛和算法训练平台，包括ACM校赛、ICPC、CCPC、信息学奥赛、NOIP、NOI等编程比赛提高训练营。适合初级小白编程入门训练，包含NOIP普及组提高组赛前集训、ACM区域赛前多校训练营。https://ac.nowcoder.com/acm/problem/207040

3，解析

圆弧总长sun,最长距离 max{max{k,sum-k}}

4，代码

#include<iostream> using namespace std; typedef long long ll; const ll N = 1e5+8; ll d[N]; ll sum; int main(){ ll n; cin >> n; for(int i = 1;i <= n;i++){ cin >> d[i]; sum += d[i]; } ll k = 0; ll ret = 0; ll left = 1,right = 1; while(right<=n){ k += d[right]; while(k*2>=sum){ ret = max(ret,sum-k); k -= d[left]; left++; } ret = max(ret,k); right++; } cout << ret << endl; return 0; }