題目

給定一個(gè)非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個(gè)位置。

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

你的目標(biāo)是使用最少的跳躍次數(shù)到達(dá)數(shù)組的最后一個(gè)位置。

示例:

輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個(gè)位置的最小跳躍數(shù)是 2。
從下標(biāo)為 0 跳到下標(biāo)為 1 的位置，跳 1 步，然后跳 3 步到達(dá)數(shù)組的最后一個(gè)位置。

說(shuō)明:
假設(shè)你總是可以到達(dá)數(shù)組的最后一個(gè)位置。

思考

下面看我的思路草圖：
每次需要更新的參數(shù)：當(dāng)前遍歷的start、end，當(dāng)前遍歷范圍中找到的最大的下一步的end。
迭代結(jié)束條件：end < nums.size()-1；

按照這個(gè)思路很快可以寫(xiě)出來(lái)代碼：

class Solution { public:int jump(vector<int>& nums) { int start = 0;int end = 0;int step = 0;//只有end >= nums.size()-1,才退出whilewhile(end < nums.size()-1){//找到當(dāng)前覆蓋范圍能到達(dá)的最遠(yuǎn)距離int max_distance = 0;for(int i = start;i <= end;i++){max_distance = max(nums[i]+i,max_distance);}//利用最遠(yuǎn)距離更新end和startstart = end + 1;end = max_distance;//步數(shù)加一step += 1;}return step;} };

總結(jié)

貪心思想：每次記錄你能夠跳到的最遠(yuǎn)距離 max_distance ！！！
下一次尋找的范圍從上一次范圍的end后面一個(gè)開(kāi)始，到最遠(yuǎn)距離結(jié)束。

start = end + 1; end = max_distance;

總結(jié)

以上是生活随笔為你收集整理的leetcode 45. 跳跃游戏 II 思考分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。