当前位置：首页 > article >正文

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

article 2024/10/18 12:11:46

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 跳跃游戏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;
    }
}