题目链接： https://leetcode.com/problems/jump-game/

1. 题目介绍（Jump Game）

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

【Translate】: 给你一个整数数组nums。初始位置是数组的第一个索引，数组中的每个元素表示在该位置的最大跳转长度。

Return true if you can reach the last index, or false otherwise.

【Translate】: 如果您能到达最后一个索引，则返回true，否则返回false。

【测试用例】：

【约束】：

2. 题解

2.1 贪心 – O(n)

原题解来自于hllowrld的 6 line java solution in O(n)。解题思路就是通过贪心的思想，找到当前的最大一跳，并判断当前的最大跳数是否能够到达下一目标，如果不行，则返回false.

    public boolean canJump(int[] nums) {
        int reachable = 0;
        for (int i=0; i<nums.length; ++i) {
            if (i > reachable) return false;
            reachable = Math.max(reachable, i + nums[i]);
        }
        return true;
    }
1
2
3
4
5
6
7
8

2.2 倒序遍历

原题解来自于mlblount45的 Java 98% Percentile Solution。通过倒序检查元素，每当元素为0时，判断是否可以跳过，不能则返回false，能则下一跳。

public class Solution {
    public boolean canJump(int[] nums) {
       if(nums.length < 2) return true;
       
       for(int curr = nums.length-2; curr>=0;curr--){
           if(nums[curr] == 0){
               int neededJumps = 1;
               while(neededJumps > nums[curr]){
                   neededJumps++;
                   curr--;
                   if(curr < 0) return false;
               }
           }
       }
       return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17