【hot100篇-python刷题记录】【跳跃游戏 II】

R7-贪心算法

目录

方法1：

方法2： 

很贪心啊，局部最优解就是全局最优解，要求到达nums[n-1]的最小步数，我们每一步都走最远。

方法1：

class Solution:def jump(self, nums: List[int]) -> int:n=len(nums)if n==1:return 0start,ret=0,0while start<len(nums)-1:step=nums[start]if step+start>=len(nums)-1:return ret+1#默认从第一位开始跳next_index=start+1max_address=nums[next_index]+next_index#选择能到达的最大索引为跳点for i in range(start+2,start+step+1):if i+nums[i]>=max_address:next_index=imax_address=i+nums[i]start=next_indexret+=1return ret+1

方法2： 

难他天

class Solution:def jump(self, nums: List[int]) -> int:n=len(nums)start=step=0end=1while end<n:max_num=0for i in range(start,end):max_num=max(max_num,i+nums[i])start,end,step=end,max_num+1,step+1return step