day1·算法-双指针

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

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

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

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

void moveZeroes(vector<int>& nums) {
        //解法1
        int 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;
    }   
};

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