Problem: 1089. 復寫零

題目解析

首先我們來分析一下本題的題目意思

• 可以看到題目中給到了一個數(shù)組，意思是讓我們將數(shù)組中的零元素都復寫一遍，然后將其余的元素向后平移

• 光就上面這樣來看還是不太形象，我們通過畫圖來分析一下，通過下圖我們可以看到，凡是0的都復寫了兩遍，凡不是0的都復寫了一遍

• 但是呢題目中很明顯地講到只能讓我們在數(shù)組上進行就地操作，但是就我們上面的操作而言則是在另外開辟了一塊數(shù)組的空間

那在下面我們就去考慮一下在數(shù)組原地的操作

• 可以看到在下面我使用到了雙指針的操作，若是cur遍歷到0的話就進行兩次的復寫操作，不過呢大家可以看到在第一次的復寫操作完成之后，【2】被覆蓋了，但是這個【2】是我們需要的，那也就造成了一定的問題

?? 那么反應快的同學可以意識到，如果要進行覆蓋操作的話就需要 從后往前 進行遍歷操作才可以

算法原理分析

好，接下去呢我們就來分析一下解決本題的思路

找到最后一個復寫的位置

• 上面說到是要從后往前開始做復寫操作，那么第一步我們所要做的就是找到最后一個復寫的位置，即讓這個dest指向最后的0

那要怎么去找呢？（頭一次嘗試幻燈片≧ ﹏ ≦）

可以分為以下幾步：

1. 判斷cur位置的值，決定dest走一步還是兩步
2. 判斷dest是否到達末尾，決定cur是否++

<,,,,,,>

但是呢，就上面這樣的邏輯去走的話其實是不對的，因為我們還未考慮到特殊的邊界情況

• 即下面的這種情況，當測試用例的倒數(shù)第二個數(shù)為0的時候，此時dest又剛好到這個位置，那么就需要向后移動兩步，此時就造成了越界問題

所以此時我們應該要考慮處理一下這個邊界問題

• 因為倒數(shù)第二個數(shù)為0，那么對其進行復寫操作的話，最后一個也是0，我們將其做一個修改即可，不過呢兩個指針cur和dest也需要去做一個變化，cur前移一位即可，dest因為做了復寫操作，所以需要前移兩位

從后往前進行復寫操作

上面呢，我們已經(jīng)找到了需要復寫的最后一個位置，那接下去我們就要正式開始復寫操作了

• 這一塊的話就不做動畫演示了，讀者可以試著自己去手動模擬一下，也就是從我們上面所找到的cur位置開始，慢慢地向前遍歷然后去做復寫操作即可，將數(shù)一一地復寫到dest所在的位置，如果arr[cur]為0的話，那我們就需要考慮復寫兩次了

代碼展示

最后來展示一下整體的代碼

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        // 1.找到復寫的最后一個位置
            // (1) 判斷cur位置的值，決定dest走一步還是兩步
            // (2) 判斷dest是否到達末尾，決定cur是否++
        int dest = -1;
        int cur = 0;
        int sz = arr.size();
        while(dest < sz)
        {
            if(arr[cur])  dest++;
            else   dest += 2;
            if(dest >= sz - 1)
                break;
            cur++;
        }

        // 2.判斷邊界的情況
        if(dest == sz)
        {
            arr[dest - 1] = 0;
            cur--;
            dest -= 2;
        }     

        // 3.從右往左復寫0
        while(cur >= 0)
        {
            if(arr[cur]) arr[dest--] = arr[cur--];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }   
    }
};

下面是運行后的結(jié)果

文章來源地址http://www.zghlxwxcb.cn/news/detail-667939.html

到了這里，關(guān)于【算法】活用雙指針完成復寫零操作的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！