Jump Game
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.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
Solutions:
1. DP1
每到一個(gè)點(diǎn) i，我們掃描之前所有的點(diǎn)，如果之前某點(diǎn)j本身可達(dá)，并且與current 點(diǎn)可達(dá)，表示點(diǎn)i是可達(dá)的。
返回值：DP數(shù)組的最后一個(gè)值。
1 // DP1. 2 public boolean canJump1(int[] A) { 3 if (A == null || A.length == 0) { 4 return false; 5 } 6 7 int len = A.length; 8 boolean[] can = new boolean[len]; 9 can[0] = true;10 11 for (int i = 1; i < len; i++) {12 can[i] = false;13 for (int j = 0; j < i; j++) {14 // j can arrive and can jump to i.15 if (can[j] && A[j] >= i - j) {16 can[i] = true;17 break;18 }19 }20 }21 22 return can[len - 1];23 }
2. DP2
優(yōu)化的點(diǎn)1：既然某點(diǎn)可達(dá)，肯定前面的點(diǎn)全部是可達(dá)的。這個(gè)比較好理解。因?yàn)槟愕竭_(dá)i點(diǎn)肯定要經(jīng)過(guò)前面的一個(gè)點(diǎn)，這個(gè)依次推知可知前面所有的點(diǎn)可達(dá)。
所以我們不需要數(shù)組來(lái)記錄結(jié)果，只要默認(rèn)i點(diǎn)前全部可達(dá)就行了。
優(yōu)化點(diǎn)2：如果某點(diǎn)不可達(dá)了，直接返回false。不需要再往后計(jì)算。
返回值：如果全部掃完仍沒(méi)有返回false,返回true。
1 // DP2. 2 public boolean canJump2(int[] A) { 3 if (A == null || A.length == 0) { 4 return false; 5 } 6 7 int len = A.length; 8 9 for (int i = 1; i < len; i++) {10 boolean can = false;11 for (int j = 0; j < i; j++) {12 // j can arrive and can jump to i.13 if (A[j] >= i - j) {14 // 說(shuō)明i是可達(dá)的，置標(biāo)記位15 can = true;16 break;17 }18 }19 20 // 優(yōu)化:如果某一步已經(jīng)到不了了，后面的也不必再計(jì)算了.21 if (!can) {22 return false;23 }24 }25 26 return true;27 }
3. 遞歸
思想是，從前至尾掃描，至第一個(gè)距離與本點(diǎn)可達(dá)的點(diǎn)j，計(jì)算j點(diǎn)是否可達(dá)。使用遞歸計(jì)算j
點(diǎn)的可達(dá)性。
其實(shí)這里還是用到了貪心的思維。在考慮本點(diǎn)是否可達(dá)的時(shí)候，我們是考慮與本點(diǎn)最遠(yuǎn)的一個(gè)點(diǎn)是否可達(dá)。實(shí)際上這也make sense。
假設(shè)j點(diǎn)可以到達(dá)i點(diǎn)，那么后面的點(diǎn)可以不管。
（1）因?yàn)槿绻鹙點(diǎn)不可達(dá)，那么j+1也不可達(dá)。如果i不可達(dá)，后面的點(diǎn)也可不算。
（2）如果j點(diǎn)可達(dá)，并且j點(diǎn)可到達(dá)i,那么也沒(méi)有必要再往后計(jì)算了。因?yàn)榻Y(jié)論已經(jīng)出來(lái)了。
(3) 如果j點(diǎn)可達(dá)，但j不可達(dá)i，那么就繼續(xù)計(jì)算。
1 // 3. DFS. 2 public static boolean canJump3(int[] A) { 3 if (A == null || A.length == 0) { 4 return false; 5 } 6 7 return canJump(A, A.length - 1); 8 } 9 10 public static boolean canJump(int[] A, int index) {11 if (index == 0) {12 return true;13 }14 15 for (int i = 0; i <= index - 1; i++) {16 if (A[i] >= index - i) {17 return canJump(A, i);18 }19 }20 21 return false;22 }
Leetcode加強(qiáng)了test case,用動(dòng)規(guī)現(xiàn)在是過(guò)不了的。我們現(xiàn)在來(lái)使用貪心法One pass解決此問(wèn)題。
維護(hù)一個(gè)right (表示右邊能跳到的最遠(yuǎn)的點(diǎn)），從左往右掃描，根據(jù)當(dāng)前可跳的步驟不斷更新right ,當(dāng)right到達(dá)終點(diǎn)，即可返回true. 若更新完right后，right未
動(dòng)，并且index = right，而且這時(shí)沒(méi)到達(dá)終點(diǎn)，代表我們不可能到達(dá)終點(diǎn)了。（當(dāng)前index的可跳值應(yīng)該是0）。
1 // solution 3: one pass. 2 public boolean canJump(int[] A) { 3 // 4:42 4 if (A == null) { 5 return false; 6 } 7 8 int len = A.length; 9 10 int right = 0; 11 for (int i = 0; i < A.length; i++) {12 right = Math.max(right, i + A[i]);13 if (right == len - 1) {14 return true;15 }16 17 if (i == right) {18 return false;19 }20 }21 22 return true;23 }
5. GitHub代碼
References:
感謝http://blog.csdn.net/fightforyourdream/article/details/14219049給予的靈感。
聯(lián)系客服
