[数据结构与算法]45. 跳跃游戏 II

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

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

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

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

我的思路是采用深度遍历,输出所有可能的跳跃方式的步数,取其中最小的那个

代码如下:

class?Solution?{

????int?res?=?Integer.MAX_VALUE;

????

????public?int?jump(int[]?nums)?{

????????dfs(nums,?0,?0);

????????return?res;

????}

????

????public?void?dfs(int[]?nums,int?index,int?times){

????????if?(index?==?nums.length-1){

????????????res?=?Math.min(res,?times);

????????????return;

????????}

????????if?(index?>=?nums.length){

????????????return;

????????}

????????for?(int?i?=?1;?i?<=?nums[index];?i++)?{

????????????dfs(nums,?index+i,?times+1);

????????}

????}

}

问题:超出时间限制

这题是典型的贪心算法

官方给出的思路是:

第一种:如果有多个位置通过跳跃都能够到达最后一个位置，那么我们应该如何进行选择呢？直观上来看，我们可以「贪心」地选择距离最后一个位置最远的那个位置，也就是对应下标最小的那个位置。因此，我们可以从左到右遍历数组，选择第一个满足要求的位置。

第二种:正向搜索每次找到可到达的最远位置,注意这里指的是每次覆盖范围最大,并不是有多远跳多远,而是每次跳的都是将会产生最大覆盖范围的位置.

代码如下:

class Solution {
? ? public int jump(int[] nums) {
? ? ? ? int length = nums.length;
? ? ? ? int end = 0;
? ? ? ? int maxPosition = 0;?
? ? ? ? int steps = 0;
? ? ? ? for (int i = 0; i < length - 1; i++) {
? ? ? ? ? ? maxPosition = Math.max(maxPosition, i + nums[i]);?
? ? ? ? ? ? if (i == end) {
? ? ? ? ? ? ? ? end = maxPosition;
? ? ? ? ? ? ? ? steps++;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return steps;
? ? }
}