算法练习：四大算法设计思想之一——贪心算法(Greedy)

[ShannonChenCHN]

题目列表

• 122. 买卖股票的最佳时机Ⅱ⭐️
• 860. 柠檬水找零⭐️
• 455. 分发饼干⭐️
• 874. 模拟行走机器人
• 435. 无重叠区间（难度中等）
• 背包问题⭐️

总结：

1. 什么是贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。
2. 适用场景：适用贪心算法的场景就是，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
3. 用贪心算法解决问题的思路，并不总能给出最优解。
4. 典型案例：背包问题（注：不是0-1背包问题），分糖果，钱币找零，区间覆盖

[ShannonChenCHN]

理论知识：贪心算法(Greedy)

1. 什么是贪心算法？
2. 什么情况下需要用到贪心算法？

1. 什么是贪心算法？

贪⼼法，又称贪心算法、贪婪算法：在对问题求解时，总是做出在当前看来是最好的选择。

几个例子：

• 背包问题（注：不是0-1背包问题）
• 分糖果
• 钱币找零
• 区间覆盖

2. 什么情况下需要用到贪心算法？

实际上，用贪心算法解决问题的思路，并不总能给出最优解。比如，求有权图两顶点之间的最短路径。

简单地说，适用贪心算法的场景就是，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题最优解成为最优子结构。

贪心算法有很多经典的应用，比如霍夫曼编码（Huffman Coding）、Prim 和 Kruskal 最小生成树算法、还有 Dijkstra 单源最短路径算法。

3. 贪心算法和动态规划的区别

贪⼼算法与动态规划的不同在于它对每个子问题的解决⽅案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进⾏选择，有回退功能。

4. 小结

实际上，贪心算法适用的场景比较有限。这种算法思想更多的是指导设计基础算法。比如最小生成树算法、单源最短路径算法，这些算法都用到了贪心算法。在学习贪心算法时，建议不要刻意去记忆贪心算法的原理，多练习才是最有效的学习方法。

贪心算法的最难的一块是如何将要解决的问题抽象成贪心算法模型，只要这一步搞定之后，贪心算法的编码一般都很简单。贪心算法解决问题的正确性虽然很多时候都看起来是显而易见的，但是要严谨地证明算法能够得到最优解，并不是件容易的事。所以，很多时候，我们只需要多举几个例子，看一下贪心算法的解决方案是否真的能得到最优解就可以了。

参考

• 极客时间专栏：数据结构和算法之美
• 极客时间专栏：算法通关面试40讲

[ShannonChenCHN]

455. 分发饼干

2021.05.07 02:20 pm ~ 02:40 pm

参考题解：

• https://leetcode-cn.com/problems/assign-cookies/solution/455-fen-fa-bing-gan-tan-xin-jing-dian-ti-o6k6/
• https://leetcode-cn.com/problems/assign-cookies/solution/fen-fa-bing-gan-by-leetcode-solution-50se/

思路：这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。可以尝试使用贪心策略，先将饼干数组和小孩数组排序。然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。

注意点：

• Swift 中数组的排序函数: sorted(by: <)，sorted()，sorted(by: >)

class Solution {
    func findContentChildren(_ g: [Int], _ s: [Int]) -> Int {
        // 从小到大排好序
        let gSorted = g.sorted(by: <)
        let sSorted = s.sorted(by: <)
        var count = 0
        var i = 0
        var j = 0
        while i < gSorted.count && j < sSorted.count {
            let kid = gSorted[i]
            let cookie = sSorted[j]

            if kid <= cookie { // 够喂一个孩子
               count += 1 
                i += 1
            }
            j += 1
        }
        
        return count
    }
}

[ShannonChenCHN]

860. 柠檬水找零

2021.05.07 02:40 pm ~ 02:50 pm

参考题解：https://leetcode-cn.com/problems/lemonade-change/solution/ning-meng-shui-zhao-ling-by-leetcode-sol-nvp7/

三种情况：

• 5 美元 = 1 杯柠檬水
• 10 美元 = 1 杯柠檬水 + $5
• 20 美元(优先选第一种，因为需要使用 5 美元的找零场景会比需要使用 10 美元的找零场景多，我们需要尽可能保留 5 美元的钞票)
  • 1 杯柠檬水 + $5 + $10
  • 1 杯柠檬水 + $5 x 3

能不能找开取决于手中有多少零钱，所以我们需要用两个变量记录手中的零钱数。

class Solution {
    func lemonadeChange(_ bills: [Int]) -> Bool {
        var fiveCoin: Int = 0
        var tenCoin: Int = 0
        for bill in bills {
            if bill == 5 {
                fiveCoin += 1 // 得到一张 5 元
            } else if bill == 10 {
                if fiveCoin >= 1 {
                    tenCoin += 1  // 得到一张 10 元
                    fiveCoin -= 1 // 找出一张 5 元
                } else {
                    return false
                }
                
            } else if bill == 20 {
                if tenCoin >= 1 && fiveCoin >= 1 {
                    tenCoin -= 1  // 找出一张 10 元
                    fiveCoin -= 1 // 找出一张 5 元
                } else if fiveCoin >= 3 {
                    fiveCoin -= 3 // 找出一张 5 元
                } else {
                    return false
                }
            }
        }
        return true
    }
}

[ShannonChenCHN]

122. 买卖股票的最佳时机Ⅱ

2021.05.07 02:50 pm ~ 03:00 pm

参考题解：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/tan-xin-suan-fa-by-liweiwei1419-2/

解法一：贪心算法

这里可以用贪心算法来解，主要是基于以下原因：

• 不限制交易次数，只要今天股价比昨天高，就交易
• 虽然题目要求卖出之前不能买，但是计算的过程并不是真正交易的过程，因为 prices[2] - prices[0] = (prices[2] - prices[1]) + (prices[1] - prices[0])
• 对于 「今天的股价 - 昨天的股价」，得到的结果有 3 种可能：正数，0，负数。贪心算法的决策是：只加正数 。

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        guard prices.count >= 2 else {
            return 0
        }
        var profit: Int = 0
        for day in 1..<prices.count {
            let tempProfit = prices[day] - prices[day-1]
            if tempProfit > 0 {
                profit += tempProfit
            }
        }
        return profit
    }
}

解法二：动态规划

见 算法练习：动态规划。

[ShannonChenCHN]

背包问题