力扣贪心——跳跃游戏I和II

1 跳跃游戏

利用边界进行判断，核心就是判定边界，边界内所有步数一定是最小的，然后在这个边界里找能到达的最远地方。

1.1 跳跃游戏I

class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int maxDistance = 0;
        int temp = 0;
        for(int i = 0;i < len;i++){
            if(i>maxDistance){
                if(temp<i)
                    return false;
                maxDistance = temp;
            }
            temp = Math.max(i+nums[i],temp);
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.2 跳跃游戏II

设置边界，每次到边界就更新，重点在step遇到边界就更新，然后再到最远距离，每次步数一定+1；

class Solution {
    public int jump(int[] nums) {
        int len = nums.length -1;
        int step = 0;
        int maxn = 0;
        int distance = 0;
        for(int i = 0;i <= len;i++){
            if(i>maxn){
                maxn=distance;
                step++;
            }
            distance = Math.max(distance,i+nums[i]);
        }
        return step;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16