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.

思路：

　　数组的层次遍历方法

我的代码：

public class Solution {
    public int jump(int[] nums) {
        if(nums==null || nums.length<=1)  return 0;
        int start = 0;
        int end = start+nums[start];
        int level = 1;
        
        while(end < nums.length-1)
        {
            int begin = start+1;
            int tmpEnd = begin;
            while(begin <= end)
            {
                tmpEnd = Math.max(tmpEnd, nums[begin]+begin);
                begin++;
            }
            if(tmpEnd <= end) return 0;
            start = end; 
            end = tmpEnd;
            level++;
        }
        return level;
    }
}

View Code

他人代码：

public class Solution {
    public int jump(int[] A) {
        int[] steps = new int[A.length];
        
        steps[0] = 0;
        for (int i = 1; i < A.length; i++) {
            steps[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (steps[j] != Integer.MAX_VALUE && j + A[j] >= i) {
                    steps[i] = steps[j] + 1;
                    break;
                }
            }
        }
        
        return steps[A.length - 1];
    }
}


// version 2: Greedy
public class Solution {
    public int jump(int[] A) {
        if (A == null || A.length == 0) {
            return -1;
        }
        int start = 0, end = 0, jumps = 0;
        while (end < A.length - 1) {
            jumps++;
            int farthest = end;
            for (int i = start; i <= end; i++) {
                if (A[i] + i > farthest) {
                    farthest = A[i] + i;
                }
            }
            start = end + 1;
            end = farthest;
        }
        return jumps;
    }
}

View Code

学习之处：

数组也可以进行层次遍历啊，基于本题层次遍历的上界是下一层能到达的左界，下界是下一层能到达的右界。