0 題目描述
leetcode原題鏈接：跳躍游戲
1 貪心演算法
思路：盡可能到達最遠位置（貪心）
如果能到達某個位置，那一定能到達它前面的所有位置，
方法：初始化最遠位置為 0，然后遍歷陣列，如果當前位置能到達，并且當前位置+跳數>最遠位置，就更新最遠位置，如果當前位置比最遠位置還要遠，直接回傳False，
class Solution:
def canJump(self, nums: List[int]) -> bool:
# 最遠到達位置
reach = 0
for i in range(len(nums)):
if i > reach: return False
reach = max(reach, i + nums[i])
return True復雜度分析：
時間復雜度
O
(
n
)
O(n)
O(n)，空間復雜度
O
(
1
)
O(1)
O(1)，
參考資料
Python擊敗97%，看不懂你錘我
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/204668.html
標籤：其他