贪心算法面试常见问题分类解析

一、贪心算法问题

1. 跳跃游戏系列

• 能否到达终点：

  def canJump(nums):max_reach = 0for i in range(len(nums)):if i > max_reach:return Falsemax_reach = max(max_reach, i + nums[i])return True

• 最少步数：

  def jump(nums):jumps = end = max_pos = 0for i in range(len(nums)-1):max_pos = max(max_pos, i + nums[i])if i == end:jumps += 1end = max_posreturn jumps

2. 分发饼干

• 解法：排序+双指针

  def findContentChildren(g, s):g.sort()s.sort()i = j =