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

Leetcode 45-跳跃游戏 II

article 2024/9/29 3:14:45

题解

法一找当前可跳到最远的起始位置（贪心法）

局部最优： 当前覆盖范围内尽选可到达最远的一步，如果还没到终点，步数再加一。
整体最优： 一步尽可能多走，从而达到最少步数。

本题和55题不同，55题只需在当前可覆盖范围内找到可覆盖的最远的位置，相当于可以不断跳跃，不断更新最大覆盖范围，最后得到整体最大覆盖范围，看是否能到终点。
本题为了尽可能减少跳跃步数，不能每次跳跃，本题只在找到当前可覆盖范围内可跳跃最远的一个位置i作为下一步的起点开始跳跃，并更新下一步可覆盖的范围。这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。
如果到达当前这一步的最大覆盖最远距离(curCover)还没有到终点的话，那么就必须再走一步（step++,curCover=nextCover）来增加覆盖范围。如何更新下一步可覆盖的范围？遍历i到curCover，通过选择最大的（i+nums[i]）不断更新nextCover和curCover。
图片转载自代码随想录

//贪心解法：跳的步数尽可能少-->每一步跳的距离尽可能远
//局部贪心：在当前能覆盖的区域里选择下一步的起始位置，下一步覆盖的距离要尽可能远
//step什么时候更新？到达当前这一步覆盖的边界的时候+1
class Solution {
    public int jump(int[] nums) {
        //走0步时覆盖范围为0
        int curCover=0;
        int nextCover=nums[0];
        int step=0;
        for(int i=0;i<nums.length;i++){
            if(curCover>=nums.length-1) break;
            //更新下一步可覆盖的区域边界
            nextCover=Math.max(nextCover,i+nums[i]);
            //到达当前这一步覆盖的边界的时候,step必须+1，curCover=nextCover
            if(i==curCover){
                step++;
                curCover=nextCover;
            }
        }
        return step;
    }
}

法二找可到达终点的最靠前的位置（贪心法）

知道最终要到达最后一个位置，然后我们找前一个位置，遍历数组，找到能到达它的位置，离它最远的就是要找的位置。然后继续找上上个位置，最后到了第 0 个位置就结束了。

至于离它最远的位置，其实我们从左到右遍历数组，第一个满足的位置就是我们要找的
图片转载自windliang
在这里插入图片描述

//从后往前找可以到达nums.length-1位置的最靠前的数
//怎么找最靠前的数？从前往后遍历到的第一个能到达nums.length-1的数即为最靠前的数
//找到了以后更新需要到达的数（position=nums.length-1-->position=找到的位置i），且step++,循环往复
//贪心法里面经常用到的一个手法，更新待循环的数组范围
class Solution {
    public int jump(int[] nums) {
        int position=nums.length-1;
        int step=0;
        while(position>0){
            for(int i=0;i<position;i++){
                if(nums[i]+i>=position){
                        step++;
                        //将当前的i置为下次跳转需要到达的点
                        position=i;
                        //这一步使得此轮循环结束，下一轮的遍历起点还是0，遍历目标是找到i使得nums[i]+i>position
                 }
                if(position==0) break;
            }
        }
       
        return step;
    }
}

法三暴力搜索（动态规划）

dp[i]：能跳到该数组需要的最小步数
通过dp[i+count]=Math.min(dp[i]+1,dp[i+count])更新到达dp[i+count]的最小步数

//dp[i]：能跳到该数组需要的最小步数
//dp[i+count]=Math.min(dp[i]+1,dp[i+count]) count<=nums[i]
class Solution {
    public int jump(int[] nums) {
        int[] dp=new int[nums.length];
        for(int i=0;i<nums.length;i++){
            dp[i]=Integer.MAX_VALUE;
        }
        //初始化
        dp[0]=0;
        for(int i=0;i<nums.length;i++){
            int count=nums[i];
            while(count>0&&dp[i]!=Integer.MAX_VALUE){
                if(dp[nums.length-1]!=Integer.MAX_VALUE) return dp[nums.length-1];
                if(i+count<nums.length) dp[i+count]=Math.min(dp[i]+1,dp[i+count]);
                count--;
            }
        }
        return dp[nums.length-1];
    }
}