Pat学习Two pointers总结

1.递增数列寻找和为某一固定值的两个数
暴力求解：

void violentS(vector<int> &a,int target)
{
	int n=a.size();
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			if(a[i]+a[j]==target)
			{
				printf("%d %d",a[i],a[j]);
			 } 
		}
	}
 } 

暴力破解唯一的好处是不需要将数组进行排序；但如果数组是递增的，那么暴力破解不算是一个比较好的方法。

two_pointers方法
如果我们观察一下当a[i]+a[j]等于target的时候，显然a[i+1]+a[j]大于target
a[i]+a[j+1]大于target（假设没有相同的数字），这两种情况其实是可以不需要判断的。

那么如何来改进？
假设ｉ从0到n-1，ｊ从n-1到0
1.当ａ［ｉ］＋ａ［ｊ］＝＝ｔａｒｇｅｔ的时候，显然单纯ｉ＋＋或者ｊ＋＋是已知大于ｔａｒｇｅｔ，那么只有ｉ＋＋，ｊ－－；大小是不确定的
2.当ａ［ｉ］＋ａ［ｊ］＞ｔａｒｇｅｔ时候，ｊ－－；
3.当ａ［ｉ］＋ａ［ｊ］＜ｔａｒｇｅｒ时候．ｉ＋＋
结束条件，i>=j时

void TwpPoniters_first(vector<int>a,int i,int j,int target)
 {
 	while(i<j)
 	{
 		if(a[i]+a[j]==target)
 		{
 			printf("%d %d\n",a[i],a[j]);
 			i++;j--;
		 }
		 else if(a[i]+a[j]>target)
		 {
		 	j--;
		 }
		 else
		 {
		 	i++;
		 }
	 }
  } 

二分方法：
本题可以也是可以用二分进行的，可以固定left，对right进行 *** 作，
注意需要先将数组排列有序才可以使用二分。

 int Binary_first(vector<int> a,int left,int right,int target)
  {
  	int mid;
  	int k=left;//左端点值不变，但是我们需要对mid进行放大或者缩小，left正常改变 
  	while(left<=right)
  	{
  		mid=left+(right-left)/2;
  		if(a[k]+a[mid]==target)
  		{
  			printf("%d %d\n",a[k],a[mid]);
  			return 1;
		  }
		  else if(a[k]+a[mid]>target)
		  {
		      right=mid-1; 
		  }
		  else
		  {
		  	left=mid+1;
		  }
	  }
	  return -1;
  }

