題目

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