Lexi's Leetcode solutions

[leetcode] Jump Game | 数组value代表能跳到哪,看能否从头跳到尾?

Posted on: July 19, 2013

这个好做,是build up的一维DP。还是,把状态d一定义,关系就自然出来了。d[i]表示能不能跳到i处,要是能跳,则再把从i处能跳到的别的地方全set up了。这样过一遍数组,就出来了。

public boolean canJump(int[] A) {
 boolean d[] = new boolean[A.length];
 d[0] = true;
 for (int i = 0; i < A.length; i++) {
   if (d[i] == true) {
     for (int j = 1; j <= A[i]; j++) {
       if (i + j < A.length)
         d[i + j] = true;
     }
   }
 }
 return d[A.length - 1];
}

然后大的就挂了有木有!!卧槽dp原来也不一定是最优解啊!!你的dp是个两层循环,有很多重复(比如到j,从i已经跳到它过了,但是i+1也能跳到它,所以重设了一遍true)。没必要把每个i能不能走到都算出来,只要算出最后一跳能不能>=n就行了。

算法:keep一个var,表示目前看来最远能走到哪。比如现在在i上,已知之前算的从0~i-1上最远就能跳到m处,那么如果i <= m,就说明i这个位置是能跳到的。为什么这就说明了呢?因为你的m是在0~i-1中的某个index上算出的,比如i0,那么说明从i0一直到m全能跳到(一步一步跳),而i还>i0,所以i到m之间当然也能一步一步跳到了。

public boolean canJump(int[] A) {
  int farIndex = 0;
  for (int i = 0; i < A.length; i++) {
    if (i <= farIndex){
      farIndex = Math.max(farIndex, A[i] + i);
    }
  }
  return farIndex >= A.length - 1;
}
Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog Stats

  • 222,235 hits
July 2013
M T W T F S S
1234567
891011121314
15161718192021
22232425262728
293031  
%d bloggers like this: