贪心算法
# 贪心算法
# 📋 学习目标
- 理解贪心算法的基本思想
- 掌握贪心选择性质和最优子结构
- 学会证明贪心算法的正确性
- 熟练解决经典贪心问题
# 🎯 算法思想
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。
# 核心特征
- 贪心选择性质：局部最优选择能导致全局最优解
- 最优子结构：问题的最优解包含子问题的最优解
- 无后效性：某阶段状态一旦确定，就不受这个状态以后决策的影响
# 🏆 经典问题
# 1. 活动选择问题
问题描述：给定n个活动，每个活动都有开始时间和结束时间，选择最多的活动使得它们互不冲突。
public int activitySelection(int[] start, int[] end) {
int n = start.length;
// 按结束时间排序
Integer[] indices = new Integer[n];
for (int i = 0; i < n; i++) {
indices[i] = i;
}
Arrays.sort(indices, (a, b) -> end[a] - end[b]);
int count = 1;
int lastEnd = end[indices[0]];
for (int i = 1; i < n; i++) {
if (start[indices[i]] >= lastEnd) {
count++;
lastEnd = end[indices[i]];
}
}
return count;
}
# 2. 分发饼干
问题描述：假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g); // 孩子的胃口
Arrays.sort(s); // 饼干的尺寸
int child = 0, cookie = 0;
while (child < g.length && cookie < s.length) {
if (g[child] <= s[cookie]) {
child++;
}
cookie++;
}
return child;
}
# 3. 跳跃游戏
问题描述：给定一个非负整数数组，你最初位于数组的第一个位置，数组中的每个元素代表你在该位置可以跳跃的最大长度。
public boolean canJump(int[] nums) {
int maxReach = 0;
for (int i = 0; i < nums.length; i++) {
if (i > maxReach) {
return false;
}
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;
}
# 💡 解题技巧
- 排序：很多贪心问题需要先排序
- 局部最优：每一步都选择当前最优解
- 证明正确性：需要证明局部最优能导致全局最优
- 反证法：常用于证明贪心算法的正确性