題目
給你一個非負整數(shù)數(shù)組 nums ，你最初位于數(shù)組的第一個位置通铲。數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度官辈。你的目標是使用最少的跳躍次數(shù)到達數(shù)組的最后一個位置援岩。假設你總是可以到達數(shù)組的最后一個位置。
例：
輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數(shù)是 2锹锰。從下標為 0 跳到下標為 1 的位置芥炭，跳 1 步，然后跳 3 步到達數(shù)組的最后一個位置恃慧。
方法
貪心算法的思路就是通過局部最優(yōu)推出整體最優(yōu)园蝠，應用到該題中就是，每一步盡可能多走糕伐，從而實現(xiàn)最小步數(shù)
- curCover 表示這一步的最大覆蓋范圍砰琢，nextCover 表示下一步的最大覆蓋范圍，count 表示步數(shù)
- 若 nums 數(shù)組只有一個元素，那么步數(shù)為零
- 若 nums 數(shù)組含有多個元素陪汽，循環(huán)遍歷數(shù)組训唱。首先，更新 nextCover挚冤。若下標到達這一步的覆蓋的最遠處 curCover况增，那么此時需要再次判斷該點是否為數(shù)組的終點，若并未到達數(shù)組的終點训挡，那么步數(shù)加一澳骤，并且將下一步的最大覆蓋范圍賦值給這一步的最大覆蓋范圍。并且判斷下一步的最大覆蓋范圍是否覆蓋到數(shù)組的末尾澜薄，若覆蓋到为肮，則結束循環(huán)，輸出步數(shù)
class Solution(object):
def jump(self, nums):
curCover, nextCover = 0, 0
count = 0
if len(nums) == 1:
return 0
for i in range(len(nums)):
nextCover = max(nextCover, i + nums[i])
if i == curCover:
if curCover != len(nums) - 1:
count += 1
curCover = nextCover
if nextCover >= len(nums) - 1:
break
return count
參考
代碼相關：https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html
