[leetcode] Jump Game

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.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

 

思路： 从下标i开始，能走到的最远下标为i+A[i],且i~i+A[i]范围内都是可以走到的。所以遍历A,不断更新能走到的最远下标即可。当最终max>=len-1，说明max以及max之前的路径都是可以走到的，即包含在这之内的len-1这一位是可以走到的。

 

 public boolean canJump(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int len = A.length;
        
        int max = 0;//能走到的最远下标
        for(int i = 0;i<=len-1;i++){
                if(i<=max&&i+A[i]>max) max = i+A[i];
        }
        return max>=len-1;
    }

 

 

 

Jump Game IIMar 17 '127347 / 20162

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

 

思路：单源最短路径，类似于BFS, d[i]表示走到下标i的最短路径。

 

 public int jump(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
       int len = A.length;
       int max = 0;
       int [] d = new int[len];
       d[0] = 0;
       
       for(int i = 0;i<len-1;i++){
           if(A[i]>0){
            if(A[i]+i>=len-1) return d[i]+1;
            if(i+A[i]>max){
               for(int j = max+1;j<=A[i]+i;j++)//直接从max+1开始更新即可。因为路径                                               //肯定是以下标递增的方式走的，和图                                                //不同（图没有这种特性）。
                    d[j] = d[i]+1;
               max = i+A[i];
               
            }
           }
       }
      return d[len-1];
        
    }