hot100-跳跃游戏

跳跃游戏

题目描述：

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

思路：

一开始的做法是深度优先加回溯，但是无法通过最后一个案例，超过时间限制

看了题解才反应过来可以直接贪心或是回溯，即遍历数组更新能跳到的最远的地方，当最远达到最后一个下标返回true，若在某一个地方无法继续跳，返回false

代码：

//深度优先加回溯的代码
 //static boolean flag = false;
//    public static boolean canJump(int[] nums) {
//
//        fun(0,nums);
//        return flag;
//    }
//
//    public static void fun(int cur,int[] nums){
//        if(flag == true)return;
//        if(cur== nums.length-1){
//            flag = true;
//            return;
//        }
//        if(nums[cur]==0)return;
//        for (int i = Math.min(nums[cur],nums.length-1-cur);i>0; i--) {
//
//            fun(cur+i,nums);
//        }
//    }

    public static boolean canJump(int[] nums) {
        int len = 0;
        for (int i = 0; i < nums.length; i++) {
            len = Math.max(len,i + nums[i]);
            if(len>= nums.length-1)return true;
            if(len==i&&nums[i]==0)return false;
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30