[leetcode] Jump Game 2

Posted by: lexigrey on: July 21, 2013

• In: leetcode
• 1 Comment

这个是要算到达最后一步最少要跳几步。不用非的跳到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;
}

Tags: array, greedy, hard, undone