给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2
     从下标为0跳到下标为1的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:

假设你总是可以到达数组的最后一个位置。

 

贪心：curMax当前能走的最大长度，maxNext最终能走的最大长度

TIME:O(N)

SPACE:O(1)

 1 class Solution {
 2     public int jump(int[] nums) {
 3         if(nums.length < 2 || nums==null)return 0;
 4         int curMax = 0;
 5         int maxNext = 0;
 6         int res = 0;
 7         for(int i = 0;i < nums.length - 1;i++){//一定会走到最后，则res多加了一个1，所以让其走到倒数第二个数字停止。
 8             maxNext = Math.max(maxNext,nums[i]+i);
 9             if(i == curMax){
10                 res++;
11                 curMax = maxNext;
12             }
13         }
14         return res;
15     }
16 }

广度优先BFS:

在当前能走的最大长度范围内不断搜索能走的最大长度，一旦超过总长度，返回结果.

TIME:O(N)

SPACE:O(1)

 1 class Solution {
 2     public int jump(int[] nums) {
 3         if(nums.length < 2 || nums==null)return 0;
 4         int curMax = 0;
 5         int maxNext = 0;
 6         int res = 0;
 7         int i = 0;
 8         while(curMax - i + 1 > 0){
 9             res++;
10             for(;i<=curMax;i++){
11                 maxNext=Math.max(maxNext,nums[i]+i);
12                 if(maxNext >= nums.length-1){
13                     return res;
14                 }
15             }
16             curMax = maxNext;
17         }
18         return 0;
19     }
20 }

2019-05-03 20:26:42