Java教程

算法题四(贪心算法)

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

题目:

* 给定一个非负整数数组,你最初位于数组的第一个位置。
*
* 数组中的每个元素代表你在该位置可以跳跃的最大长度。
*
* 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
*
* 假设你总是可以到达数组的最后一个位置。
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;
    }
}

 

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