蓝桥杯第十五届抱佛脚（十）贪心算法
贪心算法基本概念
贪心算法是一种在算法设计中常用的方法，它在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。
贪心算法与枚举法的不同之处在于每个子问题都选择最优的情况，然后向下继续进行，且不能回溯。枚举法是将所有情况都考虑然后选出最优的情况。贪心算法在解决问题时，不从整体考虑，而是采用一种一眼看到局部最优解的选择方式。并且，贪心算法没有固定的模板可以遵循，每个题目都有不同的贪心策略，所以算法设计的关键在于贪心策略的选择。
贪心算法有一个必须注意的事情。贪心算法对于问题的要求是，所有的选择必须是无后效性的，即当前的选择不能影响后续选择对于结果的影响。
贪心算法主要适用于最优化问题，例如：最小生成树问题。有时候贪心算法并不能得到最优答案，但是能得到精确答案的近似结果。有时可以辅助其他算法得到不那么精确的结果。
贪心算法的设计步骤
分析问题：理解问题的本质和要求，确定是寻找最大化还是最小化解决方案。定义贪心策略：确定在每一步如何做出最优选择。这是贪心算法的核心，需要准确判断哪种局部最优选择能够导向全局最优解。构建算法结构：根据定义的贪心策略，构建算法的整体结构。这通常涉及循环或递归，以便在每一步应用贪心策略。验证贪心策略：确保所选的贪心策略可以解决问题，对于某些问题，需要数学证明来确保局部最优选择可以导致全局最优解。
例题：分发饼干
题目描述
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
解题思路
这个问题可以用贪心算法来解决。我们的目标是尽可能满足更多的孩子，所以我们应该优先满足胃口小的孩子，因为他们更容易被满足。同时，我们应该使用尽可能小的饼干来满足孩子，这样才能保留较大的饼干满足胃口更大的孩子。
排序：先将孩子的胃口值数组 g 和饼干尺寸数组 s 进行排序。贪心选择：遍历每个孩子，尝试用尺寸最小的饼干满足他们。分配饼干：如果当前最小尺寸的饼干可以满足这个孩子的胃口，就将这块饼干分给他，并从饼干数组中去除这块饼干，同时计数加一；如果不能满足，就继续尝试下一个孩子。
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g); // 对孩子的胃口值进行排序
Arrays.sort(s); // 对饼干尺寸进行排序
int childIndex = 0, cookieIndex = 0;
int count = 0;
while (childIndex < g.length && cookieIndex < s.length) {
if (g[childIndex] <= s[cookieIndex]) {
// 如果当前饼干可以满足当前孩子的胃口，计数加一
count++;
childIndex++; // 考虑下一个孩子
}
cookieIndex++; // 取下一块饼干
}
return count;
}
}
经典贪心问题
找零钱问题
柠檬水找零
题目描述
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：
输入：bills = [5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
解题思路
问题关键在于如何有效管理手头的零钱，以确保能够为每位顾客正确找零。算法的基本思路是：尽量保留更多的 5 美元纸币，因为它们对找零来说更灵活。当顾客使用 20 美元时，优先使用 10 美元来找零（如果有的话），这样可以留下更多的 5 美元来应对未来的交易。
初始化两个变量，分别用于记录手头的 5 美元和 10 美元纸币数量。遍历 bills 数组。
如果顾客支付了 5 美元，增加 5 美元纸币的数量。如果顾客支付了 10 美元，检查是否有 5 美元纸币用于找零。如果有，则减少 5 美元的数量并增加 10 美元的数量；如果没有，则无法找零，返回 false。如果顾客支付了 20 美元，优先使用 10 美元和 5 美元的组合来找零（如果可能）。如果不可能，则尝试使用三张 5 美元纸币。如果两种方式都不可行，则返回 false。 如果遍历结束，都能成功找零，返回 true。
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0, ten = 0; // 初始没有任何零钱
for (int bill : bills) {
if (bill == 5) {
five++; // 收到5美元，five增加
} else if (bill == 10) {
if (five == 0) return false; // 没有5美元找零
five--;
ten++;
} else {
// 优先使用10美元和5美元组合找零
if (five > 0 && ten > 0) {
five--;
ten--;
} else if (five >= 3) {
five -= 3; // 只能用三张5美元找零
} else {
return false; // 无法找零
}
}
}
return true;
}
}
区域选择问题
无重叠区间
题目描述
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
解题思路
基本思路是优先保留结束时间早的区间，因为这样留给其他区间的空间更多，从而减少重叠的可能性。按照区间的结束时间对所有区间进行排序，然后遍历区间集合，每次选择结束时间最早且与前一个选择的区间不重叠的区间。
按结束时间排序：首先将所有区间按照结束时间进行升序排序。选择区间：从排序后的区间集合中，选择结束时间最早的区间作为起始区间。遍历和比较：遍历后续的区间，如果一个区间与当前选中的区间不重叠，则选择这个区间，并更新当前选中的区间。计算移除的区间数量：计算在这个过程中跳过的区间数量，即为需要移除的最小区间数量。
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) return 0;
// 按照区间的结束时间进行排序
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int end = intervals[0][1];
int count = 1; // 计数器，记录非重叠区间的数量
for (int[] interval : intervals) {
if (interval[0] >= end) {
// 如果当前区间的开始时间大于等于上一个区间的结束时间，更新end并计数
end = interval[1];
count++;
}
}
return intervals.length - count; // 返回需要移除的区间数量
}
}
用最少数量的箭引爆气球
题目描述
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
示例 1：
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 6处射出箭，击破气球[2,8]和[1,6]。
- 在x = 11处发射箭，击破气球[10,16]和[7,12]。
示例 2：
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。
示例 3：
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。
解题思路
关键在于找出一种方式，使得每一支射出的弓箭能引爆尽可能多的气球。为此，我们可以将问题视为一个区间重叠的问题，其中每个气球代表一个区间。如果两个气球（区间）至少有一个共同点，那么一支弓箭就能引爆它们。
按结束坐标排序：首先根据气球的结束坐标对所有气球（区间）进行排序。找出共同点：遍历排序后的气球，寻找一个共同点（即x坐标），从而用最少的弓箭引爆所有重叠的气球。更新弓箭数：每当遇到一个新的不重叠的气球时，就需要再射出一支新的弓箭。
class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length == 0) return 0;
// 根据每个气球的结束坐标进行排序
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
int arrowPos = points[0][1]; // 第一支箭射在第一个气球的结束位置
int arrowCount = 1;
for (int[] balloon : points) {
// 如果当前气球的开始位置在上一支箭的射击位置之后，需要再射一支箭
if (balloon[0] > arrowPos) {
arrowPos = balloon[1]; // 更新箭的位置到当前气球的结束位置
arrowCount++;
}
}
return arrowCount;
}
}
合并区间
题目描述
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
解题步骤
排序：根据区间的起始位置进行排序。初始化：选取第一个区间作为起始区间，用于与后续区间进行比较。合并区间：
遍历剩余的区间，对于每个区间，如果它的起始位置小于或等于当前区间的结束位置，说明它们重叠，可以合并。更新当前区间的结束位置为两个区间结束位置的最大值。如果它的起始位置大于当前区间的结束位置，说明它们不重叠，应将当前区间加入结果集，并更新当前区间为新的区间。
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length <= 1) return intervals;
// 按照起始位置排序
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
LinkedList
for (int[] interval : intervals) {
// 如果列表为空，或者当前区间不与前一个区间重叠，直接添加
if (merged.isEmpty() || merged.getLast()[1] < interval[0]) {
merged.add(interval);
} else {
// 否则，我们合并当前和前一个区间
merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]);
}
}
return merged.toArray(new int[merged.size()][]);
}
}
在这个解法中，我们首先对区间进行排序，然后创建一个 LinkedList 来存储合并后的区间。通过遍历排序后的区间，我们逐一确定是否需要合并区间，或者将当前区间添加到结果列表中。最后，将 LinkedList 转换为二维数组并返回。
跳跃问题
跳跃游戏
题目描述
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
解题步骤
基本思路是在每一步中更新你所能到达的最远位置。遍历数组中的每个元素，如果当前位置可以达到，并且从这个位置可以跳到更远的地方，则更新最远可达位置。如果在某个时刻，这个最远位置超过或等于数组的最后一个下标，就意味着可以到达数组的末尾。
初始化：设置一个变量 maxReach，表示从当前位置或之前的任意位置可以达到的最远位置。遍历数组：遍历数组的每个元素。更新最远可达位置：如果当前位置可达（即当前位置的下标小于等于 maxReach），则更新 maxReach 为当前位置加上该位置可跳跃的最大长度和 maxReach 本身中的较大者。判断可达性：如果在遍历过程中 maxReach 超过或等于数组的最后一个下标，则返回 true。如果遍历结束 maxReach 未能达到或超过最后一个下标，则返回 false。
class Solution {
public boolean canJump(int[] nums) {
int maxReach = 0; // 最远可达位置初始化为0
for (int i = 0; i < nums.length; i++) {
if (i > maxReach) {
return false; // 当前位置不可达
}
maxReach = Math.max(maxReach, i + nums[i]); // 更新最远可达位置
if (maxReach >= nums.length - 1) {
return true; // 可以到达数组末尾
}
}
return false;
}
}
跳跃游戏 II
题目描述
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
解题步骤
与判断是否能到达数组末尾的问题类似，这里的目标是计算到达数组末尾的最小跳跃次数。我们可以在每一步中贪心地选择能跳得最远的那个位置，同时计算跳跃次数。
初始化变量：
jumps：跳跃次数，初始化为 0。maxReach：当前跳跃可以达到的最远位置，初始化为 nums[0]。end：当前跳跃的结束位置，初始化为 nums[0]。 遍历数组：从第一个元素开始，遍历到倒数第二个元素（因为起始位置已经是 nums[0]，且最后一个位置是我们的目标）。 更新最远可达位置：更新 maxReach 为当前位置加上该位置可跳跃的最大长度和 maxReach 本身中的较大者。 跳跃：如果到达了当前跳跃的结束位置，则增加跳跃次数，并将当前跳跃的结束位置更新为当前可以达到的最远位置。 返回结果：最后返回跳跃次数。
class Solution {
public int jump(int[] nums) {
if (nums.length <= 1) {
return 0;
}
int jumps = 0, maxReach = nums[0], end = nums[0];
for (int i = 1; i < nums.length - 1; i++) {
maxReach = Math.max(maxReach, i + nums[i]);
if (i == end) {
jumps++;
end = maxReach;
}
}
return jumps + 1; // 加上最初的一跳
}
}
精彩文章
您阅读本篇文章共花了：
发表评论