Lexi's Leetcode solutions

Posts Tagged ‘greedy

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

这个好做,是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: ,