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--; }}
};