本文共 2013 字，大约阅读时间需要 6 分钟。
问题描述：
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps.For example:
Given array A = [2,3,1,1,4]The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Note:
You can assume that you can always reach the last index.算法设计：
package com.bean.algorithmbasic;public class JumpGameII { public static int jump(int[] nums) { // If nums.length < 2, means that we do not // need to move at all. if (nums == null || nums.length < 2) { return 0; } // First set up current region, which is // from 0 to nums[0]. int l = 0; int r = nums[0]; // Since the length of nums is greater than // 1, we need at least 1 step. int step = 1; // We go through all elements in the region. while (l <= r) { // If the right of current region is greater // than nums.length - 1, that means we are done. if (r >= nums.length - 1) { return step; } // We should know how far can we reach in current // region. int max = Integer.MIN_VALUE; for (; l <= r; l++) { max = Math.max(max, l + nums[l]); } // If we can reach far more in this round, we update // the boundary of current region, and also add a step. if (max > r) { l = r; r = max; step++; } } // We can not finish the job. return -1; } public static void main(String[] args) { // TODO Auto-generated method stub int [] arrayDemo= { 2,3,1,1,4}; int result=jump(arrayDemo); System.out.println("ANSWER is: "+result); }} （完）
转载地址：http://rrvdi.baihongyu.com/