LeetCode - 1089. 复写零

题目

1089. 复写零 - 力扣（LeetCode）

思路

这道题我首先想到的是从前往后双指针，但是这样做会造成数据的覆盖，比如说下面的这个情况

所以解决的方法就是从后往前去复写，但是从后往前的话就要知道最后一个有效元素是什么。

对于这个情况，我们可以先去根据"异地操作"找到最后一个有效元素，需要一个cur指针，和一个dest指针，cur先进行判断，当遇到非0元素cur++,dest++，当遇到0元素，就让cur,dest+2，直到dest到数组的末端，判断此时的cur就是最后一个有效元素

再进行优化，我们就需要双指针下的"就地"操作

但是此时会有个特殊情况：当cur最后一个位置是0的时候，会导致dest+2的时候越界了，此时就会报错了

所以我们要处理这个边界情况，方法就是当查找有效位置的时候，跳出循环后，如果dest=n，此时说明cur指向的一定0（这样另外数的dest连跳两步所以才会越界），所以我们此时让dest-1的位置为0，然后dest-=2，cur-1

接下来就是

读者可能出现的错误写法

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = arr.size();
        int cur = 0;
        int dest = 0;

        while(arr[dest])
        {
            if(arr[cur]==0)
            {
                cur++;
                dest+=2;
            }
            else
            {
                cur++;
                dest++;
            }
        }

        while(arr[cur])
        {
            if(arr[cur]==0)
            {
                cur--;
                for(int i=0;i<2;i++)
                {
                    arr[dest] = 0;
                    dest--;
                }

            }
            else
            {
                arr[dest] = arr[cur];
                cur--;
                dest--;
            }  
        }

    }
};

第一个问题是循环条件写错了，while(arr[dest]) 这里有问题，你这样写的话，如果dest越界了，访问arr[dest]就会出错。应该改成 while(dest < n)。

第二个问题是第二个循环也有问题，while(arr[cur]) 这里也不对，应该改成 while(cur >= 0)。

第三个问题是缺少边界处理，你没有处理那种刚好在边界的特殊情况。

修改一下：首先第一个while循环应该是 while(dest < n)，然后在循环里面如果arr[cur]等于0就让dest加2，否则dest加1，但是要记得加个判断if(dest >= n) break，然后cur++。

接下来要处理边界情况，如果dest==n的话，说明最后一个0只能写一半，所以arr[n-1] = 0，然后dest减2，cur减1。

最后第二个while循环应该是while(cur >= 0)，在循环里面如果arr[cur]是0就连续写两个0到dest位置，否则就把arr[cur]写到dest位置，记得每次都要cur和dest往前移。

dest表示"当前元素应该在的最终位置"，因为我们不知道第一个元素应该在的位置，所以应该初始化为-1

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = arr.size();
        int cur = 0;
        int dest = -1;

        while(dest<n)
        {
            if(arr[cur]==0)
            {
                dest+=2;
            }
            else
            {
                dest++;
            }
            if(dest >= n-1) break;
            cur++;
        }

        if(dest>n-1)
        {
            arr[n-1] = 0;
            dest-=2;
            cur--;
        }

        while(cur>=0)
        {
            if(arr[cur]==0)
            {
                for(int i=0;i<2;i++)
                {
                    arr[dest] = 0;
                    dest--;
                }
            }
            else
            {
                arr[dest] = arr[cur];
                dest--;
            } 
            cur--; 
        }
    }
};