1、題目鏈接
https://leetcode.com/problems/jump-game/
2、解題思路
首先，這是一道比較經(jīng)典的貪心算法題曙咽，何為貪心，我所理解的就是局部最優(yōu)挑辆，不考慮全局的情況下（>_<說(shuō)人話：就是說(shuō)每次我都選最好的那一個(gè)），這道題就是說(shuō)給你一個(gè)數(shù)組孝情，數(shù)組里面的數(shù)代表你每次能跳躍的最大距離鱼蝉，就好比我走臺(tái)階，每一階臺(tái)階上面都標(biāo)了你最多只能往前走幾個(gè)臺(tái)階箫荡，問(wèn)你能不能從臺(tái)階的起點(diǎn)到達(dá)臺(tái)階的終點(diǎn)魁亦，那么，我們就走起來(lái)羔挡。我剛開始的想法是遍歷數(shù)組并計(jì)算數(shù)組當(dāng)前位置和當(dāng)前數(shù)組的值（最多能走幾步洁奈，貪心，我們就走最多的）绞灼，看是否有大于等于數(shù)組長(zhǎng)度的利术，如果有就輸出true，沒有就輸出false低矮，后來(lái)發(fā)現(xiàn)并不是這么簡(jiǎn)單印叁，就比如[1, 0, 1, 0]這一組數(shù)據(jù)，我連第一個(gè)0都走不過(guò)去军掂，還怎么往后走轮蜕，于是乎就有了一個(gè)maxDistance這個(gè)值，這個(gè)值定義你當(dāng)前能走得到的最遠(yuǎn)的距離蝗锥，如果當(dāng)前我遍歷到的坐標(biāo)比maxDistance大那么說(shuō)明我遇到了0（不能走的）而且還走不過(guò)去跃洛，這時(shí)候也沒必要往后遍歷了；如果遍歷到maxDistance已經(jīng)可以走到最后一個(gè)位置的時(shí)候终议，這時(shí)候我們也沒必要往后再遍歷了汇竭，因?yàn)榭梢砸徊降轿涣讼醒樱绻疾粷M足的話，那么我們就一直遍歷然后更新maxDistance韩玩，遍歷完成之后判斷maxDistance是否可以走到最后一個(gè)位置
3垒玲、代碼
- Java
private static boolean canJump(int[] nums) {
if (null == nums || nums.length == 0) {
return false;
}
if (nums.length == 1) {
return true;
}
if (nums[0] == 0) {
return false;
}
int maxDistance = 0;
for (int i = 0; i < nums.length; i++) {
if (maxDistance < i) {
return false;
} else if (maxDistance >= nums.length - 1) {
return true;
}
maxDistance = Math.max(maxDistance, nums[i] + i);
}
return maxDistance >= nums.length - 1;
}
- Python
def canJump(numList):
if numList is None or len(numList) == 0:
return False
if len(numList) == 1:
return True
if numList[0] == 0:
return False
maxDistance = 0
for index in range(len(numList)):
if maxDistance < index:
return False
elif maxDistance >= len(numList) - 1:
return True
maxDistance = max(maxDistance, numList[index] + index)
return maxDistance >= len(numList) - 1
- JavaScript
var canJump = function(numList) {
if (undefined === numList || null === numList || numList.length == 0) {
return false
}
if (numList.length == 1) {
return true
}
let maxDistance = 0
for (let i = 0; i < numList.length; i++) {
if (i > maxDistance) {
return false
} else if (maxDistance >= numList.length - 1) {
return true
}
maxDistance = Math.max(maxDistance, numList[i] + i)
}
return maxDistance >= numList.length - 1
}
4、提交結(jié)果
