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

桃扇骨 2021-09-21 02:18 286阅读 0赞

跳跃游戏，合计三道题。

# 55. Jump Game #

## 1. 题目 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]

## 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. 运行结果 ##

![在这里插入图片描述][20200118010729572.png]

# 45. Jump Game II #

## 1. 题目 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 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 运行结果 ###

![在这里插入图片描述][20200118010752781.png]

## 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 运行结果 ###

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

![在这里插入图片描述][20200118010814602.png]

# 1306. Jump Game III #

## 1. 题目 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 2]

## 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. 运行结果 ##

![在这里插入图片描述][20200118010834112.png]

# 相关链接 #

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]: /images/20210920/5830a94d17474d569e1fce3dadfc4ac7.png
[20200118010729572.png]: /images/20210920/4260ab0375304abd86aed1d24c4d273b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 1]: /images/20210920/3443ea1043a34618abba25f5a24b58f4.png
[20200118010752781.png]: /images/20210920/a0d231785a1b4b77acc24153ee932ad9.png
[20200118010814602.png]: /images/20210920/0f2ed44bd6d1446596d196705a54226c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 2]: /images/20210920/69f41a16bcfc4350972cba56ae119118.png
[20200118010834112.png]: /images/20210920/5c5b692198e7482fb312b123bc73384d.png
[github_ _ 55. Jump Game]: https://github.com/Parallelline1996/Leetcode/blob/master/Problems/src/main/java/page1/N55_JumpGame.java
[github_ _ 45. Jump Game II]: https://github.com/Parallelline1996/Leetcode/blob/master/Problems/src/main/java/page1/N45_JumpGameII.java
[github_ _ 1306. Jump Game III]: https://github.com/Parallelline1996/Leetcode/blob/master/Problems/src/main/java/page14/N1306_JumpGameIII.java
[LeetCode]: https://blog.csdn.net/applying/category_9629399.html
[LeetCode Top 100 Liked Questions]: https://blog.csdn.net/applying/article/category/9466044