Leetcode-55-jump game

# LeetCode-55- Jumping game

Given an array of nonnegative integers , You are first in the array .

Each element in the array represents the maximum length you can jump at that location .

Judge whether you can reach the last position .

Example 1：

 Input : [2,3,1,1,4]
 Output : true
 explain :  We can jump first  1  Step , From the position  0  arrive   Location  1,  And then from the position  1  jump  3  Step to the last position .

Copy

Example 2：

 Input : [3,2,1,0,4]
 Output : false
 explain :  No matter what , You will always arrive at the index for  3  The location of . But the maximum jump length for this position is  0 ,  So you can never get to the last place .

Copy

# Their thinking

Method 1、 greedy ：

For any position in the array y, How to judge whether it can reach

According to the meaning , As long as there is one place x, It can be reached by itself , And the maximum length of its jump is x+nums[x], This value >=y, namely x+nums[x]>=y, So location y It can also reach

let me put it another way , For every accessible location x, It makes the x+1,x+2,......,x+nums[x] These continuous positions can reach

So we can record dynamically The farthest you can reach , For each take-off point , Update the corresponding The farthest you can reach

That is, try every point that can take off , Use max Indicates the farthest point that can be reached , exceed max You can't jump , Go straight back

# Java Code

class Solution {
    public boolean canJump(int[] nums) {
        boolean falg = true;
        if(nums.length<2) return falg;
        int max = 0;
        for(int i=0;i<nums.length;i++){
            if(i>max)
                falg = false;
            max = Math.max(max,i+nums[i]);
        }
        return falg;
    }
}

Copy