双指针问题5（c++）

概念

双指针，顾名思义，就是用两个指针解决问题。

有些问题用单指针会出现超时等问题，这时就需要用到双指针

双指针由两个指针组成，一般是左右指针，或前后指针

通过两个指针配合变化，用更短的时间高效解决问题

题目

（续上一篇，如需了解上一篇题目，请移步主页观看）

合并有序数组

#include <bits/stdc++.h> #define ll long long using namespace std; int la,lb,lab; int a[20010],b[10010]; int main() { cin>>la; for(int i = 1;i<=la;i++) { cin>>a[i]; } cin>>lb; for(int i = 1;i<=lb;i++) { cin>>b[i]; } lab = la+lb; int ai = la+1,bi = lb+1,abi = lab+1; while(ai>1&&bi>1) { if(a[ai-1]>b[bi-1]) a[--abi] = a[--ai]; else a[--abi] = b[--bi]; } while(bi>1) a[--abi] = b[--bi]; for(int i = 1;i<=lab;i++) cout<<a[i]<<" "; return 0; }

完美数列

#include <bits/stdc++.h> #define ll long long using namespace std; int n,p; int a[10010]; int main() { cin>>n>>p; for(int i = 1;i<=n;i++) { cin>>a[i]; } sort(a+1,a+n+1); int fast = 0,slow = 1; int ma,mi; mi = a[slow]; int mama = -999999999; while(fast<n) { while(fast<n) { ma = a[++fast]; int x = mi*p; if(ma<=x) mama = max(mama,fast-slow+1); else break; } while(slow<fast) { mi = a[++slow]; int x = mi*p; if(ma<=x) { mama = max(mama,fast-slow+1); break; } } } cout<<mama; return 0; }

反转元音字母

#include <bits/stdc++.h> #define ll long long using namespace std; string a; char yy[] = {'a','e','i','o','u'}; int main() { cin>>a; int n = a.size(); int l = 0,r = n-1; while(l<r) { bool lf = false; bool rf = false; for(int i = 0;i<5;i++) { if(a[l]==yy[i]) lf = true; if(a[r]==yy[i]) rf = true; } if(lf==false) l++; if(rf==false) r--; if(lf==true&&rf==true) { swap(a[l],a[r]); l++; r--; } } cout<<a; return 0; }

验证回文串2

#include <bits/stdc++.h> #define ll long long using namespace std; string a; int n; bool chushi(); bool hou(int,int); int main() { cin>>a; n = a.size(); if(chushi()==true) cout<<"true"; else cout<<"false"; return 0; } bool chushi() { int l = 0,r = n-1; while(l<r) { if(a[l]==a[r]) l++,r--; else { if((hou(l+1,r)|hou(l,r-1))==true) return true; else return false; } } return true; } bool hou(int l,int r) { while(l<r) { if(a[l]==a[r]) l++,r--; else return false; } return true; }

最接近的三数之和

#include <bits/stdc++.h> #define ll long long using namespace std; int n,a[10010],target,misum,micha; int main() { micha = 999999999; cin>>n; for(int i = 1;i<=n;i++) { cin>>a[i]; } cin>>target; sort(a+1,a+n+1); for(int i = 1;i<=n-2;i++) { int l = i+1,r = n; while(l<r) { int sum = a[l]+a[i]+a[r]; int cha = sum-target; if(cha<0) cha = target-sum,l++; else r--; if(cha<micha) { micha = cha; misum = sum; } } } cout<<misum; return 0; }

三数之和的多种可能

#include <bits/stdc++.h> #define ll long long using namespace std; int n,a[10010],target; int cnt; int main() { cin>>n; for(int i = 1;i<=n;i++) { cin>>a[i]; } cin>>target; sort(a+1,a+n+1); for(int i = 1;i<=n-2;i++) { int l = i+1; int r = n; while(l<r) { int sum = a[i]+a[l]+a[r]; if(sum==target) { cnt++; // cout<<cnt<<" "<<i<<" "<<l<<" "<<r<<" "<<a[i]<<" "<<a[l]<<" "<<a[r]<<endl; int p = r-1; while(a[p]==a[r]&&p>l) { cnt++; p--; // cout<<cnt<<" "<<i<<" "<<l<<" "<<p<<" "<<a[i]<<" "<<a[l]<<" "<<a[p]<<endl; } l++; } if(sum>target) r--; if(sum<target) l++; } } cout<<cnt; return 0; }