目錄

題目介紹：

算法原理：

特殊位置處理：

代碼實(shí)現(xiàn)：

題目介紹：

題目鏈接：. - 力扣（LeetCode）

算法原理：

這種對(duì)數(shù)組元素進(jìn)行修改，移動(dòng)的題目我們?nèi)匀豢梢允褂秒p指針?lè)?，不過(guò)我們按照常規(guī)思路從左到右處理數(shù)組，不難發(fā)現(xiàn)如下這種問(wèn)題：

當(dāng)cur指向1時(shí)，讓dest下一個(gè)元素復(fù)寫cur指向的元素，并讓dest和cur++，當(dāng)cur指向0的時(shí)候，?讓dest后兩個(gè)元素復(fù)寫0，并讓cur++，dest+=2。按照這種常規(guī)思路，模擬運(yùn)行幾步就會(huì)發(fā)現(xiàn)問(wèn)題：

當(dāng)cur指向第一個(gè)0時(shí)，會(huì)讓后面的2被0復(fù)寫，這樣就會(huì)導(dǎo)致未處理的數(shù)就會(huì)被覆蓋?。那么如何解決這個(gè)問(wèn)題呢？

當(dāng)雙指針?biāo)惴赡軙?huì)覆蓋未處理數(shù)據(jù)時(shí)，我們不妨倒著來(lái)遍歷數(shù)組，假設(shè)我們兩根指針都已找到了結(jié)束位置（如何找到等會(huì)會(huì)講）

?此時(shí)，我們?cè)傧駝偛拍菢樱?/p>

若cur指向的元素不為0，則讓dest指向的元素復(fù)寫cur指向的元素，再cur--，dest--，若cur指向的元素為0，則讓dest指向的元素復(fù)寫0，再dest--，繼續(xù)讓dest指向的元素復(fù)寫0，最后讓dest--，cur--。

這樣之后確實(shí)能像我們預(yù)想一樣處理完數(shù)組，那么現(xiàn)在最重要的問(wèn)題來(lái)了，就是，如何讓兩個(gè)指針找到結(jié)束位置。其實(shí)很簡(jiǎn)單，只要把上面講的常規(guī)思路稍作修改，只移動(dòng)指針，不復(fù)寫數(shù)據(jù)，當(dāng)dest走到數(shù)組末尾的時(shí)候結(jié)束：

初始位置如下：

當(dāng)cur找到非0時(shí)，dest++,cur++。

當(dāng)cur找到0時(shí)，dest+=2，cur++。

當(dāng)dest走到數(shù)組末尾時(shí)結(jié)束。?

這樣走完后，我們的兩個(gè)指針就會(huì)走到對(duì)應(yīng)結(jié)束的位置。

特殊位置處理：

上面的算法看似完美，實(shí)則還有一個(gè)特殊情況沒(méi)處理，當(dāng)執(zhí)行如下案例時(shí)：

在找結(jié)束位置算法中，兩個(gè)指針走到如上圖所示的位置時(shí)，此時(shí)cur指向0，dest走兩個(gè)位置后

可以發(fā)現(xiàn)dest越界了，我們?cè)傧裰爸v的那樣復(fù)寫時(shí)，會(huì)出現(xiàn)越界訪問(wèn)，所以要特殊處理一下：

? 當(dāng)cur 和 dest 找到結(jié)束位置后，判斷dest是否等于n（數(shù)組元素個(gè)數(shù)），若等于則是出現(xiàn)了這種情況，我們就用一個(gè)if 自己控制第一步復(fù)寫，然后再讓復(fù)寫算法用循環(huán)走剩下的，第一步復(fù)寫：先--dest，再讓dest指向的元素復(fù)寫cur指向的元素，再dest--，cur--,第一步復(fù)寫后指針位置如圖：

代碼實(shí)現(xiàn)：

void duplicateZeros(int* arr, int arrSize) {
    int dest =-1;
    int cur =0;
    int n =arrSize;
    //找到結(jié)束位置
    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--;
    }
    //開始從后往前進(jìn)行復(fù)寫
    while(cur>=0)
    {
        if(arr[cur]==0)
        {
            arr[dest]=0;
            --dest;
            arr[dest]=0;
            --dest;
        }
        else
        {
            arr[dest]=arr[cur];
            --dest;
        }
        cur--;
    }
}

?

?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-856176.html

到了這里，關(guān)于LeetCode每日一題之 復(fù)寫0的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！