LeetCode每日一题之 复写0

目录

题目介绍：

算法原理：

特殊位置处理：

代码实现：

题目介绍：

题目链接：. - 力扣（LeetCode）

算法原理：

这种对数组元素进行修改，移动的题目我们仍然可以使用双指针法，不过我们按照常规思路从左到右处理数组，不难发现如下这种问题：

当cur指向1时，让dest下一个元素复写cur指向的元素，并让dest和cur++，当cur指向0的时候， 让dest后两个元素复写0，并让cur++，dest+=2。按照这种常规思路，模拟运行几步就会发现问题：

当cur指向第一个0时，会让后面的2被0复写，这样就会导致未处理的数就会被覆盖 。那么如何解决这个问题呢？

当双指针算法可能会覆盖未处理数据时，我们不妨倒着来遍历数组，假设我们两根指针都已找到了结束位置（如何找到等会会讲）

此时，我们再像刚才那样：

若cur指向的元素不为0，则让dest指向的元素复写cur指向的元素，再cur--，dest--，若cur指向的元素为0，则让dest指向的元素复写0，再dest--，继续让dest指向的元素复写0，最后让dest--，cur--。

这样之后确实能像我们预想一样处理完数组，那么现在最重要的问题来了，就是，如何让两个指针找到结束位置。其实很简单，只要把上面讲的常规思路稍作修改，只移动指针，不复写数据，当dest走到数组末尾的时候结束：

初始位置如下：

当cur找到非0时，dest++,cur++。

当cur找到0时，dest+=2，cur++。

当dest走到数组末尾时结束。

这样走完后，我们的两个指针就会走到对应结束的位置。

特殊位置处理：

上面的算法看似完美，实则还有一个特殊情况没处理，当执行如下案例时：

在找结束位置算法中，两个指针走到如上图所示的位置时，此时cur指向0，dest走两个位置后

可以发现dest越界了，我们再像之前讲的那样复写时，会出现越界访问，所以要特殊处理一下：

当cur 和 dest 找到结束位置后，判断dest是否等于n（数组元素个数），若等于则是出现了这种情况，我们就用一个if 自己控制第一步复写，然后再让复写算法用循环走剩下的，第一步复写：先--dest，再让dest指向的元素复写cur指向的元素，再dest--，cur--,第一步复写后指针位置如图：

代码实现：

void duplicateZeros(int* arr, int arrSize) {
    int dest =-1;
    int cur =0;
    int n =arrSize;
    //找到结束位置
    while(dest<n-1)
    {
        if(arr[cur]==0)
        {
            dest+=2;
        }
        else
        {
            dest++;
        }
        if(dest<n-1)
        {
           cur++;
        }
    }
    //特殊位置处理
    if(dest==n)
    {
        dest--;
        arr[dest]=arr[cur];
        dest--;
        cur--;
    }
    //开始从后往前进行复写
    while(cur>=0)
    {
        if(arr[cur]==0)
        {
            arr[dest]=0;
            --dest;
            arr[dest]=0;
            --dest;
        }
        else
        {
            arr[dest]=arr[cur];
            --dest;
        }
        cur--;
    }
}