关于java:LeetCode045跳跃游戏-II

31次阅读

共计 2146 个字符，预计需要花费 6 分钟才能阅读完成。

题目形容：给定一个非负整数数组，你最后位于数组的第一个地位。

数组中的每个元素代表你在该地位能够跳跃的最大长度。

你的指标是应用起码的跳跃次数达到数组的最初一个地位。

假如你总是能够达到数组的最初一个地位。

示例阐明请见 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));
    }
}