【LeetCode 45 55 1306】Jump Game I，II，III【JAVA】

跳跃游戏，合计三道题。

55. Jump Game

1. 题目

2. 思路

这道题即考虑是否达到最后的一个位置，我们可以通过到达每一个下标处时，维护一个可达最大下标值，判断我们能否到达数组的最后一个下标。

3. 代码

    public boolean canJump(int[] nums) {int maxIndex = 0;for (int i = 0; i < nums.length; i++) {// 可达最大下标值大于当前遍历的下标值，则说明该下标无法被到达if (maxIndex < i) {return false;}// 更新可达最大下标值maxIndex = Math.max(maxIndex, i + nums[i]);// 可达最大下标值不小于数组最大下标值，则说明可以到达最后一个位置if (maxIndex >= nums.length - 1) {return true;}}return false;}

4. 运行结果

45. Jump Game II

1. 题目

2. 方法一

2.1 思路

该题目与上一道题的区别在于这个是求最少几次可以到达，一个比较笨的方法是，我们可以维护一个数组来记录到达每一个下标的最少次数，从头往后遍历每一个下标，更新从该下标能到达的位置的最少次数，最终来算出数组最后一个位置最少几次可以到达。该思路需要一个额外的数组，空间复杂度为o(n)，而时间上，需要从头到尾遍历一次，同时每个节点又需要更新其能到达的下标位置的值，因此时间复杂度为O(n?)

2.2 代码

   public int jump(int[] nums) {int[] dp = new int[nums.length];for (int i = 1; i < nums.length; i++) {dp[i] = Integer.MAX_VALUE;}for (int i = 0; i < nums.length; i++) {for (int j = 1; j <= nums[i] && i + j < nums.length; j++) {dp[i + j] = Math.min(dp[i + j], dp[i] + 1);}}return dp[nums.length - 1];}

2.3 运行结果

3. 方法二

3.1 思路

上面的方法一思路简单，但是时间复杂度比较高，我们考虑其他做法。
我们可以联想Jump Game的第一题，第一题是问我们能否到达最后一个下标，即我们其实也是求了我们能到达最大下标处，那我们是不是也可以将这道题这么考虑：我们需要求出最少几步才能到达数组的末尾，即我们可以通过求第n步最远能到达哪里来进行判断，即思路变为求每增加一步时，我们可以到达的下标位置是多少，是否已经到达了数组的末尾。这种思路只需要遍历一次数组，空间复杂度为O(n)。

3.2 代码

    public int jump1(int[] nums) {// 跳跃的步数int steps = 0;// 当前步数可到达的最大下标int maxIndex = 0;// 增加一步可以到达的最大下标int nextIndex = nums[0];for (int i = 0; i < nums.length; i++) {// 当前遍历的下标值已经超过了当前步数可达的最大下标if (i > maxIndex) {steps++;if (nextIndex >= nums.length - 1) {break;} else {maxIndex = nextIndex;}}// 更新下一步能到达最大下标nextIndex = Math.max(nextIndex, i + nums[i]);}return steps;}

3.3 运行结果

可以看到所需时间远远小于方法一。

1306. Jump Game III

1. 题目

2. 思路

这道题比较有意思，判断的是从数组的某个下标开始，能否最终到达元素值为0的下标处。这种题目，很容易联想到递归的思路。

3. 代码

    private HashSet<Integer> set = new HashSet<>();public boolean canReach(int[] arr, int index) {// set中已有该下标，则说明出现循环，退出if (index < 0 || index > arr.length - 1 || set.contains(index)) {return false;}set.add(index);// 判断该点是否为下标值为0的地方，或者index + arr[index]跟index - arr[index] 是否为下标值为0的地方if (arr[index] == 0 || canReach(arr, index + arr[index]) || canReach(arr, index - arr[index])) {return true;}set.remove(index);return false;}

4. 运行结果

相关链接

本题代码的github链接 —— 55. Jump Game
本题代码的github链接 —— 45. Jump Game II
本题代码的github链接 —— 1306. Jump Game III
其他 LeetCode 题目
LeetCode Top 100 Liked Questions 题目