前言：

補充一下前文沒有寫到的雙指針入門知識：專題1 -- 雙指針 -- 移動零

目錄

基礎(chǔ)入門知識：

1. 復(fù)寫零（easy）

1. 題?鏈接：1089.復(fù)習(xí)0 - 力扣（LeetCode）

2. 題?描述：

3.算法原理：

異地操作

本地操作

【從后向前的復(fù)寫過程】

整體思路：

??1.先找到最后一個“復(fù)寫”的數(shù);

1.5 處理一下邊界情況:

??2."從后向前"完成復(fù)寫操作（前面已經(jīng)驗證)

基礎(chǔ)入門知識：

常?的雙指針有兩種形式，?種是對撞指針，?種是左右指針。

對撞指針：?般?于順序結(jié)構(gòu)中，也稱左右指針。

? 對撞指針從兩端向中間移動。?個指針從最左端開始，另?個從最右端開始，然后逐漸往中間逼近。

? 對撞指針的終?條件?般是兩個指針相遇或者錯開（也可能在循環(huán)內(nèi)部找到結(jié)果直接跳出循環(huán)），也就是：

? left == right （兩個指針指向同?個位置）

? left > right （兩個指針錯開）

快慢指針：?稱為?兔賽跑算法

其基本思想：就是使?兩個??移動速度??不同的指針在數(shù)組或鏈表等序列結(jié)構(gòu)上移動。

??這種?法對于處理環(huán)形鏈表或數(shù)組?常有?。

其實不單單是環(huán)形鏈表或者是數(shù)組，?如果我們要研究的問題出現(xiàn)循環(huán)往復(fù)的情況時，均可考慮使?快慢指針的思想。

??快慢指針的實現(xiàn)?式有很多種，最常?的?種就是：

? 在?次循環(huán)中，每次讓慢的指針向后移動?位，?快的指針往后移動兩位，實現(xiàn)?快?慢

1. 復(fù)寫零（easy）

1. 題?鏈接：1089.復(fù)習(xí)0 - 力扣（LeetCode）

2. 題?描述：

給你?個?度固定的整數(shù)數(shù)組 arr ，請你將該數(shù)組中出現(xiàn)的每個零都復(fù)寫?遍，并將其余的元素向右平移。

注意：請不要在超過該數(shù)組?度的位置寫?元素。請對輸?的數(shù)組就地進?上述修改，不要從函數(shù)返回任何東西。

?例 1：

輸?： arr = [1,0,2,3,0,4,5,0]

輸出： [1,0,0,2,3,0,0,4]

解釋：

調(diào)?函數(shù)后，輸?的數(shù)組將被修改為： [1,0,0,2,3,0,0,4]

3.算法原理：

這題需要用到雙指針算法，但這不是憑空來的，原題目需要我們對原數(shù)組進行操作，

異地操作

??但是為了方便如何理解復(fù)寫 0?的過程，我們先畫出異地操作的過程：

原圖：

復(fù)寫過程：

cur用于遍歷原數(shù)組，dest指向了異地操作的數(shù)組，

當(dāng)cur指向的元素為非0時，dest此時要復(fù)寫一次cur指向的非0元素，cur++,dest++

當(dāng)cur指向的元素為?0?時，dest要先復(fù)寫一次0,之后dest++，再復(fù)寫一次0，復(fù)寫兩次完畢之后cur++，dest++

復(fù)寫完成：

本地操作

優(yōu)化為本地操作后，嘗試從前往后操作：

驗證【從后往前】操作的可行性:

因此我們選擇「從后往前」的復(fù)寫策略，cur指向最后一個需要復(fù)寫的元素，dest指向最后一個需要復(fù)寫的位置(結(jié)果中的最后一個位置)??

這同時也是上面異地操作的結(jié)果：

【從后向前的復(fù)寫過程】

結(jié)果：我們可以看到，原地操作和異地操作最終的復(fù)寫結(jié)果是一樣的

????????在這個示例里面，我們可以看到cur指向的4是最后一個需要復(fù)寫的元素，但是在其他示例里面我們不清楚，那么我們?nèi)绾握业阶詈笠粋€需要復(fù)寫的元素呢？

整體思路：

??1.先找到最后一個“復(fù)寫”的數(shù);

1.先判斷 cur 位置的值
2.決定 dest 向后移動一步或者兩步
3.判斷一下 dest 是否已經(jīng)到結(jié)束為止
4.cur++；

開始的狀態(tài)：

遍歷過程(動圖實現(xiàn)):

最終的狀態(tài)：

但是思考一下，此時如果cur指向的數(shù)組倒數(shù)第二個元素是0，那么dest此時指向的位置將會是數(shù)組最后一個元素的位置的下一個位置,因為上面遍歷的方式是遇到 0 則++兩次，非0是一次，那么必定會造成數(shù)組越界：

1.5 處理一下邊界情況:

arr[n - 1] = 0;

cur--;

dest -= 2;

??2."從后向前"完成復(fù)寫操作（前面已經(jīng)驗證)

代碼實現(xiàn)：

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
    int cur = 0,dest = -1,n=arr.size();
    
    //1.先找到最后一個需要復(fù)寫的數(shù)
    while(cur<n)
    {
        if(arr[cur])
            dest++;
        else
            dest+=2;
        if(dest>=n-1)//數(shù)組最后一個位置或者最后一個位置的下個位置
            break;
        cur++;
        }
    //2.處理一下邊界情況
    if(dest == n)
    {
        arr[n-1] = 0;
        cur--;
        dest-=2;
    }
    //3.從后往前完成復(fù)寫操作
    while(cur >= 0)
    {
        if(arr[cur])
        {
           arr[dest--] = arr[cur--];
           //arr[dest] = arr[cur],cur--,dest--
        }
        else
        {
           arr[dest--] = 0;
           arr[dest--] = 0;
           cur--;
        }
    }
    }
};

?

本篇完結(jié)。?

??本文修改次數(shù)：0

??更新時間：2024年3月26日??文章來源地址http://www.zghlxwxcb.cn/news/detail-854624.html

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