45. Jump Game II

week8

难度：Hard

题目链接

题目描述

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.

Note:

  • The number of stones is ≥ 2 and is < 1,100.
  • Each stone’s position will be a non-negative integer < 231.
  • The first stone’s position is always 0.

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.

题目分析

  这道题目十分简单，就是给予一个数组，使得一开始在数组的首元素中，能够跳越到最后一项，而每项中的数字即跳跃的极限范围。给出最快到达数组尾的步数。

解题思路

  和上一周所做的青蛙跳十分类似，但又不太一样，因为这次的只给出了跳越的极限，所以范围可以选择0~x，使得几乎都可以到达终点。

  既然是这样的话，那么就可以不需要进行分支预测和判断了，直接使用贪心算法，贪心策略并不是每次都走到最远的距离，而是根据到达的顶点之后所能达到的最大距离。这样就能保证每一个的距离都是由上一个的最远距离而来。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size() == 0 || nums.size() == 1){
            return 0;
        }

        int maxjump = nums[0];
        int steps = 0;
        int index = 0;
        for(; index <= maxjump && index < nums.size() - 1;){
            steps++;
            if(maxjump >= nums.size() -1){
                return steps;
            }

            int nextjump = maxjump;
            int start = index;

            for(int i = nextjump; i >= start; i--){
                if(i + nums[i] > maxjump){
                    maxjump = i + nums[i];
                    index = i;
                }
            }
        }
        return -1;
    }
};

Note

  1. 这个贪心策略的证明可以根据递归来说明，即已经到达了终点，那么要寻找达到终点的最远的起点，不断地往前回溯，最后可以得知每一次判断下一个顶点的最远距离来选择下一个跳点，能够最快到达终点。

  2. 这个算法同青蛙跳石头一样可以进行优化，我们可以选择从当前可跳越的最远距离的顶点开始遍历，那么很有可能第一次就得到最佳跳点，就不用经常进行赋值运算。经过优化后的算法可从12ms降为8ms。

Jump Game II_test
Jump Game II_test

总结

  最近刚学习贪心算法，恰好用一下，这个题目的关键之处在于怎么去证明贪心是可行的，有可能不一定贪心就可以，就像上一周青蛙跳的题目，使用贪心算法时一定要注意是否满足条件。