My code:
public class Solution {
public int jump(int[] nums) {
if (nums == null || nums.length == 0)
return -1;
int[] steps = new int[nums.length];
for (int i = 0; i < steps.length; i++)
steps[i] = Integer.MAX_VALUE;
steps[0] = 0;
for (int i = 1; i < nums.length; i++) {
steps[i] = steps[i - 1] + 1;
for (int j = i - 1; j >= 0; j--) {
if (steps[i - 1] - steps[j] == 0)
continue;
if (steps[i - 1] - steps[j] > 1)
break;
if (j + nums[j] >= i) {
steps[i] = Math.min(steps[i], steps[j] + 1);
}
}
}
return steps[steps.length - 1];
}
}
这个是我自己写的代码，是超时的，没过测试。
我得思路是，DP。用数组 steps，记录下到每个index的最小的step，最后返回
steps[steps.length - 1]
到达某个index = i 时，该处的steps最大为, steps[i - 1] + 1
最小为， steps[i - 1]
因为steps数组一定是递增类型发展的。
然后就可以实现了。
但是依然是超时。
看了网上的代码，自己实现如下：
public class Solution {
public int jump(int[] nums) {
if (nums == null || nums.length == 0)
return -1;
if (nums.length == 1)
return 0;
int steps = 0;
int lastLocation = 0; // the last maximum location it can reach. If there is one location it cannot reach, update it as // maxLocation, and increase steps by 1
int maxLocation = 0; // the maximum location it can reach at current time. Update it all the time
for (int i = 0; i <= maxLocation && i < nums.length; i++) {
if (lastLocation < i) { // it cannot reach current i, so update it and increase steps by 1
lastLocation = maxLocation;
steps++;
}
maxLocation = Math.max(maxLocation, nums[i] + i); // update maximum location
}
if (maxLocation < nums.length - 1) { // it means it cannot jump to the end, return -1
return -1;
}
return steps;
}
}
其实就是两个变量，last， max 的演绎。
lastLocation 表示的是，当前这个步数所能到达的最大的位置处。
然后如果 i > lastLocation， 说明了，当前所能到达的最大位置也不能到达该 i 所在的位置。所以必须要更新lastLocation 为多走一步后所能到达的最大的位置处。
这里不用担心maxLocation仍然小于 i， 这是不可能的。
首先题目假设一定可以jump to the end， 所以不可能小于i
其次，for 循环中保证了 i <= maxLocation
所以，这道题木，相当于让 i 一直走。
记录下当前步数所能到达的最大位置。假设是lastLocation
那么，当 i 在 [0, lastLocation] 里面行走时， steps都是这个值。
但是在这段区域中，我不断更新下一步，即 steps + 1 步中，所能走到的最大位置，
maxLocation.
然后，当 i 超出lastLocation的时刻时，立即把下一步所能走到的最大位置更新给lastLocation， 同时更新steps
That's all.
参考网页：
http://www.programcreek.com/2014/06/leetcode-jump-game-ii-java/
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int jump(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
else if (nums.length == 1) {
return 0;
}
int maxReach = nums[0];
int minStep = 0;
int edge = 0;
for (int i = 1; i < nums.length; i++) {
if (i > edge) {
minStep++;
edge = maxReach;
if (edge >= nums.length - 1) {
return minStep;
}
}
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach == i) {
return -1;
}
}
return minStep;
}
}
reference:
https://discuss.leetcode.com/topic/4069/sharing-my-ac-java-solution
看的答案。的确是巧妙。想不到。
Anyway, Good luck, Richardo! -- 09/04/2016
