Lexi's Leetcode solutions

[leetcode] Jump Game 2

Posted on: July 21, 2013

这个是要算到达最后一步最少要跳几步。不用非的跳到last index上,越过去也算。

还是,用dp的话有重复,不需要算d[i]跳到每一步用的最小步数,只要算最后一步能不能跳到,最少用几步就行了。这题其实自己还不够理解,下次还得重做。

算法:在每一步i,都已知到当前这一点用的最小step数k(但是不是存在数组里的,而是local variable)。在每层小循环里,都是“走一步能到的这些点中”, 最远能到哪一点,记载为p,那么到p就能最少用k + 1步就能到了。如果p出了数组边界,直接返回k + 1,就做出来了。要是没出界,则小循环之后,继续下一层循环,但是下一层循环和当前循环不重合,因为下一层说明多走了一步,则k++, 那循环的起始部分就是上一个小循环的尾。(每层小循环的意义是:用k步能走到的这些点,都试探一下,看看从他们身上走一步最远能走到哪)。

public int jump(int[] A) {
 if (A.length == 0 || A.length == 1)
   return 0;
 int examingStart = 0;
 int currSectionCanReach = 0;
 int steps = 0;
 while (examingStart <= currSectionCanReach) {
   int examingEnd = currSectionCanReach;
   int nextSectionCanReach = examingStart;
   for (int i = examingStart; i <= examingEnd; i++) {
     nextSectionCanReach = Math.max(nextSectionCanReach, i + A[i]);
     if (nextSectionCanReach >= A.length - 1)
       return steps + 1;
   }
   examingStart = examingEnd + 1;
   currSectionCanReach = nextSectionCanReach;
   steps++;
 }
 return -1;
}

1 Response to "[leetcode] Jump Game 2"

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

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