目錄

前言：

55. 跳躍游戲 - 力扣（LeetCode）

45. 跳躍游戲 II - 力扣（LeetCode）

總結(jié)：

前言：

????????今天兩道類型都是貪心算法，希望可以有所收獲

55. 跳躍游戲 - 力扣（LeetCode）

給定一個非負整數(shù)數(shù)組?nums?，你最初位于數(shù)組的?第一個下標(biāo)?。

數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最后一個下標(biāo)。

其實這道題注重的是思想，很多人把這道題當(dāng)作貪心算法思路去做，但是都陷入了一個思維陷阱：

我在當(dāng)前位置如何選擇下一步，使其最后能夠到達目的點。

但是如果這樣想，就會陷入很難的一個解題思路，就是如何選取下一步怎么走，因為有的時候貪的步數(shù)多反而無法到達重點。

因此我們不要糾結(jié)于到底應(yīng)該怎么走，而是看覆蓋范圍，我用實例給大家舉例子：

?我們可以用橫線表示覆蓋范圍：

?可以清楚的看到3已經(jīng)覆蓋了4，那么我們就可以知道在這個數(shù)組中，我們是可以走到最后一個點的。

我們再舉一個反例：

?我們就可以看到這個數(shù)組的元素（不包括最后一個元素）是無法覆蓋到最后一個點的，那么無論我們怎么走也不可能到達最后一個點。

因此這道題我們根據(jù)這種思想，可以寫出解法：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int size =nums.size();
        int cover=0;
        for(int i=0;i<=cover;i++)
        {
           cover=max(nums[i]+i,cover);
            if(cover>=size-1)
            {
                return true;
            }         
        }
        return false;
    }
};

45. 跳躍游戲 II - 力扣（LeetCode）

給定一個長度為 n 的 0 索引整數(shù)數(shù)組 nums。初始位置為 nums[0]。

每個元素 nums[i] 表示從索引 i 向前跳轉(zhuǎn)的最大長度。換句話說，如果你在 nums[i] 處，你可以跳轉(zhuǎn)到任意 nums[i + j] 處:

0 <= j <= nums[i]?
i + j < n
返回到達?nums[n - 1] 的最小跳躍次數(shù)。生成的測試用例可以到達 nums[n - 1]。

?這道題也是貪心算法思路，但是很多人貪心的目的錯了，上道題中我們引入了覆蓋范圍，那么實際上在最小跳躍次數(shù)的前提下我們貪的不是最多的步數(shù)，而是最大的覆蓋范圍。

根據(jù)這個解題思想，我們可以得出：

class Solution {
public:
    int jump(vector<int>& nums) {
        int size =nums.size();
        int cur=0;
        int next=0;
        int count=0;
        if(size==1)
        {
            return 0;
        }

        for(int i=0;i<size;i++)
        {
            next=max(i+nums[i],next);
            if(i==cur)
            {
                if(cur!=size-1)
                {
                    count++;
                    cur=next;
                }
                if(cur>=size-1)
                {
                    break;
                }
            }
        }
        return count;
    }
    
};

我來做一下詳細的解釋：先建立四個變量：size? 表示到達目的點所需長度，cur? 表示當(dāng)前所在點的覆蓋范圍，next? 表示我們將要跳到的點的覆蓋范圍，count? 記錄跳躍次數(shù)。

此后基于當(dāng)前位置的覆蓋范圍，我們向后尋找下一個最大的覆蓋范圍，這也就是for語句里面三個if的作用

• if(i==cur)用來判斷我們的是否已經(jīng)判斷完當(dāng)前覆蓋范圍內(nèi)的下一個最大覆蓋范圍。
• if(cur!=size-1)用來判斷是否當(dāng)前覆蓋范圍未覆蓋到目的點，如果不等于就是沒覆蓋，如果沒覆蓋，我們就要走到下一個最大覆蓋點處（cur=next),并且給跳躍次數(shù)+1（count++）
• if(cur>=size-1)用來判斷是否當(dāng)前覆蓋范圍已經(jīng)覆蓋到目的點，如果已經(jīng)覆蓋，則說明此時的跳躍步數(shù)就已經(jīng)是最短跳躍步數(shù)，直接退出循環(huán)，輸出結(jié)果。

總結(jié)：

貪心算法的題目萬變不離其宗，我們還是要通過大量的刷題掌握更多的貪心算法思路。

如果我的內(nèi)容對你有幫助，請點贊，評論，收藏。創(chuàng)作不易，大家的支持就是我堅持下去的動力！

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

?

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