資訊專欄INFORMATION COLUMN
摘要：當(dāng)前起點(diǎn)為數(shù)組中下標(biāo)為零的位置，要走到數(shù)組的最后一個(gè)下標(biāo)。其中，數(shù)組中每一個(gè)元素代表當(dāng)前下標(biāo)下可以前進(jìn)的最大步數(shù)。如果最終的終點(diǎn)就是起始節(jié)點(diǎn)，那么肯定可以從其實(shí)節(jié)點(diǎn)找到一條路徑到達(dá)終點(diǎn)，否則失敗。
題目要求
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.
翻譯過來就是，假設(shè)有一個(gè)數(shù)組，該數(shù)組中的元素全部都是非負(fù)整數(shù)。當(dāng)前起點(diǎn)為數(shù)組中下標(biāo)為零的位置，要走到數(shù)組的最后一個(gè)下標(biāo)。其中，數(shù)組中每一個(gè)元素代表當(dāng)前下標(biāo)下可以前進(jìn)的最大步數(shù)。如果可以從起點(diǎn)走向終點(diǎn)，那么返回true，否則返回false
思路一：遞歸backtracking最直接想法，就是通過遞歸遍歷當(dāng)前點(diǎn)作為起始點(diǎn)是否可以走到終點(diǎn)。這種思路的結(jié)果是代碼超時(shí)。細(xì)想一下，前一個(gè)節(jié)點(diǎn)的遍歷可能和后一個(gè)節(jié)點(diǎn)的遍歷出現(xiàn)路徑上的重復(fù)，但是這些重復(fù)的結(jié)果并沒有被重復(fù)利用。所以這種方法雖然直觀但是效率低下。
代碼如下
public boolean canJump(int[] nums) {
int lastIndex= nums.length - 1;
if(lastIndex < 0){
return false;
}
return canJump(nums, 0, lastIndex);
}
public boolean canJump(int[] nums, int currentIndex, int lastIndex){
int remainSteps = nums[currentIndex];
if(currentIndex + remainSteps >= lastIndex){
return true;
}
while(remainSteps-- > 0){
boolean canJump = canJump(nums, ++currentIndex, lastIndex);
if(canJump){
return true;
}
}
return false;
}
思路二：逆轉(zhuǎn)遍歷
其實(shí)通過對(duì)上一種思路的觀察，可以知道，如果某一個(gè)節(jié)點(diǎn)可以通過某種路徑到達(dá)終點(diǎn)，那么所有可以到達(dá)這一個(gè)節(jié)點(diǎn)的其他節(jié)點(diǎn)也一定可以到達(dá)終點(diǎn)。如果從終點(diǎn)向起點(diǎn)遍歷，已知終點(diǎn)本身肯定可以到達(dá)自己，那么可以依次向前遍歷，判斷當(dāng)前節(jié)點(diǎn)是否能夠達(dá)到終點(diǎn)。如果能夠找到這么一個(gè)節(jié)點(diǎn)，就將該節(jié)點(diǎn)設(shè)為新的終點(diǎn)，并按照之前的思路繼續(xù)遍歷，直到起始節(jié)點(diǎn)。如果最終的終點(diǎn)就是起始節(jié)點(diǎn)，那么肯定可以從其實(shí)節(jié)點(diǎn)找到一條路徑到達(dá)終點(diǎn)，否則失敗。
代碼如下：
boolean canJump2(int A[]) {
int last=A.length-1,i;
for(i=last-1;i>=0;i--){
if(i+A[i]>=last)last=i;
}
return last==0;
}
其實(shí)，這道題的官方也給出了明確的循序漸進(jìn)的思路，可以進(jìn)行參考
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/67198.html
摘要：轉(zhuǎn)換為廣度優(yōu)先算法即為我們只需要找到每一步的開始節(jié)點(diǎn)和結(jié)束下標(biāo)，找到下一輪遍歷的最大下標(biāo)，如果該下標(biāo)超過了數(shù)組長(zhǎng)度，那么結(jié)束遍歷，返回步數(shù)，否則將上一輪的最終節(jié)點(diǎn)加一作為起始節(jié)點(diǎn)，并將下一輪最大下標(biāo)最為結(jié)束節(jié)點(diǎn)，繼續(xù)遍歷。 題目要求 Given an array of non-negative integers, you are initially positioned at the ...
摘要：復(fù)雜度思路每次設(shè)置一個(gè)窗口，觀察在這一步下能到達(dá)的最遠(yuǎn)距離，不斷的移動(dòng)這個(gè)窗口。計(jì)數(shù)，需要移動(dòng)幾次，才能覆蓋到末尾的值。 LeetCode[45] Jump Game II Given an array of non-negative integers, you are initially positioned at the first index of the array. Eac...
摘要：建立動(dòng)規(guī)數(shù)組，表示從起點(diǎn)處到達(dá)該點(diǎn)的可能性。循環(huán)結(jié)束后，數(shù)組對(duì)所有點(diǎn)作為終點(diǎn)的可能性都進(jìn)行了賦值。和的不同在于找到最少的步數(shù)。此時(shí)的一定是滿足條件的最小的，所以一定是最優(yōu)解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...
摘要：代碼記錄下當(dāng)前區(qū)域的上界，以便待會(huì)更新下一個(gè)區(qū)域的上界更新下一個(gè)區(qū)域的上界更新下一個(gè)區(qū)域的下界后續(xù)如果要求返回最短跳躍路徑，如何實(shí)現(xiàn)可以使用，并根據(jù)一個(gè)全局最短步數(shù)維護(hù)一個(gè)全局最短路徑，當(dāng)搜索完所有可能后返回這個(gè)全局最短路徑。 Jump Game I 最新解法請(qǐng)見：https://yanjia.me/zh/2019/01/... Given an array of non-negat...
摘要：還有一個(gè)石頭可能由之前的多個(gè)石頭到達(dá)，這又是可以優(yōu)化的地方。當(dāng)前結(jié)果可由之前的結(jié)果得出，且有重復(fù)的搜索方法，就需要用。 [鏈接描述]leetcode 題目。 有點(diǎn)類似于jump game， 只不過這里對(duì)步數(shù)有了隱形的要求，當(dāng)前步數(shù)和之前步數(shù)有關(guān)。如果我們用brute force的方法來解，每一步有三種可能，一共n個(gè)石頭，時(shí)間復(fù)雜度就是O(3^n)。這其中有很多步數(shù)是多余的，第i個(gè)石頭...
閱讀 3280·2023-04-26 02:42
閱讀 791·2021-10-09 09:41
閱讀 3191·2021-09-06 15:02
閱讀 700·2019-08-26 10:45
閱讀 480·2019-08-23 15:53
閱讀 733·2019-08-22 18:10
閱讀 550·2019-08-22 18:01
閱讀 3517·2019-08-22 17:34
