首页贪心算法leetcode经典例题

贪心算法leetcode经典例题

时间: 2025-05-03 12:32:41 浏览: 26

### 关于贪心算法的经典例题在 LeetCode 上有许多经典的贪心算法题目可以练习。这些题目能够帮助理解如何通过局部最优解来构建全局最优解。 #### 题目一：跳跃游戏 Jump Game 在这个问题中，给定一个非负整数数组 `nums` ，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断是否能到达最后一个位置[^1]。 ```python def canJump(nums): max_reach, n = 0, len(nums) for i in range(n): if i > max_reach: return False max_reach = max(max_reach, i + nums[i]) return True ``` #### 题目二：分发饼干 Assign Cookies 假设你是一位很棒的家长，想要给孩子分配一些饼干。对于每一个孩子 `i`，都有一个胃口值 `g[i]`；对于每一块饼干 `j`，都有一个尺寸 `s[j]` 。如果 `s[j] >= g[i]`，我们可以将这个饼干 `j` 分配给孩子 `i` ，这个孩子会得到满足。求最大能满足的孩子数量。 ```python def findContentChildren(g, s): g.sort() s.sort() child_i = cookie_j = 0 while child_i < len(g) and cookie_j < len(s): if s[cookie_j] >= g[child_i]: child_i += 1 cookie_j += 1 return child_i ``` #### 题目三：区间选点 Non-overlapping Intervals 给出若干闭合区间，区间的仅有端点可能重叠，移除最少数量的区间使剩下的区间不重叠。 ```python def eraseOverlapIntervals(intervals): end, cnt = float('-inf'), 0 intervals.sort(key=lambda x: x[1]) for s, e in intervals: if s >= end: end = e else: cnt += 1 return cnt ```

阅读全文