贪心


(0)前言

通过局部最优得到全局最优解。

(1)55.跳跃游戏

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_pos=0
        n=len(nums)
        for i in range(n):
            if i>max_pos: return False
            max_pos=max(max_pos,i+nums[i])
            if max_pos>=n-1: return True

(2)45.跳跃游戏 II

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums)==1:return 0
        count,end,max_pos=0,0,0
        
        for i in range(len(nums)):
            max_pos=max(max_pos,nums[i]+i)
            if i==end:       #解法的核心
                end=max_pos 
                count+=1
            if end>=len(nums)-1:
                return count
                
        return count

# 经典贪心

文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录