【Hot100】LeetCode—45. 跳跃游戏 II

题目

• 原题连接：45. 跳跃游戏 II

1- 思路

思路

• 跳跃游戏——>贪心
  • 借助 curCover 记录当前覆盖范围、nextCover 记录下一次的覆盖范围
  • ① 遍历数组，如果 i 等于当前的覆盖范围，且 i 未到达终点——> 此时 res++，更新 nowCover

2- 实现

⭐45. 跳跃游戏 II——题解思路

class Solution {
    public int jump(int[] nums) {
        // 1.数据结构
        int res = 0;
        int nowCover = 0;
        int nextCover = 0;
        
        // 遍历 nums
        for(int i = 0 ; i < nums.length;i++){
            nextCover = Math.max(nextCover,nums[i]+i);
            if( i == nowCover){
                if(nowCover!=nums.length-1){
                    res++;
                    nowCover = nextCover;
                }
            }
        }
        return res;
    }
}

3- ACM 实现

public class jumpGame {

    public static int jump(int[] nums){
        //1. 数据结构
        int res = 0;
        int nowCover = 0;
        int nextCover = 0;

        for(int i = 0 ; i < nums.length;i++){
            nextCover = Math.max(nextCover,i+nums[i]);
            if(i==nowCover){
                if(nowCover!=nums.length-1){
                    res++;
                    nowCover = nextCover;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入数组长度n");
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n;i++){
            nums[i] = sc.nextInt();
        }
        System.out.println("最小跳为"+jump(nums));
    }
}