「力扣」第 45 题:跳跃游戏 II


「力扣」第 45 题:跳跃游戏 II

提示:这题初学的时候很陌生,一定要多练习,经常拿出来复习一下。

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

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

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

方法一:BFS(超时)

提示:在纸上画出一个「图」结构。

Java 代码:

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Solution {

    public int jump(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return 0;
        }

        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> hashSet = new HashSet<>();

        queue.add(0);
        int target = len - 1;
        int minStep = 0;
        while (!queue.isEmpty()) {
            int currentSize = queue.size();
            for (int i = 0; i < currentSize; i++) {
                Integer head = queue.poll();
                if (head == target) {
                    return minStep;
                }

                for (int j = head + 1; j <= Math.min(head + nums[head], len - 1); j++) {
                    if (hashSet.contains(j)) {
                        continue;
                    }
                    queue.add(j);
                    hashSet.add(j);
                }
            }
            minStep++;
        }
        return minStep;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = new int[]{2, 3, 1, 1, 4};
        int res = solution.jump(nums);
        System.out.println(res);
    }
}

方法二:贪心算法(Greedy)

说明:下面的描述还不够清楚,需要结合代码理解。

  • 贪心不是每一步选择能跳最远的(举反例,就用题目中的例子);
  • 贪心策略是:在下一步能跳的区间里选择最远的下标;

Java 代码:

public class Solution {

    // 贪心算法:类似层序遍历,脑子里要形成一个动画

    public int jump(int[] nums) {
        int len = nums.length;
        if (len < 2){
            return 0;
        }

        // 当前区间的结束下标
        int currentEnd = 0;
        // [0, i) 里能达到的最远下标
        int maxReached = 0;
        int steps = 0;
        for (int i = 0; i < len - 1; i++) {
            maxReached = Math.max(maxReached, i + nums[i]);
            if (i == currentEnd) {
                currentEnd = maxReached;
                steps++;
            }

        }
        return steps;
    }
}

可以多加一个剪枝操作。

Java 代码:

public class Solution {

    public int jump(int[] nums) {
        int len = nums.length;
        if (len < 2){
            return 0;
        }

        int minStep = 0;

        // 上一步能到达的最远位置
        int currentEnd = 0;
        // maxReached 是当前能到达的最远位置
        int maxReached = 0;
        for (int i = 0; i < len - 1; i++) {
            maxReached = Math.max(maxReached , i + nums[i]);

            if (i == currentEnd){
                minStep++;
                currentEnd = maxReached;

                // 这一步可以不要
                if (maxReached >= len - 1){
                    break;
                }
            }
        }
        return minStep;
    }
}

文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「力扣」第 310 题:最小高度树 「力扣」第 310 题:最小高度树
「力扣」第 310 题:最小高度树题解地址:贪心法:根据拓扑排序的思路(Python 代码、Java 代码)。 说明:文本首发在力扣的题解版块,更新也会在第 1 时间在上面的网站中更新,这篇文章只是上面的文章的一个快照,您可以点击上面的链接
下一篇 
「力扣」第 12 题:整数转罗马数字 「力扣」第 12 题:整数转罗马数字
「力扣」第 12 题:整数转罗马数字 链接:12. 整数转罗马数字; 题解:贪心算法(贪心算法的有效性未证明))。 罗马数字包含以下七种字符: I,V, X, L,C,D 和 M。 字符 数值 I
  目录