LeetCode-045-跳跃游戏|LeetCode-045-跳跃游戏 II LeetCode-045-跳跃游戏II

跳跃游戏 II

题目描述：给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例说明请见LeetCode官网。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：穷举法

首先，如果nums的长度为1，因为不需要走，直接返回0；

如果nums的长度为2，由于一定可以到达最后一个位置，而且至少需要一步，直接返回1；

当不是前两种情况时，首先，声明一个变量length为数组最大的索引位，声明一个变量result记录最少的跳跃次数，初始化为最大的的int值，声明一个HashMap为toJumpTimes记录跳跃过的位置和相应跳跃到该位置最少的步数，声明一个队列toJump记录当前走到的位置，声明一个队列times同步记录走到当前位置需要的步数，首先，将0加入到jumped和times，然后遍历队列toJump按照以下过程处理：

从队列中取出一位cur；

如果cur对应的数组的值为0，则跳过处理下一个队列中的值；

判断toJumpTimes中是否存在该位置的索引，如果存在且走到当前位置的步数多于其他走法走到当前位置的步数，则跳过处理下一个；

如果cur对应的数组的值大于等于length-cur即可以从当前位置直接跳跃到最后一位，则判断如果当前的跳跃次数小于result，则更新result的值；

否则，如果当前跳跃次数不小于result，则跳过处理下一个；如果当前跳跃次数小于result，则将cur+1 ~ cur+nums[cur]索引位添加到toJump，添加之前需要判断toJumpTimes的key中是否存在当前索引位：

如果不存在并且当前跳跃次数小于result，则把当前索引位和相应的跳跃次数添加到toJump和times和toJumpTimes；

如果存在并且当前跳跃次数小于最小的跳跃次数，则把当前索引位和相应的跳跃次数添加到toJump和times，并且更新当前索引位在toJumpTimes中的最少跳跃次数。

最后，返回result即为最少跳跃次数。
【LeetCode-045-跳跃游戏|LeetCode-045-跳跃游戏 II】说明：处理方法类似于 LeetCode-055-跳跃游戏这道题目。

import java.util.*; public class LeetCode_045 { public static int jump(int[] nums) { if (nums.length == 1) { return 0; } if (nums.length == 2) { return 1; } int result = Integer.MAX_VALUE; int length = nums.length - 1; // 定义走到过的位置，并且记录走到当前位置最少的步数 Map toJumpTimes = new HashMap<>(); toJumpTimes.put(0, 0); // 定义当前到的位置 Stack toJump = new Stack<>(); Stack times = new Stack<>(); toJump.push(0); times.push(0); while (!toJump.isEmpty()) { Integer cur = toJump.pop(); Integer curTimes = toJumpTimes.get(cur); if (nums[cur] == 0) { continue; } // 判重，如果走到当前位置的步数多于其他走法走到当前位置的步数，则跳过处理下一个 if (toJumpTimes.containsKey(cur) && curTimes > toJumpTimes.get(cur)) { continue; } if (nums[cur] >= length - cur) { if (curTimes + 1 < result) { result = curTimes + 1; } } else { if (curTimes + 1 >= result) { continue; } for (int i = 1; i <= nums[cur]; i++) { if (!toJumpTimes.containsKey(cur + i)) { if (curTimes + 1 < result) { toJumpTimes.put(cur + i, curTimes + 1); toJump.push(cur + i); times.push(curTimes + 1); } } else { Integer time = toJumpTimes.get(cur + i); if (curTimes + 1 < time) { toJumpTimes.put(cur + i, curTimes + 1); toJump.push(cur + i); times.push(curTimes + 1); } } } } } return result; }public static void main(String[] args) { int[] nums = new int[]{2, 3, 1, 1, 4}; System.out.println(jump(nums)); } }