贪心算法-跳跃游戏问题（java）-Toy模板网

这篇具有很好参考价值的文章主要介绍了贪心算法-跳跃游戏问题（java）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

贪心算法-跳跃问题

一.能否跳跃到最后位置(难度Medium)

1.1 题目描述

输入是一个非负整数数组nums,数组元素nums[i]代表你站的位置i最多能够向前跳几步。现在你站的第一个位置nums[0],请问能否跳到最后一个位置。
举例：
nums = [2,3,1,1,4] 这个就可以跳到最后，返回true
nums = [3,2,1,0,4]这个就无法跳到最后，返回false

1.2解题思路：

我们每次来到一个位置，就计算出当前能跳到的最远位置，我们每次和上一步能跳到的最远位置进行比较，比较出能跳到的最远位置，碰到跳不动时，还没到最后一个位置，就认为跳不到最后一个位置。如果能跳到的最远距离大于最后一个位置的距离，就能跳到，这样就很容易代码里写出来了。

1.3 代码演示

 /**
     * 能否跳到最后一个位置。
     * @param arr
     * @return
     */
    public static boolean jump(int[]arr){
        int fast = 0;
        for (int i = 0; i < arr.length - 1;i++){
            //每一个位置都比较出能到的最远距离
            fast = Math.max(fast,i + arr[i]);
            //能到最后一个位置，就直接返回true
            if (fast >= arr.length - 1){
                return true;
            }
            //碰到0 就跳不动了
            if (fast <= i){
                return false;
            }
        }
        return fast >= arr.length - 1;
    }

二.跳到最后位置最少要跳几次(难度hard)

2.1 解题思路

每一步我们计算出能到的最远距离。在到达最远距离前，我们每一步去更新能到的最远距离。一直走最优的状态，就能保证以最少的步数走到最后一位。

2.2 代码演示

 /**
     * 最少走几步
     * @param arr
     * @return
     */
    public static int minJump(int[]arr){
        if (arr == null || arr.length == 0){
            return 0;
        }
        int jump = 0;
        int farthest = 0;
        //当前这一步能走到的最远距离
        int end = 0;
        for (int i = 0; i < arr.length - 1;i++){
            //更新能到的最远距离
            farthest = Math.max(farthest,i + arr[i]);
            //到达最远距离之前要选择走下一步。步数加一
            if (end == i){
                jump++;
                end = farthest;
            }
            //如果無法跳到最後,返回-1
            if (farthest <= i){
                return -1;
            }

        }
        return jump;
    }