算法训练-6高效算法部分 贪心算法

6.3 贪心算法

前言

贪心算法一般出现在笔试题中，面试出现的概率非常低。贪心算法理解并不难，他区分于我们常用DFS/BFS/DP，他并不会枚举所有情况，而是只选择其中“当前最优”的情况。因此，贪心算法的思想并不难，甚至代码也并不难实现，但是难点在于找到贪心的策略和证明贪心策略有可行性。

贪心的正确性严格意义上来说是需要数学证明的，但这超出了数据结构的范畴，特别是笔试的时候，几乎不会有充足的时间让我们去证明贪心的正确性。因此，笔试的时候更多是观察数据的范围，如果数据量比较大，我们就可以往贪心的方向去尝试，注意这里的措辞：尝试。笔试的时候贪心算法的正确性往往是试出来的。

对于贪心，如果准备时间不是非常充裕的同学，可以不用花费太多时间，知道大概思考方向即可，因为即使花费再多时间训练贪心，效果依然是不明显的。

无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
示例 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 <= intervals.length <= 10^5
intervals[i].length == 2
- 5 * 10^4 <= starti < endi <= 5 * 10^4

题目解析

区间问题的贪心策略常见的有以下几种情况：

  • 每次选择开始时间最早的
  • 每次选择结束时间最早的
  • 每次选择总耗时最少的
  • 每次选择与最少重叠的。

此题选择策略2进行贪心。

因为结束时间越早，可选的区间就越多。这是最直观的一个解释，如果要严格地证明的话，方法如下：

  • 与其他方案相比，此算法的选择方案在选取了相同数量的更早开始的区间时，其最终结束时间不会比其他方案晚。
  • 因此，不存在选择更多区间的方案。

代码展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {

    // eraseOverlapIntervals 方法用于找出给定区间数组 intervals 中不重叠区间的数量
    // 通过首先按照结束时间对区间进行排序，然后遍历排序后的区间数组，计算出不重叠的区间数量
    public int eraseOverlapIntervals(int[][] intervals) {
        // 使用 Arrays.sort 方法和 lambda 表达式按照区间的结束时间对 intervals 进行升序排序
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        
        // 初始化计数器 cnt 为 1，表示至少有一个不重叠的区间（即第一个区间）
        // 初始化 pre 为第一个区间的结束时间
        int cnt = 1, pre = intervals[0][1];
        
        // 从第二个区间开始遍历排序后的 intervals 数组
        for (int i = 1; i < intervals.length; i++) {
            // 如果当前区间的开始时间大于或等于 pre（即前一个区间的结束时间），
            // 则说明当前区间与前一个区间不重叠，cnt 加 1
            if (intervals[i][0] >= pre) {
                cnt++;
                // 更新 pre 为当前区间的结束时间
                pre = intervals[i][1];
            }
            // 如果当前区间与前一个区间重叠，则跳过当前区间，pre 保持不变
        }
        
        // 返回 intervals 长度与 cnt 的差值，即为不重叠区间的数量
        return intervals.length - cnt;
    }
}

分发饼干

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

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
示例 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.length <= 3 * 10^4
0 <= s.length <= 3 * 10^4
1 <= g[i], s[j] <= 2^31 - 1

题目解析

首先将孩子数组和饼干数组排序。首先将最小的饼干尝试匹配胃口最小的孩子，如果匹配成功，那就直接考虑下一个；否则，则说明这个饼干无法做出贡献。

代码展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {

    // findContentChildren 方法用于找出能够满足所有孩子的最少饼干数量
    // g 是孩子们贪婪程度的数组，数值越大表示孩子越贪婪
    // s 是各种饼干的数组，数值越大表示饼干越高级
    // 方法返回能够满足所有孩子的最少饼干数量
    public int findContentChildren(int[] g, int[] s) {
        // 使用 Arrays.sort 方法对孩子们的贪婪程度进行升序排序
        Arrays.sort(g);
        // 使用 Arrays.sort 方法对饼干的高级程度进行升序排序
        Arrays.sort(s);
        
        // 初始化计数器 cnt 为 0，用于记录满足的孩子数量
        int cnt = 0;
        
        // 初始化两个指针 i 和 j 分别用于遍历饼干数组 s 和孩子们的贪婪程度数组 g
        int i = 0, j = 0;
        // 使用 for 循环同时遍历两个数组
        // 循环条件是指针 i 和 j 都在各自的数组范围内
        for (; i < s.length && j < g.length; i++) {
            // 如果当前饼干 s[i] 的高级程度大于等于当前孩子的贪婪程度 g[j]，则表示这个孩子可以被满足
            if (s[i] >= g[j]) {
                // 满足计数器 cnt 加 1
                cnt++;
                // 移动孩子们的贪婪程度数组的指针 j
                j++;
            }
        }
        // 返回满足的孩子数量 cnt
        return cnt;
    }
}

买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。

示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。

示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

提示：
1 <= prices.length <= 3 * 10^4
0 <= prices[i] <= 10^4

题目解析

由于此题不限制买卖次数，因此此题的贪心策略如下：

如果今天买明天卖可以赚钱，那么我们就执行这个操作。

代码展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {

    // maxProfit 方法用于计算在给定价格数组 prices 下，一次股票交易的最大利润
    // 假设可以完成无限次交易，但每笔交易都需要在下一次购买前出售
    public int maxProfit(int[] prices) {
        // 初始化利润变量 profit 为 0，用于累加每次交易的利润
        int profit = 0;
        
        // 遍历 prices 数组，从第二个元素开始
        for (int i = 1; i < prices.length; i++) {
            // 比较当前价格与上一个价格，如果当前价格更高，说明可以卖出获得利润
            if (prices[i] > prices[i - 1]) {
                // 计算本次交易的利润，即当前价格与上一个价格的差额，并累加到 profit
                profit += prices[i] - prices[i - 1];
            }
        }
        
        // 返回计算出的总利润
        return profit;
    }
}
计算机基础 > 算法
#算法
算法训练-6高效算法部分 贪心算法
https://fulequn.github.io/2024/05/Article202405061/
作者
Fulequn
发布于
2024年5月6日
许可协议