一、雙指標演算法兩種常見的問題分類：
（1）對于兩個序列，維護某種次序，比如歸并中合并兩個有序序列的操作
（2）對于一個序列，用兩個指標維護一段區間
二、核心思想：
樸素演算法：
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
//暴力方式：O(n^2)
雙指標演算法：
先寫一個樸素的演算法，尋找 i，j 有沒有單調的關系，利用這些單調的關系，將上面的樸素演算法演算法優化到O(n)
for(i=0,j=0;i<n;i++)
{
while(j<i&&check(i,j)) j++;
//每道題的具體邏輯
//優化到O(n)
}
三、雙指標簡單的應用：
1. 將字串“abc def ghi ”輸出為abc\n def\n ghi
具體實作：
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
char str[1000];
gets(str);
int n=strlen(str);
for(int i=0; i<n; i++)
{
int j=i;
while(i<n && str[j] != ' ') j++;
//這道題的具體邏輯
for(int k=i;k<j;k++) cout<<str[k];
cout<<endl;
i=j;
}
return 0;
2. 給定一個長度為n的整數序列，請找出最長的不包含重復數字的連續子序列，輸出它的長度
//樸素做法：O(n^2)
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++)
if(check(j,i))
{
res=max(res,j-i+1);
}
//雙指標演算法：O(n)
for(int i=0,j=0;i<n;i++)
{
while(j<=i&&check(j,i)) j++;
res=max(res,j-i+1)
}
具體實作：
#include<iostream>
using namespace std;
const int N=100010;
int n;
int a[N],s[N];
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int res=0;
for(int i=0,j=0;i<n;i++)
{
s[a[i]]++;
while(s[a[i]]>1)
{
s[a[j]]--;
j++;
}
res=max(res,i-j+1);
}
cout<<res<<endl;
return 0;
}
查看更多
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/197177.html
標籤：其他
上一篇：高可用負載均衡（hproxy）
下一篇：深度學習工程師能力模型