Leetcode 55. jump game

题目：

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

题意：

       这道题类似于之前一道爬台阶的题，首先会给定输入一个非负整数的数组，每次从数组第一个元素出发，每次可以跳跃前进的步数小于或等于当前所在数组元素的值。 给定数组，输出是否存在走到终点的方案。

 

最初的尝试：

       一开始我准备尝试回溯法，通过层层递归进行寻找，当找到终点时，进行返回。

代码如下：

class Solution {
    public int flag=0;
    public void jump(int[] nums,int index){
        if(this.flag==1) return;
        if(index==(nums.length-1)){
            this.flag=1;
            return;
        }
        else if(index>=nums.length){
            return;
        }
        else{
            for(int j=1;j<=nums[index];j++){
                jump(nums,index+j);
            }
        }
        
    }
    public boolean canJump(int[] nums) {
        for(int i=0;i<=nums[0];i++){
            jump(nums,i);
        }
        if(this.flag==1) return true;
        else return false;
    }
}

但是，这个方法在执行一个很大的用例时超时了，其实也是可以预见的，这种循环递归效率往往是不行的。

 

 

看到大神的解法：只用了六行代码

class Solution {
    
    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;
    }
}

 

理解：

其实这道题就是在找从起始点所能到达的范围，只要点在最远范围内，他就一定可以到达。而不是需要每一步都去精确计算到哪，只需要确立从每一步出发最远能到哪。