【算法】贪心算法:LeetCode 55 跳跃游戏、LeetCode 45 跳跃游戏 II

LeetCode 55:跳跃游戏

(中等)

题目

描述
给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

示例 1:
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2:
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

思路

可用一个变量 maxIndex 来动态记录当前能到达的最远距离,若最终 maxIndex 大于最后一个数组元素的下标,那么则跳跃成功,而关于如何去动态更新 maxIndex 值,我们可以从 0 开始,到倒数第二个元素(不能遍历到最后一个下标,因为本身问题就是问能否到达最后一个下标,应通过”跳跃“到达,而不是”遍历“到达)结束进行遍历数组,maxIndex 动态更新的结果应为 maxIndex 之前的值,与当前下标加上当前下标可以”跳跃“的最大距离的值,这两者中较大的那一个,而能够继续遍历进行更新的条件是 maxIndex >= 当前遍历的下标,因为只有这样,在贪心算法的局部最优解中考虑才是可行的,即至少到达当前下标的位置是可行的,进而才能最终得出全局最优解,即能否到达最后的下标。

实现

public class TX5跳跃游戏 {
     

    public boolean canJump(int[] nums) {
     
        int maxIndex = 0;
        for (int i = 0; i < nums.length - 1; i++) {
     
            if (maxIndex >= i) {
     
                maxIndex = Math.max(i + nums[i], maxIndex);
            }
        }
        return maxIndex >= nums.length - 1;
    }

    public static void main(String[] args) {
     
        TX5跳跃游戏 s = new TX5跳跃游戏();
        System.out.println("s.canJump(new int[]{2, 3, 1, 1, 4}) = " + s.canJump(new int[]{
     2, 3, 1, 1, 4}));
        System.out.println("s.canJump(new int[]{2, 0, 0}) = " + s.canJump(new int[]{
     2, 0, 0}));
        System.out.println("s.canJump(new int[]{3, 2, 1, 0,4}) = " + s.canJump(new int[]{
     3, 2, 1, 0, 4}));
        System.out.println("s.canJump(new int[]{0, 2, 3}) = " + s.canJump(new int[]{
     0, 2, 3}));

    }
}

【算法】贪心算法:LeetCode 55 跳跃游戏、LeetCode 45 跳跃游戏 II_第1张图片
【算法】贪心算法:LeetCode 55 跳跃游戏、LeetCode 45 跳跃游戏 II_第2张图片

LeetCode 45:跳跃游戏 II

(中等)

题目

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

示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。

示例 2:
输入: nums = [2,3,0,1,4]
输出: 2

思路

此题的要求是在上一题的基础上,“总是可以到达数组的最后一个位置”,因此,我们可以不再考虑无法到达的情况,而可以专心考虑到达最后一个下标至少要几次。

我们还是利用上一题中的关键语句:maxIndex = Math.max(i + nums[i], maxIndex),用于动态更新当前下标 i 及其之前能到达的最远距离,因为下标 i 是在遍历过程中不断变化的,因此 maxIndex 的值,也就是上述语句也要在每次循环时都要执行一次,但是并不是每次执行都需要跳跃一次,这是需要分清楚的,而应该在什么时候跳跃一次呢?注意,因为要求是最小的跳跃次数,因此,我们不到不得已时,就不能去跳跃,而应在迫不得已时,也就是再不跳就没法到终点时才应该进行跳跃,而这个关键的时间点,就是:i == farIndex,即当前下标,已经等于上次记录的最远下标时,这时候就不得不去跳跃了,并且,这个跳跃的距离,应该也是从贪心的局部最优解角度去考虑,应该尽可能跳得远,而具体应该跳多远呢?这时候我们之前用于动态记录当前下标 i 及其之前能到达的最远距离的变量 maxIndex 就可以发挥作用了,同时,我们令 farIndex = maxIndex,并记录一次跳跃次数,这样,最终,我们在过程中满足了局部最优解:不得不跳时才跳,若要是跳,就应该往可行的最远处跳,因此,在全局上,就可以满足全局最优解:使用最少的跳跃次数到达数组的最后一个位置。

实现

public class TX6跳跃游戏II {
     

    public int jump(int[] nums) {
     
        int maxIndex = 0;
        int farIndex = 0;
        int count = 0;
        for (int i = 0; i < nums.length - 1; i++) {
     
            maxIndex = Math.max(i + nums[i], maxIndex);
            
			if (maxIndex == nums.length - 1) {
     
				return count + 1;
            }

            if (i == farIndex) {
     
                farIndex = maxIndex;
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
     
        TX6跳跃游戏II s = new TX6跳跃游戏II();
        System.out.println("s.canJump(new int[]{2, 3, 1, 1, 4}) = " + s.jump(new int[]{
     2, 3, 1, 1, 4}));
        System.out.println("s.canJump(new int[]{2, 3, 0, 1, 4}) = " + s.jump(new int[]{
     2, 3, 0, 1, 4}));
        System.out.println("s.canJump(new int[]{2, 0, 0}) = " + s.jump(new int[]{
     2, 0, 0}));

    }
}

【算法】贪心算法:LeetCode 55 跳跃游戏、LeetCode 45 跳跃游戏 II_第3张图片
【算法】贪心算法:LeetCode 55 跳跃游戏、LeetCode 45 跳跃游戏 II_第4张图片

你可能感兴趣的