今日分享一道力扣經(jīng)典題目，復(fù)寫0！

題目如下：

題目分析：

題目要求是進行復(fù)寫0，而且不能超過原數(shù)組長度，且只能在原地進行操作！

解決本題最好的方法就是進行雙指針方法！

算法分析

一、雙指針算法先找到最后一個要復(fù)寫的數(shù)！

二、然后從后向前進行完成復(fù)寫（因為如果要是從前向后進行復(fù)寫會導(dǎo)致元素的覆蓋！）

其中第一大步又是一個雙指針的思想：再次分為了以下幾步！

1.判斷cur指針位置的值！

2.決定des向后移動1或2步?。?span style="color:#fe2c24;">如果cur的值為0則des向后移動兩步，否則移動一步）！

3.判斷是否達到原數(shù)組的最大長度！即（des的位置是否等于n-1）!若des已經(jīng)結(jié)束，直接跳出循環(huán)！

4.若3不滿足，則進行cur++操作！

5.因為最后des的位置可能是數(shù)組長度的最大值，也可能是最大值后面那個值！所以后面還需進行判斷是否以及越界！若以越界，再進行修改即可！

此步驟非常重要！一定要考慮到，如若沒有考慮到，那么則會導(dǎo)致越界的問題！

當(dāng)?shù)谝淮蟛浇Y(jié)束時，此時des位置處于最后需要復(fù)寫的最后一個位置，cur位置為最后一個復(fù)寫的元素！然后最后進行從后向前完成復(fù)寫即可！

畫圖分析：

代碼實現(xiàn)

C代碼

void duplicateZeros(int* arr, int arrSize)
{
    //雙指針！解法進行求解！
    //首先先找到最后一個復(fù)寫的元素！
    int cur=0;
    int des=-1;
    while(des<arrSize)
    {
        if(arr[cur])
        {
            des++;
        }
        else if(arr[cur]==0)
        {
            des+=2;
        }
        //必須需要注意的是只要des位于最后一個位置即arrSize-1即停止循環(huán)！
        if(des>=arrSize-1)
        {
            break;
        }
        cur++;
    }

    //經(jīng)過此時，cur位于最后一個復(fù)寫的元素！des位于最后一個位置或者之后的位置！
    //此時需要注意的是，如果des位于n的位置是，此時已經(jīng)越界！
    if(des==arrSize)
    {
        arr[arrSize-1]=0;
        des-=2;
        cur--;
    }

    while(cur>=0)
    {
        if(arr[cur]==0)
        {
            arr[des--]=0;
            arr[des--]=0;
        }
        else
        {
            arr[des]=arr[cur];
            des--;
        }
        cur--;
    }
}

c++代碼

class Solution {
public:
    void duplicateZeros(vector<int>& arr)
    {
        
        int cur=0;
        int des=-1;
        int n=arr.size();
        while(cur<n)
        {
            if(arr[cur])
            {
                des++;
            }
            else
            {
                des+=2;
            }
            if(des>=n-1)
            {
                break;
            }
            cur++;
        }
        if(des==n)
        {
            arr[n-1]=0;
            des-=2;
            cur--;
        }
        while(cur>=0)
        {
            if(arr[cur]==0)
            {
                arr[des--]=0;
                arr[des--]=0;
            }
            else
            {
                arr[des]=arr[cur];
                des--;
            }
            cur--;
        }
    }
};

今日分享到此結(jié)束！如若還有不懂，歡迎評論區(qū)留言！文章來源地址http://www.zghlxwxcb.cn/news/detail-738307.html

到了這里，關(guān)于力扣：1089. 復(fù)寫零的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！