題目鏈接
tag:
- Hard；
- Greedy衅枫；
question：
??Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:
You can assume that you can always reach the last index.
思路：
??這題是之前那道Jump Game 跳躍游戲 的延伸并炮，那題是問(wèn)能不能到達(dá)最后一個(gè)數(shù)字，而此題只讓我們求到達(dá)最后一個(gè)位置的最少跳躍數(shù)，貌似是默認(rèn)一定能到達(dá)最后位置的? 此題的核心方法是利用貪婪算法Greedy的思想來(lái)解钉赁，想想為什么呢？ 為了較快的跳到末尾携茂，我們想知道每一步能跳的范圍你踩，這里貪婪并不是要在能跳的范圍中選跳力最遠(yuǎn)的那個(gè)位置，因?yàn)檫@樣選下來(lái)不一定是最優(yōu)解，這么一說(shuō)感覺(jué)又有點(diǎn)不像貪婪算法了带膜。我們這里貪的是一個(gè)能到達(dá)的最遠(yuǎn)范圍吩谦，我們遍歷當(dāng)前跳躍能到的所有位置，然后根據(jù)該位置上的跳力來(lái)預(yù)測(cè)下一步能跳到的最遠(yuǎn)距離膝藕，貪出一個(gè)最遠(yuǎn)的范圍式廷，一旦當(dāng)這個(gè)范圍到達(dá)末尾時(shí)，當(dāng)前所用的步數(shù)一定是最小步數(shù)芭挽。我們需要兩個(gè)變量cur和pre分別來(lái)保存當(dāng)前的能到達(dá)的最遠(yuǎn)位置和之前能到達(dá)的最遠(yuǎn)位置滑废，只要cur未達(dá)到最后一個(gè)位置則循環(huán)繼續(xù)，pre先賦值為cur的值袜爪，表示上一次循環(huán)后能到達(dá)的最遠(yuǎn)位置策严，如果當(dāng)前位置i小于等于pre，說(shuō)明還是在上一跳能到達(dá)的范圍內(nèi)饿敲，我們根據(jù)當(dāng)前位置加跳力來(lái)更新cur妻导，更新cur的方法是比較當(dāng)前的cur和i + A[i]之中的較大值，如果題目中未說(shuō)明是否能到達(dá)末尾怀各，我們還可以判斷此時(shí)pre和cur是否相等倔韭，如果相等說(shuō)明cur沒(méi)有更新，即無(wú)法到達(dá)末尾位置瓢对，返回-1寿酌，代碼如下：
class Solution {
public:
int jump(vector<int>& nums) {
int res = 0, n = nums.size(), i = 0, cur = 0;
while (cur < n - 1) {
++res;
int pre = cur;
for (; i<= pre; ++i)
cur = max(cur, i + nums[i]);
if (pre == cur) return -1; // May not need this
}
return res;
}
};
