跳跃游戏 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-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<Integer, Integer> toJumpTimes = new HashMap<>(); toJumpTimes.put(0, 0); // 定义以后到的地位 Stack<Integer> toJump = new Stack<>(); Stack<Integer> 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)); }}【每日寄语】 要铭记在心：每天都是一年中最美妙的日子。