My code:
public class Solution {
public boolean canJump(int[] nums) {
if (nums == null)
return false;
if (nums.length == 0)
return false;
if (nums.length == 1)
return true;
boolean[] canJump = new boolean[nums.length];
canJump[nums.length - 1] = true;
for (int i = nums.length - 2; i >= 0; i--)
canJump(i, canJump, nums);
return canJump[0];
}
private void canJump(int index, boolean[] canJump, int[]nums) {
int minIndex = getMinIndex(index + 1, index + nums[index], canJump, nums);
if (nums[index] >= minIndex - index)
canJump[index] = true;
}
private int getMinIndex(int begin, int end, boolean[] canJump, int[] nums) {
int range = 0;
if (end < nums.length)
range = end;
else
range = nums.length;
int minIndex = nums.length - 1;
int i = begin;
while(i < range + 1) {
if (canJump[i] == false) {
i = i + nums[i] + 1;
}
else {
minIndex = i;
break;
}
}
return minIndex;
}
public static void main(String[] args) {
Solution test = new Solution();
int[] a = {3, 2, 1, 0, 4};
System.out.println(test.canJump(a));
}
}
My test result:
这次的作业如果第一次做这个类型，还是会感觉到比较难的。但之前做过一个叫做 Word Break 的题目，所以对这个题目也就有了差不多的思路。
首先肯定不能一个个找。
所以得设置一个标志位数组，来避免重复搜索。
这里有两个优化。
1.一开始的数组都是false，除了最后一位是true。
假设从某个index开始，要判断这个index能不能到达末尾，若能到达，则布尔数组中该位为T，否则为F。
那么，能够到达末尾的无非以下这种情况。
通过途中的某个点，多个点，最后跳到末尾。
这种情况可以细分为多种具体的情况，深入进去会很复杂。但不要忘了我们的目的是什么。我们的目的是，判断能不能到末尾。既然判断能到末尾这么复杂，那么，我们就来判断，不能到末尾。
不能到末尾，只有一种情况，如果满足了，那就为F。
那就是，距离该index最近的T，其index在该index所能跳到的范围之内。只要能跳到这个T，之后就会按照之前的扫描结果到达末尾，一定能到达末尾，所以不用再重复扫描了。
所以，第一个优化是，限定搜索的范围在[index + 1, index + nums[index]]，只要在这个范围内有T，那么canJump[index] = true;
2.然后这样我就很开心了，提交。发现还是超时了。所以，还能优化。还能减少扫描次数。
那么，我到底哪里又重复扫描了呢？
我仔细想了下，发现如下。
比如我在index处，然后对[index + 1, index + nums[index]] 进行搜索。
我第一个先对 index + 1搜索，发现他是F，于是我前进道 index + 2,发现他是F，于是继续前进道index + 3.....直到 index + nums[index].
那么，当我在index + 1 发现为F时，我还有没有必要搜索index + 2 呢?
我仔细思考了下，发现，在之前，我位于 index + 1， 即 index = index + 1 的时候，我其实已经搜索过了index + 2, 发现它是F，于是继续往前。
那么，当我位于index的时候，我查过了index + 1是F，那么，
在 index + 1专属的范围内 [index + 1 + 1, index + 1 + nums[index + 1]],一定全部是F。我就不用再次搜索了。于是 index直接跳到index + 1 专属范围之外。
即 index = index + 1 + nums[index + 1] + 1; 开启下一段旅程。
这就是第二个优化。
然后，就测试通过了。
**
总结：
标志位数组对于这种数组内搜索，是很有效果的。自己这方面的思维还要继续培养。
这就是贪婪算法的思想。我不知道怎么表述，保证每一步走的都很稳，都是有理有据的。然后，最后结果就是我们要的了。
**
之前和一个在美国读大四的同学交流了下。没想到他们的computer architecture上的那么硬，这还只是一个美国二流的大学。不得不感叹，英国的工程类教育的确学习压力太小了。学工程，去美国。
今天，睡一觉之后就要考模电了。。。我竟然作死得写了一道题目。只不过挺快乐的。
希望家里可以好。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public boolean canJump(int[] nums) {
if (nums == null || nums.length == 0)
return false;
if (nums.length == 1 && nums[0] == 0)
return true;
int begin = 0;
int end = 0;
int maxLoc = 0;
while (end < nums.length) {
if (nums[end] == 0) {
int zeroEnd = end + 1;
while (zeroEnd < nums.length && nums[zeroEnd] == 0)
zeroEnd++;
zeroEnd = zeroEnd - 1; // zero in [i, zeroEnd]
if (maxLoc <= zeroEnd)
return false;
begin = zeroEnd + 1;
end = zeroEnd + 1;
}
else {
maxLoc = Math.max(maxLoc, end + nums[end]);
if (maxLoc >= nums.length - 1)
break;
end++;
}
}
return true;
}
}
这是我这次用的方法，然后看了网上的答案，其实和我差不多。也是找0看看能不能过得去，但是他没有把连续的0一次性处理，而是遍历。
我是利用滑动一次性处理了。
参考网址：
http://www.programcreek.com/2014/03/leetcode-jump-game-java/
我看我以前的做法，还是挺有意思的。DP
Anyway, Good luck, Richardo!
My code:
public class Solution {
public boolean canJump(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
else if (nums.length == 1) {
return true;
}
int maxIndex = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
if (maxIndex > i) {
continue;
}
else {
return false;
}
}
else {
maxIndex = Math.max(maxIndex, i + nums[i]);
if (maxIndex >= nums.length - 1) {
return true;
}
}
}
return true;
}
}
现在想来，算是比较简单的题目了。
参考：
This is a dynamic programming[1]
question. Usually, solving and fully understanding a dynamic programming problem is a 4 step process:
Start with the recursive backtracking solution
Optimize by using a memoization table (top-down[3]
dynamic programming)
Remove the need for recursion (bottom-up dynamic programming)
Apply final tricks to reduce the time / memory complexity
All solutions presented below produce the correct result, but they differ in run time and memory requirements.
https://leetcode.com/articles/jump-game/
Anyway, Good luck, Richardo! -- 09/03/2016
