双指针练习：复写0

1.题目链接：1089.复写零

2.题目描述：

给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

3.解法（原地复写-双指针）：

算法思路：

如果「从前往后」进行原地复写操作的话，由于0的出现会复习两次，导致没有复写的数「被覆盖掉」，因此我们选择「从后往前」的复写策略。

但是「从后往前」复写的时候，我们需要找到「最后一个复写的数」，因此我们的大体流程分为两步：

a.先找到最后一个复写的数；

b.然后从后往前进行复写操作。

算法流程：

1.初始化两个指针 cur = 0，dest = 0；

2.找到最后一个复写的数

        a.当 cur < n 的时候，一直执行下面循环：

                （1）判断cur位置的元素：

                        ·如果是0的话，dest++

                        ·否则dest++

                （2）判断dest时候是否已经到结束位置，如果结束就终止循环；

                （3）如果没有结束，cur++，继续判断

3.判断dest是否越界到n位置：

        a.如果越界：执行下面三步：

                ·n-1 位置值修改为0；

                ·cur 向后移动一步；

                ·dest 向前移动两步；

                （越界的原因是因为cur 位置为0，des+=2 ，越界了一位，修改了一位数组以外的数据为0，即非法访问，因此，此时我们只需要修改一个dest为0就可以了，因此先手动修改arr[n-1] = 0 ，此时cur当前指的0也就我们手动修改过了，因此cur--，dest-=2）

4.从cur位置开始往前遍历原数组，依次还原出复写后的结果数组：

        a.判断cur位置的值：

                ·如果是0，dest以及dest -1位置修改成0，dest-=2；

                ·如果非0，dest位置的数据 = cur位置的数据，dest--；

        b.cur--，复写下一个位置

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        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;
                dest -= 2;
                cur--;
      }

        // 复写
        while(cur >= 0){
        if(arr[cur]) 
        arr[dest--] = arr[cur--];
        else {
            arr[dest--] = 0;
            arr[dest--] = 0;
            cur--;
            }
    }
    }

};