每日一题-贪心算法

目录

跳跃游戏

跳跃游戏Ⅱ

跳跃游戏

• 时间：0802
• 题目

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

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

• 思路
  • 只要能够抵达当前的位置，就更新能抵达的最远值，因为题目是判断是否能够到达最后一个下标，每个能到达的下标位置都跳到最远能够抵达的下标，实时更新reach，reach就会有两种结束的情况：
    • 第一种：reach也就是当前能够跳到的最大值，都达不到i的话，证明怎么跳都跳不到终点
    • 第二种：reach >= n-1，证明能够到达最后一个下标的位置，因为能够抵达最远的地方已经超过了终点
• 代码

class Solution {
    public boolean canJump(int[] nums) {
        // 贪心算法 夸夸就是跳
        if(nums == null || nums.length == 0)
            return false;
        int reach = 0;
        int n = nums.length;
        for(int i = 0; i < nums.length; i ++){
            if(reach < i || reach >= n - 1)
                break;
            reach = Math.max(reach, i + nums[i]);
        }
        return reach >= n - 1;
    }
}

跳跃游戏Ⅱ

• 时间：0803
• 题目

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

• 思路
  • 和上面的想法一致，以最少的步数到达终点，自然是每一步跨越的都是当前能够抵达的最远位置
  • 当前跳到的位置小于遍历数组的下标，就说明该跳了；跳的目的地下标就是当前能够到达最远位置的下标
  • 当前能够抵达最远位置的下标肯定超过当前的下标，否则肯定就跳不到终点了呀
• 代码

class Solution {
    public int jump(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;
        int jump = 0;
        int next = 0, cur = 0;
        for(int i = 0; i < nums.length; i ++){
            //当前抵达的点小于下标，就要跳了
            if(cur < i){
                jump ++;
                cur = next; //cur更新为当前能跳到的最大值 多跳一次
            }
            //next当前能跳到的最大值
            next = Math.max(next, i + nums[i]);
        }
        return jump;
    }
}