双指针_复写零

复写零

题目描述：

题目链接：复写零

内容：

这道题目要求我们每遇到一次0就复写一遍，并且只能在原数组上进行修改，不能越界访问。

算法原理：

思路1：

如果我们用两个指针cur,dest同时从指向第一个元素并从左往右遍历，cur指向元素为0，dest就让后面元素改为0。可想而知，后面的元素被覆盖掉了，又怎么继续复写呢？

那么我们可以从右往左复写。我们用cur指向最后一个复写的元素（eg1.中的4）,dest指向数组最后一个元素。1.cur指向元素不为0，dest指向元素写成cur指向的元素并--。2.cur指向元素为0，dest指向元素写0并--，因为要复写0，所有再执行一次dest的操作。cur--进入循环，直到cur==dest。

那问题来了，怎么才能找到最后一个复写的元素呢？我们先让cur dest 都指向第一个元素前面，cur先++，根据cur是否为0来决定dest走一步还是两步。直到dest指向最后一个元素。

当然还有越界情况，最后一次dest++两次正好指向最后一个元素后面。这种情况就要特殊处理。（eg.[1,0,2,3,0,4] —>[1,0,0,2,3,0]）让dest指向最后一个元素并改为0，cur dest再移向下一个元素继续循环就可以了。

1.利用双指针，cur指向最后一个复写元素，dest指向最后一个元素。（注意dest越界情况）

2.从右往左复写，cur指向0，dest修改2个元素为0。cur不为0，dest修改1个元素为cur指向的值。循环直到cur==dest (如果相等说明后面已经没有需要复写的0了)

代码实现：

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        //找cur位置
        int cur = -1, dest = -1;
        while (dest < (int)(arr.size() - 1)) 
        {
            cur++;
            if (arr[cur] == 0)
                dest += 2;
            else
                dest++;
        }
        //处理dest边界情况
        if (dest == arr.size()) 
        {
            arr[--dest] = 0;
            cur--;
            dest--;
        }
        //从右向左进行复写操作
        while (cur !=dest) 
        {
            if (arr[cur] == 0) 
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
            } 
            else 
            {
                arr[dest--] = arr[cur];
            }
            cur--;
        }
    }
};

注意点：

1.while (dest < (int)(arr.size() - 1)) 因为dest类型为int arr.size()返回的类型为size_t，-1大于size_t的最大值，所有不强制转为int会导致不进入循环.

2.找cur位置时要先让cur指向第一个元素。再按照1.根据cur元素值dest++还是+=2。2.再判断dest是否小于(int)(arr.size() - 1)。3.cur++

思路2：

我们可以用vector函数pop_back insert进行复写0.

利用迭代器遍历数组，遇到0就尾删，并在0位置前插入0。

代码实现：

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        vector<int>::iterator it=arr.begin();
        while(it<arr.end())
        {
            if(*it==0)
            {
                arr.pop_back();
                arr.insert(it,0);
                it++;
            }
            it++;
        }
    }
};

注意点：

1.这里先删除在插入一般不会发生迭代器失效。arr.insert(it,0);这里不用it=arr.insert(it,0);接收返回值也可以。

2.insert是在it位置前插入元素，插入后it位置上的元素是新插入的0，it++后才指向原本的0。

3.it<arr.end() 如果最后一个元素为0的话，it++两次就会大于arr.end()。所以it!=arr.end()会出现越界访问。