LeetCode 筆記係列13 Jump Game II

LeetCode 筆記係列13 Jump Game II [去掉不必要的計算]

題目： 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.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

當本娃拿到這個題目的時候，第一反應必然是dp。

解法一：

 1  public static int jump(int[] A) { 2             // Start typing your Java solution below 3             // DO NOT write main() function 4          if(A.length < 2) return 0; 5          int[] dist = new int[A.length]; 6          int[] to = new int[A.length]; 7          for(int i = 0; i < A.length; i++){ 8              dist[i] = INFINITE; 9          }10          dist[A.length - 1] = 0;11          for(int i = A.length - 2; i >= 0; i--){12              int minDist = INFINITE;13              for(int j = 1; j <= A[i] && i + j < A.length; j++){14                  int nextIdx = i + j;15                  if(nextIdx < A.length){16                      int candidate = dist[nextIdx] + 1;17                      if(candidate < minDist){18                          minDist = candidate;19                          to[i] = nextIdx;20                      }21                  }22              }23              dist[i] = minDist;24          }25          return dist[0];26      }

然後，提交，大集合再次不過。。。WTF。。。

左思右想不得其解。

好在有leetcode討論版，看到大牛的一個幾行的代碼。

NB閃閃的，就不折疊鳥。

解法二：

/* * We use "last" to keep track of the maximum distance that has been reached * by using the minimum steps "ret", whereas "curr" is the maximum distance * that can be reached by using "ret+1" steps. Thus, * curr = max(i+A[i]) where 0 <= i <= last. */class Solution {public:    int jump(int A[], int n) {        int ret = 0;        int last = 0;        int curr = 0;        for (int i = 0; i < n; ++i) {            if (i > last) {                last = curr;                ++ret;            }            curr = max(curr, i+A[i]);        }        return ret;    }};

O(n)的。。。。#我和我的小夥伴們都驚呆了#。

要理解這個算法，首先明白，這個題隻要我們求跳數，怎麽跳，最後距離是多少，都沒讓求的。

大牛這個算法的思想主要是，掃描數組（廢話。。。），以確定當前最遠能覆蓋的節點，放入curr。然後繼續掃描，直到當前的路程超過了上一次算出的覆蓋範圍，那麽更新覆蓋範圍，同時更新條數，因為我們是經過了多一跳才能繼續前進的。

形象地說，這個是在爭取每跳最遠的greedy。舉個栗子。

 

比如就是我們題目中的[2,3,1,1,4]。初始狀態是這樣的：cur表示最遠能覆蓋到的地方，用紅色表示。last表示已經覆蓋的地方，用箭頭表示。它們都指在第一個元素上。

接下來，第一元素告訴cur，最遠咱可以走2步。於是：

下一循環中，i指向1（圖中的元素3），發現，哦，i小於last能到的範圍，於是更新last（相當於說，進入了新的勢力範圍），步數ret加1.同時要更新cur。因為最遠距離發現了。

接下來，i繼續前進，發現i在當前的勢力範圍內，無需更新last和步數ret。更新cur。

i繼續前進，接下來發現超過當前勢力範圍，更新last和步數。cur已然最大了。

最後，i到最後一個元素。依然在勢力範圍內，遍曆完成，返回ret。

這道題讓我們明白一個道理：

不要做無必要的計算。

對了，有同學會問，那為啥要用last，直接用curr跳不就行了。直接用curr跳那每次都是跳最遠的，但是最優路徑不不一定是這樣。