2.合并两个递增数列
two_pointers的i和j不一定非要是开头和末尾，可以同时在一边，需要注意
合并两个递增数列，i指向第一个数列0，j指向第二个数列0
1.若a[i]>=a[j]，将a[j】加入排序队列，j++；
2.若a[i] 最后将两个数组（其中一个）剩下的全部放入排序队列
代码如下：

void Merge(vector<int> &a,vector<int>&b,int l1,int r1,int l2,int r2)//留下归并排序的接口 
  {
  	vector<int> c;
  	int i=l1;
  	int j=l2;
  	while(i<=r1&&j<=r2)
  	{
  		if(a[i]>=b[j])
  		{
  			c.push_back(b[j]);
  			j++;
		  }
		  else
		  {
		  	c.push_back(a[i]);
		  	i++;
		  }
	  }
	  while(i<=r1)
	  {
	  	c.push_back(a[i]);
	  	i++;
	  }
	  while(j<=r2)
	  {
	  	c.push_back(b[j]);
	  	j++;
	  }
	  cout<<c.size()<<endl;
	  for(int h=0;h<c.size();h++)
	  cout<<c[h]<<" ";
  }

tow poniters利用数组的特性，进行同向扫描或者反向扫描.
3.Two pointers练习
1.完美数列patA1085/PatB1030
Given a sequence of positive integers and another positive integer p. The sequence is said to be a perfect sequence if M≤m×p where M and m are the maximum and minimum numbers in the sequence, respectively.

Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.
p (≤10 ) 所有数据应该使用long long
For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.
本题：
首先可以考虑二分的方法,由于其只要求我们输出最后最大的元素个数，没有要求我们输出每个数字本来的位置，故我们可以首先对数组进行由大到小的排序。

经过上面的二分方法，我们可以选择固定left，来进行二分
每一次二分查找其实相当于寻找第一个使M>m*p大于的数
需要在算法笔记的模板代码前面补上一句，特判，例如寻找第一个大于等于5的数，若数列是1 2 3那么最后left=3显然不对的，那么需要开头特判，如果最大的比5小 return -1
1.若M<=mp那么 left=mid;
2.若M>mp 那么 right=mid-1;
left

int binary_perfect_sequence(vector<long long> &a,long long left,long long right,long long p)
 {
 	int k=left;
 	long long _q=p*a[left];
 	if(a[right]<=_q)return right-left+1;//最好在算法笔记上加上特判，这个是本例的特判 
 	while(left<right)
 	{
 		long long mid=left+(right-left)/2;
 		if(a[mid]<=_q)
 		{
 			left=mid+1;
		 }
		 else
		 {
		 	right=mid;
		 }
	 }
	 return right-k;
 }

采用two pointers方法
若采用反向扫描，那么显然变成了二分法
若采用同向扫描
i=0 j=0
1.a[j]<=pa[i] 记录长度,j++;
2. a[j]>pa[i] i++;
代码如下：

ll Two_pointers_perfect(vector<ll> &a,ll left,ll n,ll target)//ll为 long long 
 {
 	ll i=left;
 	ll j=i;
 	ll max=-1;
 	while(i<n&&j<n)
 	{
 		ll p=a[i]*target;
		 if(a[j]<=p)
		 {
		 	if(j-i+1>max)
		 	max=j-i+1;
		 	j++;
		  } 
		  else
		  {
		  	i++;
		  }
	 }
	 
 	return max;
 }

4.1089 Insert or Merge
insert sort 插入排序（iteration algorithm）
原理：假设前i项已经有序，判断第i+1项在前i项的位置，将其插入即可；
代码实现时候，插入的过程是整个数组向后移动的过程

void InsertSort(vector<int> &a)
 {
 	for(int i=1;i<a.size();i++)
 	{
 		int temp=a[i];
 		int j;
 		for (j=i;j>0;j--)
 		{
 			if(temp>a[j-1])
 			{
 				a[j]=a[j-1];
			 }
			 else
			 break;
		 }
		 a[j]=temp;
	 }
 }

merge sort归并排序
归并排序的核心就是我们上面写的merge函数，合并两个递增序列的函数
原理：将数组划分为一个包含k个元素的小组，将组内排序，然后组外合并即可。

递归实现：由高到低，n n/2 n/4…

 void Merge(vector<int> &a,int l1,int r1,int l2,int r2)//留下归并排序的接口 
  {
  	vector<int> c;
  	int i=l1;
  	int j=l2;
  	while(i<=r1&&j<=r2)
  	{
  		if(a[i]>=a[j])
  		{
  			c.push_back(a[j]);
  			j++;
		  }
		  else
		  {
		  	c.push_back(a[i]);
		  	i++;
		  }
	  }
	  while(i<=r1)
	  {
	  	c.push_back(a[i]);
	  	i++;
	  }
	  while(j<=r2)
	  {
	  	c.push_back(a[j]);
	  	j++;
	  }
	  for(int i=0;i<c.size();i++)
	  {
	  	a[i+l1]=c[i];
	  }
  }
 void MergeSort(vector<int> &a,int left,int right)//递归写法是分成两组排序，最后合并 
 {
 	if(left<right)
 	{
 		int mid=(left+right)/2;
 		MergeSort(a,left,mid);
 		MergeSort(a,mid+1,right);
 		Merge(a,left,mid,mid+1,right);
	 }
 }

非递归实现：
从每组1个开始，step代表两组总共的个数
step=2

void MergeSort1(vector<int>&a)
 {
 	int n=a.size();
 	for(int step=2;step/2<n;step*=2)
 	{
 		for(int i=0;i<n;i++)//从以1个元素为一组，然后逐步变为2，4...
 		{
 			int mid=i+step/2-1;
 			if(mid+1<n)//如果右侧存在 
 			{
 				Merge(a,i,mid,mid+1,min(n-1,i+step-1));//最后一组的个数不确定，取最小值
			 }
		 }
	 }
 }

那么这道题目也比较明确了，每一次运行完比较就可以了。

5.1029 Median
第一种：利用Merge函数即可，需要注意的是Mid是向上取整还是向下取整.
6.A1048find corns
寻找和为固定数，且只寻找v1最小的两个数，二分，two pointers修改一下即可
7.快速排序
快速排序算法的核心是实现将一个数的前面全是小于它的数，后面是大于它的数。

如何实现，采用two_poniters方法
默认替换第一个位置的数字a，i=0,j=n；可以认为刚开始前面空下一个位置，那么从j开始找小于a的数字，然后放在i这个位置，那么就空下j这个位置，寻找比j大的数字，依次循环下去。

当i==j时候说明寻找完毕，将a数字放入i这个位置

//快速排序中的分类函数 
  int Partition(vector<int>&a ,int left,int right)
  {
  	int i=left;
	int j=right;
	int temp=a[i];
	while(i<j)
	{
	while(i<j&&a[j]>temp) j--;//搜索位置 
	a[i]=a[j];
	while(i<j&&a[i]<temp) i++;//搜索位置 
	a[j]=a[i];
   } 
   a[j]=temp;
   return j;
}

那么如何实现快速排序算法的呢，每一次使用Partition，我们会得到一个位置，然会对位置的两侧继续使用快速排序即可

void QuickSort(vector<int> &a,int left,int right)
{
	if(left>=right) return;
	
	
		int pos=Partition(a,left,right);//先分割，在依次排序
		QuickSort(a,left,pos-1);
		QuickSort(a,pos+1,right);
	
 }