算法入门：专题攻克主题一---双指针（1）移动零 复写零

移动零：

移动零leetcode题目

数组划分，数组分块，双指针算法来解决，也就是用数组的下标来充当指针。 双指针的解释：

cur：从左往右扫描数组，遍历数组； dest:已处理的区间内，非零元素的最后一个位置； 该怎么理解呢？

数组元素的下标从0到n-1,也就是这两个指针将区间划分为3个段，[0，dest] [dest+1,cur-1] [cur,n-1] [0,dest]是已处理区间，[dest+1,cur-1]是零元素，[cur+1,n-1]是待处理区间

cur是从左往右开始扫描，所以首先应该指向下标为0的位置，dest作为非零元素的最后一个位置，这里首先指向下标为-1的位置

当cur在走的过程中有两种情况：cur指向零元素，cur++,走向下一个元素，此时[dest+1,cur-1]区间就是零元素区间，仅仅向后挪动一位不做处理；cur指向非零元素，就要让这个元素加入到已处理区间内部，所以这个地方就交换，dest++之后，再交换；

当cur遍历到指向nullptr的位置时就说明已经遍历结束了，此时完全实现了数组中的零元素全部在数组的末尾位置。 如何做到？ cur从前往后遍历的过程中： 1.遇到0元素：cur++；2.遇到非零元素：swap(dest+1,cur);cur++;dest++

上代码！！！

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int cur=0,dest=-1;cur<nums.size();cur++)
        {
            if(nums[cur]!=0)
                swap(nums[++dest],nums[cur]);//dest先自增1，swap的是增加1之后的值
                //于此同时这里dest也完成了++
        }
    }
};

复写零

复写零leetcode题目

题目解析：给了一个数组，把数组中出现的0复写一遍，不允许开数组，也没有任何返回类型，将其余元素向右平移。 解法：双指针解法，先根据“异地”操作，然后优化成双指针下的“就地”操作 也即是创建一个新的数组，大小跟原数组一样， 定义一个cur用来扫描原数组，定义一个dest用来扫描新的数组， 当cur指向非0元素，将cur指向的数据拿下来复制到dest指向的位置，接着实现cur++,dest++; 当cur指向0元素，将cur指向的0拿下来复制到dest指向的位置，接着dest++的位置再次写入一个0，最后实现cur++,dest++,当dest越界时完成操作。

但是不允许开数组，我们可不可以将两个指针实现到同一个数组当中呢？

还是向上一道题一样，我们将cur的位置指向下标为0的位置，将dest也指向0的位置，如果还是从左向右的操作，复写0会覆盖掉右边还没有被判断是否为0的数字，那可以从右向左吗？

让dest指向最后一个位置（下标为n-1的元素位置），cur指向最后一个被复写的元素， 当cur指向的位置是非零元素，将cur位置的值赋值给dest，cur--;dest--;如果cur指向的位置是零元素，将cur位置的值赋值给dest,dest之前一个位置的值也是0，还要实现cur--,dest--;如果cur和dest都越界的话完成操作。

总结

1.先找到最后一个“复写”的数； 2.从后向前完成复写操作； 那么我们该怎么找到最后一个复写的数字呢？ 这里还要再嵌套一个双指针算法；cur指向下标为0的元素，dest指向下标为-1的元素，当cur指向位置的值为非零元素，dest++，再判断一下dest是否已经走到空了，再cur++；当cur指向位置的值是非零元素，dest向后移动2步,再判断一下dest是否已经走到空了，再cur++;到最后cur位置指向的是最后一个被复写的数字，dest刚好指向数组下标n-1的位置。这样才可以进行后续操作。 这一步我们总结： 1.先判断cur位置的值； 2.决定dest向后移动一位还是两位； 3.判断dest是否已经走到空了； 4.以上条件满足则cur++

还要一种特殊情况；如果数组的倒数第二个位置的数字是0，再进行上述找到最后一个复写的数字时，会导致dest移动的时候发生越界，比如说数组[1,0,2,3,0,4],按照上述操作cur最后指向的位置是0，但是dest需要向后走两步，这样就会造成越界。 所以要处理一下边界情况：把n-1的位置修改为0，然后将dest向前移动两位，cur向前移动一位再继续进行从后向前的复写操作。

上代码！

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        //1.先找最后一个复写的数
        int cur=0,dest=-1,n=arr.size();
        while(cur<n)
        {
            if(arr[cur]){dest++;}
            else{dest+=2;}
            if(dest>=n-1)break;//是否走到空了
            cur++;
        }

        //处理一下边界情况
        if(dest==n)
        {
            arr[n-1]=0;
            cur--;dest-=2;
        }

        //3.从后向前完成复写操作
        while(cur>=0)
        {
            if(arr[cur]!=0) arr[dest--]=arr[cur--];
            else{
                arr[dest--]=0;
                arr[dest--]=0;
                cur--;
            }
        }

    }
};