蓝桥杯第十五届抱佛脚（十）贪心算法

贪心算法基本概念

贪心算法是一种在算法设计中常用的方法，它在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

贪心算法与枚举法的不同之处在于每个子问题都选择最优的情况，然后向下继续进行，且不能回溯。枚举法是将所有情况都考虑然后选出最优的情况。贪心算法在解决问题时，不从整体考虑，而是采用一种一眼看到局部最优解的选择方式。并且，贪心算法没有固定的模板可以遵循，每个题目都有不同的贪心策略，所以算法设计的关键在于贪心策略的选择。

贪心算法有一个必须注意的事情。贪心算法对于问题的要求是，所有的选择必须是无后效性的，即当前的选择不能影响后续选择对于结果的影响。

贪心算法主要适用于最优化问题，例如：最小生成树问题。有时候贪心算法并不能得到最优答案，但是能得到精确答案的近似结果。有时可以辅助其他算法得到不那么精确的结果。

贪心算法的设计步骤

1. 分析问题：理解问题的本质和要求，确定是寻找最大化还是最小化解决方案。
2. 定义贪心策略：确定在每一步如何做出最优选择。这是贪心算法的核心，需要准确判断哪种局部最优选择能够导向全局最优解。
3. 构建算法结构：根据定义的贪心策略，构建算法的整体结构。这通常涉及循环或递归，以便在每一步应用贪心策略。
4. 验证贪心策略：确保所选的贪心策略可以解决问题，对于某些问题，需要数学证明来确保局部最优选择可以导致全局最优解。

例题：分发饼干

题目描述

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 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.

解题思路

这个问题可以用贪心算法来解决。我们的目标是尽可能满足更多的孩子，所以我们应该优先满足胃口小的孩子，因为他们更容易被满足。同时，我们应该使用尽可能小的饼干来满足孩子，这样才能保留较大的饼干满足胃口更大的孩子。

1. 排序：先将孩子的胃口值数组 g 和饼干尺寸数组 s 进行排序。
2. 贪心选择：遍历每个孩子，尝试用尺寸最小的饼干满足他们。
3. 分配饼干：如果当前最小尺寸的饼干可以满足这个孩子的胃口，就将这块饼干分给他，并从饼干数组中去除这块饼干，同时计数加一；如果不能满足，就继续尝试下一个孩子。

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 美元来应对未来的交易。

1. 初始化两个变量，分别用于记录手头的 5 美元和 10 美元纸币数量。
2. 遍历 bills 数组。
   • 如果顾客支付了 5 美元，增加 5 美元纸币的数量。
   • 如果顾客支付了 10 美元，检查是否有 5 美元纸币用于找零。如果有，则减少 5 美元的数量并增加 10 美元的数量；如果没有，则无法找零，返回 false。
   • 如果顾客支付了 20 美元，优先使用 10 美元和 5 美元的组合来找零（如果可能）。如果不可能，则尝试使用三张 5 美元纸币。如果两种方式都不可行，则返回 false。
3. 如果遍历结束，都能成功找零，返回 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
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

解题思路

基本思路是优先保留结束时间早的区间，因为这样留给其他区间的空间更多，从而减少重叠的可能性。按照区间的结束时间对所有区间进行排序，然后遍历区间集合，每次选择结束时间最早且与前一个选择的区间不重叠的区间。

1. 按结束时间排序：首先将所有区间按照结束时间进行升序排序。
2. 选择区间：从排序后的区间集合中，选择结束时间最早的区间作为起始区间。
3. 遍历和比较：遍历后续的区间，如果一个区间与当前选中的区间不重叠，则选择这个区间，并更新当前选中的区间。
4. 计算移除的区间数量：计算在这个过程中跳过的区间数量，即为需要移除的最小区间数量。

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]。

解题思路

关键在于找出一种方式，使得每一支射出的弓箭能引爆尽可能多的气球。为此，我们可以将问题视为一个区间重叠的问题，其中每个气球代表一个区间。如果两个气球（区间）至少有一个共同点，那么一支弓箭就能引爆它们。

1. 按结束坐标排序：首先根据气球的结束坐标对所有气球（区间）进行排序。
2. 找出共同点：遍历排序后的气球，寻找一个共同点（即x坐标），从而用最少的弓箭引爆所有重叠的气球。
3. 更新弓箭数：每当遇到一个新的不重叠的气球时，就需要再射出一支新的弓箭。

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] 可被视为重叠区间。

解题步骤

1. 排序：根据区间的起始位置进行排序。
2. 初始化：选取第一个区间作为起始区间，用于与后续区间进行比较。
3. 合并区间：
   • 遍历剩余的区间，对于每个区间，如果它的起始位置小于或等于当前区间的结束位置，说明它们重叠，可以合并。更新当前区间的结束位置为两个区间结束位置的最大值。
   • 如果它的起始位置大于当前区间的结束位置，说明它们不重叠，应将当前区间加入结果集，并更新当前区间为新的区间。

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<int[]> merged = new 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 ， 所以永远不可能到达最后一个下标。

解题步骤

基本思路是在每一步中更新你所能到达的最远位置。遍历数组中的每个元素，如果当前位置可以达到，并且从这个位置可以跳到更远的地方，则更新最远可达位置。如果在某个时刻，这个最远位置超过或等于数组的最后一个下标，就意味着可以到达数组的末尾。

1. 初始化：设置一个变量 maxReach，表示从当前位置或之前的任意位置可以达到的最远位置。
2. 遍历数组：遍历数组的每个元素。
3. 更新最远可达位置：如果当前位置可达（即当前位置的下标小于等于 maxReach），则更新 maxReach 为当前位置加上该位置可跳跃的最大长度和 maxReach 本身中的较大者。
4. 判断可达性：如果在遍历过程中 maxReach 超过或等于数组的最后一个下标，则返回 true。如果遍历结束 maxReach 未能达到或超过最后一个下标，则返回 false。

class Solution {public boolean canJump(int[] nums) {int maxReach = 0; // 最远可达位置初始化为0for (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

解题步骤

与判断是否能到达数组末尾的问题类似，这里的目标是计算到达数组末尾的最小跳跃次数。我们可以在每一步中贪心地选择能跳得最远的那个位置，同时计算跳跃次数。

1. 初始化变量：

   • jumps：跳跃次数，初始化为 0。
   • maxReach：当前跳跃可以达到的最远位置，初始化为 nums[0]。
   • end：当前跳跃的结束位置，初始化为 nums[0]。

2. 遍历数组：从第一个元素开始，遍历到倒数第二个元素（因为起始位置已经是 nums[0]，且最后一个位置是我们的目标）。

3. 更新最远可达位置：更新 maxReach 为当前位置加上该位置可跳跃的最大长度和 maxReach 本身中的较大者。

4. 跳跃：如果到达了当前跳跃的结束位置，则增加跳跃次数，并将当前跳跃的结束位置更新为当前可以达到的最远位置。

5. 返回结果：最后返回跳跃次数。

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; // 加上最初的一跳}
}