day1·算法-双指针

今天是第一天，GUNDOM带你学算法，跟上我的节奏吗，一起闪击蓝桥杯！

正文展开，今天先上点小菜供大家想用，如有错误或者建议直接放评论区，我会一个一个仔细查看的哦。

 双方指针问题一般是在数组中定义两个指针变量，通过对这两个指针变量进行操作来达到解决问题的目的。
用一道最显而易见的题目来解释。
移动0

 将所有的0都移动到数组的最后，我们可以遍历查找不是0的元素，然后将他们从下标位置为i=0位置依次放在数组中，因为可能有0元素的存在，所以在循环之后非零元素的值不会补齐数组中的所有元素，就像上边那个例子一样，我们要将nums.size()-i的部分置为0，这道题就算是结束了。
C++代码如下

void moveZeroes(vector<int>& nums) {//解法1int k=0;for(auto i:nums){if(i!=0){nums[k]=i;k++;}i++;}cout<<k<<endl;for(int j=k;j<nums.size();j++){nums[j]=0;}//写法二：int pre,tail;for(pre=0,tail=0;tail<nums.size();tail++){if(nums[tail]!=0){swap(nums[pre++],nums[tail]);}}}

复写零

 如果数组中有零元素，就将该0复写，后边的元素顺序不变，可以知道，如果有0元素，就一定会有元素越界被丢弃。
这道题目思路很容易想到，但是还是有一点坑点。
思路如下
 首先要找到最终复写的位置，然后从这个位置依次向前复写

在找到要求数组的最后一位后，根据值向前遍历。
 假设找到的位置为head，根据head位置的值来确定数组从后往前写什么，初始写入的位置一定是arr.size()-1。如果tail位置是0，就可以往前确定两个位置都是零，如果不是零，就在当前tail位置写入head位置的值，然后更新head和tail的数值。
代码如下

void duplicateZeros(vector<int>& arr) {int head = 0;int tail = 0;while (tail < arr.size()){if (arr[head] == 0){tail ++;}tail++;head++;}head--;cout << head << endl;tail = arr.size() - 1;while (tail>0){if (arr[head] == 0){arr[tail--] = 0;arr[tail--] = 0;}else{arr[tail--] = arr[head];}head--;}for (auto i : arr){cout << i;}
}

动图演示如下

但是写完后提交……

推演一遍我们就会发现，head落在了不对的地方，所以才会造成一连串错误。

 如果tail位置大于size,那就直接将数组末尾元素置0，将tail和head向前移动，重新锁定位置。

if (tail > arr.size()){arr[arr.size() - 1] = 0;tail =arr.size()-2;head=head-1;}else{tail = arr.size() - 1;}

顺利过关。

盛水最多的容器
 以x轴为桶宽，以y轴为木桶高度，我们知道水桶效应，判断木桶能装多少水是取决于短板的。
 分析题目，如果用暴力求解的方法，依次算出不同变量下木桶能盛多少水，然后就可以知道最大的装水量。
使用双指针算法可以遍历更少的次数求解出答案。

 包含第一个轴的最大盛水量就求出来了，保存该值，以第二个轴和第一个轴为木桶边界（以下称head,tail）此时两轴中低的是7，移动前边的轴宽度会减小，且高度最大还是7，所以又求出一个最大值49。
 移动后边的轴即tail，以倒数第二个轴即3的高度继续以同样的形式继续求最大值，可以得到18，移动前边的轴，即head，继续判断。
可以看出这种方式只遍历一遍，就可以找到最大的面积。
代码如下

class Solution {
public:
int maxnum(int a,int b)
{return a>b?a:b;
}
int minnum(int a,int b)
{return a<b?a:b;
}int maxArea(vector<int>& height) {int left=0;int right=height.size()-1;int width=right;int mul=0;int ret=0;while(left!=right){int length=minnum(height[left],height[right]);ret=length*width;if(ret>mul){mul=ret;}if(height[left]<height[right]){left++;}else{right--;}width--;}return mul;}   
};

总结：
 双指针的题目只需要有清晰的思路，要清楚指针的位置，把握好结束条件，双指针的思路上边的题目玩的很简单，最后一道题要善于观察分析，就可以写出更加高效的方法。