leetCode 45.Jump Game II (跳跃游戏) 解题思路和方法

Jump Game II

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.)

思路：本题是典型的贪心算法。题目难度上也不算难，贪心策略是每步前进的地方是下一步能达到的地方最远。

具体代码例如以下：

public class Solution {
    public int jump(int[] nums) {
    	/**
    	 * 本题用贪心法求解，
    	 * 贪心策略是在每一步可走步长内。走最大前进的步数
    	 */
        if(nums.length <= 1){
            return 0;
        }
        int index,max = 0;
        int step = 0,i= 0;
        while(i < nums.length){
        	//假设能直接一步走到最后，直接步数+1结束
            if(i + nums[i] >= nums.length - 1){
            	step++;
            	break;
            }
            max = 0;//每次都要初始化
            index = i+1;//记录索引。最少前进1步
            for(int j = i+1; j-i <= nums[i];j++){//搜索最大步长内行走最远的那步
                if(max < nums[j] + j-i){
                    max = nums[j] + j-i;//记录最大值
                    index = j;//记录最大值索引
                }
            }
            i = index;//直接走到能走最远的那步
            step++;//步长+1
        }
        return step;
    }
}