題目敘述
題目會給我們一個輸入陣列nums，每個元素值代表那個格子點可以跳躍的最大長度。
一開始從最左邊的格子點出發開始跳，請問可以成功抵達終點，也就是最右邊的格子點嗎?
如果可以，返回 True。如果不行，返回False。
測試範例
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
0 -> 1 - > 4
先從零跳一步到1，
再從1跳3步，可以抵達終點，也就是第四個格子點。
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
無解，跳不過去。
約束條件
Constraints:
1 <= nums.length <= 10^4
輸入陣列的長度介於1 ~ 10^4 。
0 <= nums[i] <= 10^5
每個格子點最小可以跳0格，相當於留在原地。代表題目可能會給陷阱格子。
最大可以跳10^5個格子。
演算法 第一知覺的想法
第一直覺想到就是依照遊戲規則去模擬，盡量往右邊跳，看看能不能從起點0開始跳到終點?
當然是可以的，但是仔細留意一下，nums[i]最大可以有10^5，代表每個格子點可能的選擇(也就是分枝)可以有十萬條路徑，顯然用直接進行模擬會存在執行速度太慢或者time-out超過時間限制的風險，因為是指數級別的枚舉所有跳躍路徑。
這題其實用DFS模擬，或者BFS模擬跳躍，還是勉強可以通過平台的測試。
但是，後面我們會介紹一個更好的演算法，採用貪心策略Greedy strategy的演算法來提升速度。
程式法 DFS模擬跳躍
class Solution:
def canJump(self, nums: List[int]) -> bool:
destination = len(nums)-1
if destination == 0:
return True
seen = set([0])
def dfs(i):
if i >= destination:
return True
for jump in range(1, nums[i]+1) :
if (i + jump) not in seen:
seen.add( i + jump )
if i + jump >= destination or dfs( i + jump):
return True
return False
# ===========================
return dfs( i = 0)
程式碼 BFS模擬跳躍
class Solution:
def canJump(self, nums: List[int]) -> bool:
destination = len(nums)-1
if destination == 0:
return True
bfs_q = deque([0])
seen = set([0])
while bfs_q:
cur = bfs_q.popleft()
for jump in reversed(range(1, nums[cur]+1)):
if cur + jump >= destination:
return True
if cur+jump not in seen:
bfs_q.append( cur+jump )
seen.add( cur+jump )
return False
演算法 Greedy 策略 盡量去延伸我能抵達的地方
其實題目真正問的關鍵在於"能不能夠"抵達終點?
題目並沒有去要求我們列出跳躍的路徑(也就是過程)。
題目只關心結果，能不能抵達終點?
換句話說，假如我們經由跳躍能夠碰觸的範圍，盡量去往右邊延伸，可以覆蓋到終點，那麼一定有解，可以從起點開始跳躍，抵達終點。
如果不行，則代表半路上就停下來了，已經盡力跳了，但是就是過不去，無解，返回False。
程式碼 Greedy 策略 盡量去延伸我能抵達的地方
class Solution:
def canJump(self, nums: List[int]) -> bool:
# 能夠抵達的範圍
max_reach = nums[0]
for i, jump in enumerate(nums):
# 已經盡力跳了，但是到不了 index i，
# 半路上就被迫停下來了，無解。
if max_reach < i:
return False
# 盡量去往右邊延伸經由跳躍能夠碰觸的範圍，
max_reach = max(max_reach, i + jump)
# 假如跳耀的範圍能覆蓋終點，那麼一定有解
return max_reach >= ( len(nums)-1 )
複雜度分析 Greedy 策略 盡量去延伸我能抵達的地方
令n=輸入陣列nums的長度
時間複雜度:
從左邊到右邊逐一檢查每個格子點，盡量去延伸跳躍能覆蓋的範圍，總共所需時間為O(n)。
空間複雜度:
用到的都是固定尺寸的臨時變數，總共所需空間為O(1)。
關鍵知識點
題目並沒有去要求我們列出跳躍的路徑(也就是過程)。
題目只關心結果，能不能抵達終點?
換句話說，假如我們經由跳躍能夠碰觸的範圍，盡量去往右邊延伸，可以覆蓋到終點，那麼一定有解，可以從起點開始跳躍，抵達終點。
如果不行，則代表半路上就停下來了，已經盡力跳了，但是就是過不去，無解，返回False。
