LEETCODE ALGORITHM:45. Jump Game II

发表于 更新于 分类于 Waline： 阅读次数：

题目

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:

1
2
3
4
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.

题解

从0开始跳，所能调到的所有位置为第二个起跳区间，在该区间找能跳的最远位置，当到达第二个起跳区间的最后一个位置，跳跃次数加一，进入第三个起跳区间，以此类推。（第一个起跳区间只是0号位置本身）

因为第n个起跳区间的的所有位置都能在n次跳跃到达，即为最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//贪心
class Solution {
public:
    int jump(vector<int>& nums) {
        int ans=0,maxp=0,end=0;
        for(int i=0;i<nums.size()-1;i++)
        {
            maxp=max(maxp,i+nums[i]);
            if(i==end)
            {
                end=maxp;
                ++ans;
            }
        }
        return ans;
    }
};