描述

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/jump-game-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

跳跃游戏II，可以用动态规划解，也可也用贪心解。

但最优解是用贪心，而且用贪心解也更好理解！

目标是：使用最少的跳跃次数到达数组的最后一个位置。【我们总是可以到达数组的最后一个位置。】

既然，总是可以到达数组最后一个位置。而且要求跳跃的次数最少

那么就让我们每次跳跃的距离最大就好！

拿[3,4,3,1,0,7,0,3,0,2,0,3]举例。

用pace记录跳数。

pace = 1

第一跳能跳到1(下标为3)。下跳的起跳点可以是3,4,3,1。找下一跳的最大覆盖范围。即(max(i+nums[i]))

pace = 2

下一跳最远可以跳到7(下标为5)。第三次起跳点可以是0,7。找下一跳的最大覆盖范围。即(max(i+nums[i]))

pace = 3

第三跳最远就可以跳到数组末尾了，所以结果已经出了，最少3跳。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int jump(int[] nums) {
        /*
            maxarea:最大范围
            curarea:当前所能抵达的范围
         */
        if(nums.length==1)return  0;//应对特殊情况 [0]
        int maxarea = nums[0],curarea = 0;
        int pace = 1;
        while (maxarea<nums.length-1){//如果最大范围已经可以到达末尾了
            pace++;
            int start = curarea,end = maxarea;
            curarea = maxarea;
            for (int i = start;i<=end;i++){//注意是 左闭右闭
                maxarea = Math.max(maxarea,i+nums[i]);//寻找下一条最大范围
            }
        }
        return pace;
    }
}

图解

有什么疑问欢迎评论区留言!

__END__