04-贪心算法

type
status
date
slug
summary
tags
category
icon
password
问题
说明
是否适用贪心
零钱兑换(最少硬币数)
✅ 如果是美制面额 (1,5,10,25...)
有些币值不适用
活动选择 / 区间调度
选择最多不重叠活动
Huffman 编码
最短前缀编码
跳跃游戏 Jump Game
是否能跳到终点
加油站问题
每次加最少的油
分发饼干
每个孩子分到最小满足的饼干

1️⃣ 分发饼干

每个孩子有一个“胃口值”(g[i]),每个饼干有一个“大小值”(s[j])。
只有当饼干大小 ≥ 孩子的胃口值时,孩子才能满足。
每个孩子最多只能获得一块饼干。
问最多能满足多少个孩子?

2️⃣ 跳跃游戏

给定一个非负整数数组 nums,其中 nums[i] 表示你在位置 i 最多能跳跃的长度。
问从数组的第一个位置出发,是否能够到达最后一个位置?

3️⃣ 合并区间

给你一个区间数组 intervals,其中每个 intervals[i] = [start, end],请你合并所有 重叠 的区间,并返回合并后的结果数组。

4️⃣ 加油站问题

在一条环形公路上有 n 个加油站,第 i 个加油站有:
  • gas[i] 升汽油
  • 从第 i 个站到第 i+1 个站(下一个站)需要 cost[i] 升汽油
你拥有一辆油箱无限大的车,从某个加油站出发,走一圈回到出发点。问是否存在这样的出发站点,若存在,返回该站点编号;否则返回 -1

5️⃣ 与动态规划的比较

特性
贪心
动态规划
选择策略
当前最优
所有可能都考虑
适用范围
问题结构简单
状态复杂、需记忆
回溯
解的准确性
需证明,可能错误
正确(假设状态设计无误)
 
上一篇
03-动态规划
下一篇
01-JVM类加载机制
Loading...