JumpGame [source code]
public class JumpGame {
static
/******************************************************************************/
class Solution {
public boolean canJump(int[] nums) {
if (nums.length == 0)
return false;
if (nums.length == 1)
return true;
if (nums.length == 2)
return nums[0] > 0;
int N = nums.length,next_reachable_idx = N - 1;
for (int i = N - 1; i >= 0; i--) {
if (i + nums[i] >= next_reachable_idx) {
next_reachable_idx = i;
}
}
return next_reachable_idx == 0;
}
}
/******************************************************************************/
public static void main(String[] args) {
JumpGame.Solution tester = new JumpGame.Solution();
int[][] inputs = {
{2,3,1,1,4}, {1},
{3,2,1,0,4}, {0},
};
for (int i = 0; i < inputs.length / 2; i++) {
int[] nums = inputs[2 * i];
boolean ans = inputs[2 * i + 1][0] > 0;
System.out.println (Printer.separator ());
boolean output = tester.canJump (nums);
System.out.printf ("[%s] -> %s, expected: %b\n",
Printer.array (nums), Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
);
}
}
}
大概扫了一下题目意思, 好像有点意思;
思考了一下, 只能想到一个N^2的DP解法; 但是这里既然tag说是greedy, 估计是有greedy的O(N)解法; 这个解法很直接, 直接从end开始往左边走, 然后考虑root level decision就行了, 有点想LIS问题;
笔算了一下, 好像greedy算法可能和0的位置有关系; 假如没有0, 那么最后是肯定可以走到end的;
想不通, 直接N^2解法了;
写的这个算法:
class Solution {
public boolean canJump(int[] nums) {
if (nums.length == 0)
return false;
if (nums.length == 1)
return true;
if (nums.length == 2)
return nums[0] > 0;
int N = nums.length;
boolean[] can_reach_end = new boolean[N];
can_reach_end[N - 1] = true;
for (int i = N - 2; i >= 0; i--) {
boolean success = false;
for (int j = i + 1; j < N && j - i <= nums[i]; j++)
success = success || can_reach_end[j];
can_reach_end[i] = success;
}
return can_reach_end[0];
}
}
果不其然, TLE了, 看来这题就是要求O(N), 那我想不出来了, 直接看答案了;
上面最后是模仿editorial写出来的一个算法, 速度是8ms (58%). 虽然回头想想, 这个算法虽然是有点greedy的意思, 并不是一个真正的greedy? 而且这个算法也不是最intuitive的一个算法; 严格来说其实是从N^2思路思考优化才得到的;
editorial
Approach #1 (Backtracking) [Stack Overflow]
This is the inefficient solution where we try every single jump pattern that takes us from the first position to the last. We start from the first position and jump to every index that is reachable. We repeat the process until last index is reached. When stuck, backtrack.
public class Solution {
public boolean canJumpFromPosition(int position, int[] nums) {
if (position == nums.length - 1) {
return true;
}
int furthestJump = Math.min(position + nums[position], nums.length - 1);
for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
if (canJumpFromPosition(nextPosition, nums)) {
return true;
}
}
return false;
}
public boolean canJump(int[] nums) {
return canJumpFromPosition(0, nums);
}
}
One quick optimization we can do for the code above is to check the nextPosition from right to left. The theoretical worst case performance is the same, but in practice, for silly examples, the code might run faster. Intuitively, this means we always try to make the biggest jump such that we reach the end as soon as possible
反正最后是指数级别的复杂度;
Approach #2 (Dynamic Programming Top-down) [Stack Overflow]
enum Index {
GOOD, BAD, UNKNOWN
}
public class Solution {
Index[] memo;
public boolean canJumpFromPosition(int position, int[] nums) {
if (memo[position] != Index.UNKNOWN) {
return memo[position] == Index.GOOD ? true : false;
}
int furthestJump = Math.min(position + nums[position], nums.length - 1);
for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
if (canJumpFromPosition(nextPosition, nums)) {
memo[position] = Index.GOOD;
return true;
}
}
memo[position] = Index.BAD;
return false;
}
public boolean canJump(int[] nums) {
memo = new Index[nums.length];
for (int i = 0; i < memo.length; i++) {
memo[i] = Index.UNKNOWN;
}
memo[memo.length - 1] = Index.GOOD;
return canJumpFromPosition(0, nums);
}
}
大概看了一下, 反正是一个从左到右的类似DFS的搜索过程;
往下翻了一下, 这个editorial也是瓜批, 一堆由浅入深的DP解法, 一通分析, 没一个AC的;
Approach #3 (Dynamic Programming Bottom-up) [Time limit exceeded]
enum Index {
GOOD, BAD, UNKNOWN
}
public class Solution {
public boolean canJump(int[] nums) {
Index[] memo = new Index[nums.length];
for (int i = 0; i < memo.length; i++) {
memo[i] = Index.UNKNOWN;
}
memo[memo.length - 1] = Index.GOOD;
for (int i = nums.length - 2; i >= 0; i--) {
int furthestJump = Math.min(i + nums[i], nums.length - 1);
for (int j = i + 1; j <= furthestJump; j++) {
if (memo[j] == Index.GOOD) {
memo[i] = Index.GOOD;
break;
}
}
}
return memo[0] == Index.GOOD;
}
}
跟我的差不多, 我认为代码可能不如我的clean; N^2复杂度, TLE;
不对, 看了下面的分析, 我的代码有一个严重的问题, 我的没有加一个break的short circuit, 而这个是非常重要的一个优化, 最后对于速度肯定有提升; 最重要的是, 通过这个分析, 可以得到下面的greedy思路;
Approach #4 (Greedy) [Accepted]
Once we have our code in the bottom-up state, we can make one final, important observation. From a given position, when we try to see if we can jump to a GOOD position, we only ever use one - the first one (see the break statement). In other words, the left-most one. If we keep track of this left-most GOOD position as a separate variable, we can avoid searching for it in the array. Not only that, but we can stop using the array altogether.
Iterating right-to-left, for each position we check if there is a potential jump that reaches a GOOD index (currPosition + nums[currPosition] >= leftmostGoodIndex). If we can reach a GOOD index, then our position is itself GOOD. Also, this new GOOD position will be the new leftmost GOOD index. Iteration continues until the beginning of the array. If first position is a GOOD index then we can reach the last index from the first position.
To illustrate this scenario, we will use the diagram below, for input array nums = [9, 4, 2, 1, 0, 2, 0]. We write G for GOOD, B for BAD and U for UNKNOWN. Let's assume we have iterated all the way to position 0 and we need to decide if index 0 is GOOD. Since index 1 was determined to be GOOD, it is enough to jump there and then be sure we can eventually reach index 6. It does not matter that nums[0] is big enough to jump all the way to the last index. All we need is one way.
其实第一段看完之后, 就知道是什么思路了, 真的是非常有意思的一个题目, 最后一步一步的推导, 居然还真的出来了一个很聪明的解法;
这个题目感觉有点像之前的NGE和DailyTemperatures题目的感觉, 只维护一个the closest working position; 这种思路代码写出来是一个普通的循环, 但是实际上背后有点DP的思想在里面, 类似Jason上NLP的时候说的: "anything you can do, I can do better"的思路;
public class Solution {
public boolean canJump(int[] nums) {
int lastPos = nums.length - 1;
for (int i = nums.length - 1; i >= 0; i--) {
if (i + nums[i] >= lastPos) {
lastPos = i;
}
}
return lastPos == 0;
}
}
很有意思的一个题目, 真的很有意思;
Conclusion
The question left unanswered is how should one approach such a question in an interview scenario. I would say "it depends". The perfect solution is cleaner and shorter than all the other versions, but it might not be so straightforward to figure out.
The (recursive) backtracking is the easiest to figure out, so it is worth mentioning it verbally while warming up for the tougher challenge. It might be that your interviewer actually wants to see that solution, but if not, mention that there might be a dynamic programming solution and try to think how could you use a memoization table. If you figure it out and the interviewer wants you to go for the top-down approach, it will not generally be time to think of the bottom-up version, but I would always mention the advantages of this technique as a final thought in the interview.
Most people are stuck when converting from top-down Dynamic Programming (expressed naturally in recursion) to bottom-up. Practicing similar problems will help bridge this gap.
回头想想这篇文章其实写的挺有意思的;
底下评论看到一个解法:
class Solution {
public boolean canJump(int[] nums) {
int len = nums.length;
int max = 0;
for(int i=0; i<=max; i++){
max = Math.max(max, i+nums[i]);
if(max >= len-1) return true;
}
return false;
}
}
嘿嘿, 这个思路也挺有意思的; 这个其实就是对DP性质理解的很透彻; 站在任何一个位置, 不对啊, 我没理解, 其实他这个算法的一个核心, 是你看他循环的header, 控制的是max! 这个好聪明啊; 这样max控制的实际上是可以走到的最远距离(这个最远距离肯定要考虑不仅当前的index, 还要考虑所有左边位置的最远距离), 然后这个max不停更新; 这个算法我感觉设计的还是比较难的, 因为这种loop range不停更新的算法, 真的是不太好直观解释的;
怎么好像好多人都想到了这个方法:
public bool CanJumpLinear(int[] nums)
{
if (nums[0] == 0)
{
return nums.Length == 1;
}
int lastReachable = nums[0];
for (int i = 1; i < nums.Length && i <= lastReachable; i++)
{
int lastReachableFromHere = nums[i] + i;
if (lastReachableFromHere > lastReachable)
{
lastReachable = lastReachableFromHere;
}
}
return lastReachable >= nums.Length -1;
}
这个思路的核心其实就是理解到用这个furthest reach来控制循环的范围; 这个还真的不容易想到; 那么这个解法你认为应该叫什么思路呢? 我感觉这个其实就是一个普通的循环, 关键是他自己想到了; greedy都不算, 因为没有一个select的过程;
另外, 还是继承上面作者说过的话, 真正面试的时候, 就算你想不到最优解, 能够快速写出来一个Bottom-Up的DP解法, 也是有加分的;
@alexander7 said in Linear and simple solution in C++:
I just iterate and update the maximal index that I can reach
bool canJump(int A[], int n) {
int i = 0;
for (int reach = 0; i < n && i <= reach; ++i)
reach = max(i + A[i], reach);
return i == n;
}
所以怎么都是这个做法? 不过这个人没有在中途加上一个premature exit;
@huoyao said in Linear and simple solution in C++:
Maybe for some special case ,no need to check all elements. A little change to you shearing code.Thx @alexander7
class Solution {
public:
bool canJump(int A[], int n) {
int i = 0, maxreach = 0;
for (; i < n && i <= maxreach && maxreach < n - 1; ++i)
maxreach = max(maxreach,i+A[i]);
return maxreach>=n-1;
}
};
这个加了;
我靠, 原来discussion最优解全都是这个growing loop的思路, 都这么聪明的吗; 等于说最后editorial那个解法才是异端.
@lucastan said in Simplest O(N) solution with constant space:
Idea is to work backwards from the last index. Keep track of the smallest index that can "jump" to the last index. Check whether the current index can jump to this smallest index.
bool canJump(int A[], int n) {
int last=n-1,i,j;
for(i=n-2;i>=0;i--){
if(i+A[i]>=last)last=i;
}
return last<=0;
}
editorial解法;
@xniu said in Java Solution easy to understand:
public boolean canJump(int[] A) {
int max = 0;
for(int i=0;i<A.length;i++){
if(i>max) {return false;}
max = Math.max(A[i]+i,max);
}
return true;
}
@mlblount45 said in Java 98% Percentile Solution:
The easiest way to think about this problem is to ask are the elements with a 0 value avoidable? this is the algorithm that I constructed to answer this question.Starting from the second to last element in the array we continue to decrement towards the start of the array. Only stopping if we hit an element with a value of 0; in this case we evaluate if there exist an element somewhere at the start of the array which has a jump value large enough to jump over this 0 value element.
public class Solution {
public boolean canJump(int[] nums) {
if(nums.length < 2) return true;
for(int curr = nums.length-2; curr>=0;curr--){
if(nums[curr] == 0){
int neededJumps = 1;
while(neededJumps > nums[curr]){
neededJumps++;
curr--;
if(curr < 0) return false;
}
}
}
return true;
}
}
还真有人跟我一样, 分析0; 没想到最后这个方向是走的通的; 我当时放弃这个思路的原因, 是比如..a b c 0 e f g 0..这个情况, 假如你证明了a可以跳过这个0, 那么你怎么证明a跳过去的着陆点肯定也能跳过下一个0? 但是你忽略了一个问题, 首先每一个0所对应的类似abc0的这一段当中, 只要有一个能跳过这个0, 那么所有的就都可以跳过这个0: 这个是我漏掉的关键的一个性质; 知道了这个之后, 只要你从后向前走, 证明比如efg当中至少有一个能跳过, 那么这一整段都是安全的; 那么abc只要能保证跳过第一个0, 就一定能保证能跳过第二个0;
感觉这种情况不是第一次出现了, 其实我都想到这个算法了, 都写出来了的, 但是因为没有办法证明, 所以认为不对; 这个毛病怎么解决呢? 老实说我也没有什么好办法; 我当时的想法是, 我要证明比如
但是我上面的思路其实有问题, 我以为理解了, 就自己写了这个:
public class Solution {
public boolean canJump(int[] nums) {
if (nums.length < 2)
return true;
search : for (int i = nums.length - 2; i >= 0; i--) {
if (nums[i] == 0) {
for (int j = i - 1; j >= 0; j--) {
if (nums[j] > i - j) {
i = j;
continue search;
}
if (nums[j] == 0)
return false;
}
return false;
}
}
return true;
}
}
但是这个被[3,0,0,0]给break掉了; 你知道什么原因吗? 我这个算法到了从右到左, 当到达下一个0的时候, 我直接认为efg就全部失败, 就应该return FALSE, 但是实际上, abc当中可能有一个特别大比如是10, 那么efg可以整个被跳掉了; 这里也看出来OP的这个算法的厉害之处. 他从第二个0向左走的时候, 实际上是可以走到abc的范围内的! 所以如果abc范围内有大的数字, 那么他是允许这个大数字来摆平efg的问题的; 这个就很聪明了;
他这个算法其实扫的就是, 对于每一个0, 在他的左边一定至少要有一个足够大的数字能够跳过这个0, 就ok了; 很多细节, 比如, 假如b是10, b很大, 然后efg都不够大, 都有问题; 那么你可能会想, 有没有可能b前面的一个jump, 直接跳到efg, 然后就失败呢? 但是你要知道, 这个题目本身是有一点DP的性质在里面的, 给你的是一个max jump; 如果b前面一个数字能够跳到efg, 那么他肯定能够也跳到b, 那么就够了啊, 为什么要往efg跳呢?
你可能会继续问, 那c呢? c可以跳到efg啊; 但是你是从哪里到c来的呢? 你能跳到c, 你干嘛不直接跳到b, 然后过掉两个0呢?
所以这个算法真的就是看起来简单, 但是实际上背后的弯弯绕还是挺多的的;
我自己写的那个代码, 这样改一下就可以了:
public class Solution {
public boolean canJump(int[] nums) {
if (nums.length < 2)
return true;
search : for (int i = nums.length - 2; i >= 0; i--) {
if (nums[i] == 0) {
for (int j = i - 1; j >= 0; j--) {
if (nums[j] > i - j) {
i = j;
continue search;
}
}
return false;
}
}
return true;
}
}
就是删掉看到下一个0就直接return FALSE的判断;
发了一个帖子, 自己写的解释:
@vegito2002 said in Java 98% Percentile Solution:
Similar approach. The intuition is that, as long as you make sure that there is a number big enough before each 0 to jump over this 0, you are safe. Say we have
..abc03210.., we know that321are all bad numbers that can't jump over the second0here. But as long as, saybis big enough, then we can know that both0s can be jumped over. For example,bcan be10.But you might wonder, what if we jumped from some number left of
band landed at one of321? This case does not matter, because if you can land on321from somewhere left ofb, then you sure can land onbinstead becausebis closer than any of321. Frombon, you are safe again.
But what if we are atc? Now we can land on321and fail? This also won't matter, if you can land atcin the first place, then you could have landed onbinstead in the first place.
submission基本波动;
Problem Description
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.
Difficulty:Medium
Total Accepted:153K
Total Submissions:516.8K
Contributor:LeetCode
Companies
microsoft
Related Topics
arraygreedy