Problem
ACF20240-EA56-46C0-BDBC-C78EAC14149B
Solution
Back-forward
- 首先把 list 里最后一項(xiàng)作為目標(biāo)。
- 由后向前尋找可以到達(dá)目標(biāo)的位置i（滿足 i + nums[i] >= des）。
- 如果發(fā)現(xiàn)滿足條件的位置 i 骇陈，把目標(biāo)更新為位置 i灾炭，如果 i 為 0闲坎，返回 True旺垒，否則然后開(kāi)始下一個(gè)循環(huán)寨躁。
- 如果找不到滿足條件的 i宛裕， 返回 False
Explanation in English :
- Set des(destination) equals to the last item in the “nums”.
- From back to front finding i which can meet the condition: i + nums[i] >= des
- If we can find i satisfies the condition, set des = i. If i == 0, then return True, otherwise start the next loop.
- If there is no i can meet the condition, return False.
class Solution:
def canJump(self, nums) -> int:
if not nums or len(nums) == 1:
return True
des = len(nums) - 1
for I in range(des - 1, -1, -1):
if I + nums[I] >= des:
des = i
if des == 0:
return True
Greedy
Chinese:
我們也可以通過(guò)修改問(wèn)題45 的代碼通過(guò)貪婪算法得到答案瑟啃。
English:
We can easily change our code in Problem 45 to get the solution.
class Solution:
def canJump(self, nums) -> int:
if not nums or len(nums) == 1:
return False
des = len(nums) - 1
I = 0
max_range = 0
nxt = 0
while I < des:
if I + nums[I] >= des:
return True
for r in range(I + 1, I + nums[I] + 1):
if r + nums[r] > max_range:
max_range = r + nums[r]
nxt = r
if I == nxt:
return False
else:
I = nxt
如何刷題 : Leetcode 題目的正確打開(kāi)方式
我的GitHub : Jedi-XL
其他題目答案：leetcode題目答案講解匯總（Python版 持續(xù)更新）
我的博客里還有其他好東西： 苔原帶
