贪心算法-跳跃问题

一.能否跳跃到最后位置(难度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;
    }

贪心算法专题

贪心算法–计算项目最大收益

贪心算法–安排最多会议次数

贪心算法-分金问题，返回分割最小代价

贪心算法-用最少的灯照亮所有街道

贪心算法-字符串数组能拼接出的最小字典序