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...