本文主要是介绍算法题四（贪心算法），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：

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

public class MyJump {
    public static void main(String[] args) {
        int[] nums = {1, 1, 2, 3, 5, 6, 2, 5, 1, 1, 1, 8};
        int jump = jump(nums);
        System.err.println(jump);
    }

    /**
     * 我们的目标是到达数组的最后一个位置，因此我们可以考虑最后一步跳跃前所在的位置，该位置通 
       过跳跃能够到达最后一个位置。
     * 找到最后一步跳跃前所在的位置之后，我们继续贪心地寻找倒数第二步跳跃前所在的位置，以此类 
       推，直到找到数组的开始位置。
     * @param nums
     * @return
     */
    public static int jump(int[] nums) {
        int index = nums.length-1;//记录要跳跃位置的下标
        int a = nums.length - 1;//用于从跳跃位置进行遍历
        int count = 0;//记录跳跃的次数
        while (index > 0) {
            for (int i = a; i >= 0; i--) {
                //如果元素可以跳到该位置就就将该位置赋值给index，直到找到值最大的那个元素，并把那个下标赋值给index，
                if (nums[i] >= a - i) {
                    index = i;
                }
            }
            //将index赋值给a,下次遍历就从该位置往前找，找下一个最大值
            a = index;
            count++;
        }

        return count;
    }
}

这篇关于算法题四（贪心算法）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！