贪心算法-跳跃游戏——b

1、题目描述

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

2、问题分析

　　这也是一道跳跃问题，但是这道题的目的是让我们计算跳到最后一个位置的最小跳跃次数。我们一直的是这个数组一定能从第一个位置跳到最后一个位置，但是不同的跳跃情况跳跃的次数是不一样的，怎样能保证跳跃的次数是最少的呢？跳的次数最少其实就是保证尽可能少的跳跃次数也能最后达到数组最后一个位置。

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

3、算法思路

回想第一个跳跃问题情景，我们是保证在遍历整个数组的过程中记录下经过的index[]中能跳到最远位置的值max_index,在jump往后遍历的过程中，只要保证jump的值一直小于或者等于max_index的值，其实就相当于是我们能一直往后跳跃，最后比较jump是不是能跳到index[]数组的最后一个位置。但这里我们稍微转变一下思路就好了：贪心思想（能不跳就尽量不跳，不跳就一直往下走）要想尽可能少的跳跃到最后一个位置，那么我们就保证能不跳跃就不跳跃，实在是往下没办法往下走的情况下就跳跃一次。但这一次跳跃是跳到哪里呢？跳到能保证下一走的距离最远的位置就是最合适的位置。

4、解题代码

package com.baozi.test;

/**
 * @author BaoZi
 * @create 2019-05-14-20:24
 */
public class Solution6 {
    public static void main(String[] args) {
        int[] nums=new int[]{2,3,1,1,4};
        int jump = Solution6.jump(nums);
        System.out.println(jump);
    }

    public static int jump(int[] nums) {
        if (nums.length < 2) {
            return nums.length;
        }
        //前边的边界值已经检测过了，所以这里最少会跳一次
        int jump_min = 1;
        int current_len = nums[0];
        int pre_max_len = nums[0];
        for (int i = 1; i < nums.length; i++) {
            //只有当不能再继续往下走的情况下才会跳一步，而且这一步还要保证能在接下来尽可能走的更远
            if (i > current_len) {
                current_len = pre_max_len;
                jump_min++;
            }
            //当在遍历的过程中，当发现能够跳到更远的位置的时候使用pre_max_len变量记录下更远的位置
            if (pre_max_len < nums[i] + i) {
                pre_max_len = nums[i] + i;
            }
        }
        return jump_min;
    }
}