[算法]贪心

greedy algorithm
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

思想：无后效性， 局部最优解

步骤：

1. 问题描述， 在一组数据中， 满足限制值情况下选出期望值最大
2. 贪心算法尝试解决，每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。
3. 举例验证

缺点：适用场景有限

难点： 如何将要解决的问题抽象成贪心算法模型

适用场景：最小生成树算法、单源最短路径算法

经典应用：霍夫曼编码（Huffman Coding）、Prim 和 Kruskal 最小生成树算法、Dijkstra 单源最短路径算法

1. 分糖果

2. 钱币找零

3. 区间覆盖

4. 霍夫曼编码

作业题

最短等待时间

描述：假设有 n 个人等待被服务，但是服务窗口只有一个，每个人需要被服务的时间长度是不同的，如何安排被服务的先后顺序，才能让这 n 个人总的等待时间最短？

等待时间最短的开始服务。.时间越短位置越靠前

402. 移掉K位数字

在一个非负整数 a 中，我们希望从中移除 k 个数字，让剩下的数字值最小，如何选择移除哪 k 个数字呢？
由最高位开始，比较低一位数字，如高位大，移除，若高位小，则向右移一位继续比较两个数字，直到高位大于低位则移除，循环k次

var removeKdigits = function(num, k) {
    let arr = [...num];
    while (k > 0) {
        let index = 0;
        while (index < arr.length-1 && arr[index+1] >= arr[index]) {
            index++;
        }
        arr.splice(index, 1)
        k--;
    }
    return arr.join('').replace(/^0*/g, '') || '0';
};

1881. 插入后的最大值

被插入的数字为正数
case1: “73” 6 => 763
case2: “99” 9 => 999

var maxValue = function(n, x) {
    let nums = [...n];
    let i = 0;
    while (i < n.length && nums[i] >= x) {
        i++;
    }
    nums.splice(i, 0, x);
    return nums.join('');
};

被插入的数字为正数或负数

var maxValue = function(n, x) {
    let nums = [...n];
    let sign = 1, i = 0;
    if (nums[0] == '-') {
        sign = -1;
        i++;
    }
    while (i < n.length && (nums[i] - x) * sign >= 0) {
        i++;
    }
    nums.splice(i, 0, x);
    return nums.join('');
};

练习1:

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

var maxProfit = function(prices) {
    let res = 0;
    for (let i = 1; i < prices.length; i++) {
        res += Math.max(0, prices[i]-prices[i-1]);
    }
    return res;
};

1. 分糖果（455. 分发饼干）

描述： 每个孩子最多只能给一块饼干
贪心： 优先给需求最小的孩子

var findContentChildren = function(g, s) {
    g.sort(function(a, b) { return a - b; }); // 胃口
    s.sort(function(a, b) { return a - b; }); // 饼干
    let i = 0;
    let j = 0;
    let count = 0;
    while (i < g.length && j < s.length) {
        if (g[i] <= s[j]) {
            i++;
            count++;
        }
        j++;
    }
    return count;
};

135. 分发糖果

2. 钱币找零（860. 柠檬水找零）

付 5 美元、10 美元或 20 美元, 给出付款顺序的数组
贪心：20找零时， 优先10+5的找零方案

var lemonadeChange = function(bills) {
    // 5: 0, 10: 5, 20: 15 = 10 + 5 = 5 + 5 + 5
    let five = 0;
    let ten = 0;
    for (let coin of bills) {
        if (coin == 5) {
            five++;
        } else if (coin == 10) {
            ten++;
            five--;
        } else { // 20++
            five--;
            ten > 0 ? ten-- : five = five - 2;
        }
        if (five < 0) return false;
    }
    return true;
};

3. 区间覆盖（任务调度、教师排课）

Huffman压缩算法

霍夫曼编码是一种十分有效的编码方法，广泛用于数据压缩中，其压缩率通常在 20%～90% 之间。（实现对数据压缩编码，有效节省数据存储空间的）

具体： 根据频率的不同，用不等长的编码方式。（贪心的思想，把出现频率比较多的字符，用稍微短一些的编码；出现频率比较少的字符，用稍微长一些的编码。
⚠️， 要求各个字符的编码之间，不会出现某个编码是另一个编码前缀的情况。

假设我有一个包含 1000 个字符的文件，每个字符占 1 个 byte（1byte=8bits），存储这 1000 个字符就一共需要 8000bits。
尝试：假设我们通过统计分析发现，这 1000 个字符中只包含 6 种不同字符，假设它们分别是 a、b、c、d、e、f。而 3 个二进制位（bit）就可以表示 8 个不同的字符。3000bits

生成编码

依据频率生成二叉树（叶子节点值的和为父节点的值）， 左子树边的权为0， 右子树的权为1。根结点到叶子节点的权组成编码。

练习2:

剑指 Offer 14- I. 剪绳子

var cuttingRope = function(n) {
    // 贪心， 尽可能分为长度为3
    if (n < 4) return n -1;
    let res =1;
    while (n > 4) {
        res *= 3;
        n -= 3;
    }
    return res * n;
};

剑指 Offer 14- II. 剪绳子 II（无法使用动态规划）

var cuttingRope = function(n) {
    if (n < 4) return n -1;
    let res =1;
    const P = 1000000007;
    while (n > 4) {
        res *= 3;
        res %= P;
        n -= 3;
    }
    res *= n;
    res %= P;
    return res;
};

参考：

https://leetcode-cn.com/tag/greedy/
https://time.geekbang.org/column/article/73188