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.
Main Idea:
when write the code except for the main idea,please pay attention to >= > the difference may cause result different
#include<stdio.h> #include<iostream> #include<string> #include<vector> using namespace std; class Solution { public: int jump(vector<int>& nums) { int res=0,r=0,l=0,next_r=0; int times=nums.size()-1; while(r<times) { for(int i=l;i<=r;i++) { next_r=max(next_r,nums[i]+i); } l=r+1; r=next_r; res++; } return res; } }; int main() { Solution s; vector<int> v; v.push_back(2); v.push_back(3); v.push_back(1); v.push_back(1); v.push_back(4); int res=s.jump(v); cout<<res<<endl; return 0; }
LeetCode开心刷题二十四天——45. Jump Game II
原文：https://www.cnblogs.com/Marigolci/p/11246365.html