摘要：
给定一个非负整数数组，你最初位于数组的第一个位置。你的目标是使用最少的跳跃次数到达数组的最后一个位置。示例:输入:[2,3,1,1,4]输出:2解释:跳到最后一个位置的最小跳跃数是2从下标为0跳到下标为1的位置，跳1步，然后跳3步到达数组的最后一个位置。8maxNext=Math.max;9if{10res++;11curMax=maxNext;12}13}14returnres;15}16}广度优先BFS:在当前能走的最大长度范围内不断搜索能走的最大长度，一旦超过总长度，返回结果.TIME:OSPACE:O1classSolution{2publicintjump{3ifreturn0;4intcurMax=0;5intmaxNext=0;6intres=0;7inti=0;8while{9res++;10for{11maxNext=Math.max;12if{13returnres;14}15}16curMax=maxNext;17}18return0;19}20}2019-05-0320:26:42
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2
从下标为0跳到下标为1的位置，跳1步，然后跳3步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
贪心：curMax当前能走的最大长度，maxNext最终能走的最大长度
TIME:O(N)
SPACE:O(1)
1 classSolution { 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 returnres; 15 } 16 }
广度优先BFS:
在当前能走的最大长度范围内不断搜索能走的最大长度，一旦超过总长度，返回结果.
TIME:O(N)
SPACE:O(1)
1 classSolution { 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 returnres; 14 } 15 } 16 curMax =maxNext; 17 } 18 return 0; 19 } 20 }
2019-05-0320:26:42