贪心算法一

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：了解什么是贪心算法，并且掌握贪心算法。

> 毒鸡汤：有些事情，总是不明白，所以我不会坚持。早安!

> 专栏选自：贪心算法_დ旧言~的博客-CSDN博客

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

一、算法讲解

贪心算法的定义：

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

解题的一般步骤是：

建立数学模型来描述问题；
把求解的问题分成若干个子问题；
对每一子问题求解，得到子问题的局部最优解；
把子问题的局部最优解合成原来问题的一个解。

如果大家比较了解动态规划，就会发现它们之间的相似之处。最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。

动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。

二、算法习题

2.1、第一题

题目链接：860. 柠檬水找零 - 力扣（LeetCode）

题目描述：

算法思路：

a. 遇到 5 元钱，直接收下；

b. 遇到 10 元钱，找零 5 元钱之后，收下；

c. 遇到 20 元钱：

先尝试凑 10 + 5 的组合；
如果凑不出来，拼凑 5 + 5 + 5 的组合；

代码呈现：

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) 
    {
        int five = 0, ten = 0;
        for (auto x : bills) 
        {
            if (x == 5)
                five++;       // 5 元：直接收下
            else if (x == 10) // 10 元：找零 5 元
            {
                if (five == 0)
                    return false;
                five--;
                ten++;
            } else // 20 元：分情况讨论
            {
                if (ten && five) // 贪⼼
                {
                    ten--;
                    five--;
                } else if (five >= 3) {
                    five -= 3;
                } else
                    return false;
            }
        }
        return true;
    }
};

2.2、第二题

题目链接：2208. 将数组和减半的最少操作次数 - 力扣（LeetCode）

题目描述：

算法思路：

每次挑选出「当前」数组中「最⼤」的数，然后「减半」；
直到数组和减少到⾄少⼀半为⽌。

为了「快速」挑选出数组中最⼤的数，我们可以利⽤「堆」这个数据结构。

代码呈现：

class Solution {
public:
    int halveArray(vector<int>& nums) 
    {
        priority_queue<double> heap; // 创建⼀个⼤根堆
        double sum = 0.0;
        for (int x : nums) // 把元素都丢进堆中，并求出累加和
        {
            heap.push(x);
            sum += x;
        }
        sum /= 2.0; // 先算出⽬标和
        int count = 0;
        while (sum > 0) // 依次取出堆顶元素减半，直到减到之前的⼀半以下
        {
            double t = heap.top() / 2.0;
            heap.pop();
            sum -= t;
            count++;
            heap.push(t);
        }
        return count;
    }
};

2.3、第三题

题目链接：179. 最大数 - 力扣（LeetCode）

题目描述：

算法思路：

可以先优化：

将所有的数字当成字符串处理，那么两个数字之间的拼接操作以及⽐较操作就会很⽅便。

贪⼼策略：

按照题⽬的要求，重新定义⼀个新的排序规则，然后排序即可。

排序规则：

「A 拼接 B」⼤于「B 拼接 A」，那么 A 在前，B 在后；
「A 拼接 B」等于「B 拼接 A」，那么 A B 的顺序⽆所谓；
「A 拼接 B」⼩于「B 拼接 A」，那么 B 在前，A 在后

代码呈现：

class Solution {
public:
    string largestNumber(vector<int>& nums) 
    {
        // 优化：把所有的数转化成字符串
        vector<string> strs;
        for (int x : nums)
            strs.push_back(to_string(x));
        // 排序
        sort(strs.begin(), strs.end(), [](const string& s1, const string& s2) {
            return s1 + s2 > s2 + s1;
        });
        // 提取结果
        string ret;
        for (auto& s : strs)
            ret += s;
        if (ret[0] == '0')
            return "0";
        return ret;
    }
};

2.4、第四题

题目链接：376. 摆动序列 - 力扣（LeetCode）

题目描述：

算法思路：

对于某⼀个位置来说：

如果接下来呈现上升趋势的话，我们让其上升到波峰的位置；
如果接下来呈现下降趋势的话，我们让其下降到波⾕的位置。
因此，如果把整个数组放在「折线图」中，我们统计出所有的波峰以及波⾕的个数即可

代码呈现：

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) 
    {
        int n = nums.size();
        if (n < 2)
            return n;
        int ret = 0, left = 0;
        for (int i = 0; i < n - 1; i++) 
        {
            int right = nums[i + 1] - nums[i]; // 计算接下来的趋势
            if (right == 0)
                continue; // 如果⽔平，直接跳过
            if (right * left <= 0)
                ret++; // 累加波峰或者波⾕
            left = right;
        }
        return ret + 1;
    }
};

2.5、第五题

题目链接：300. 最长递增子序列 - 力扣（LeetCode）

题目描述：

算法思路：

我们在考虑最⻓递增⼦序列的⻓度的时候，其实并不关⼼这个序列⻓什么样⼦，我们只是关⼼最后⼀个元素是谁。这样新来⼀个元素之后，我们就可以判断是否可以拼接到它的后⾯。
因此，我们可以创建⼀个数组，统计⻓度为 x 的递增⼦序列中，最后⼀个元素是谁。为了尽可能让这个序列更⻓，我们仅需统计⻓度为 x 的所有递增序列中最后⼀个元素的「最⼩值」。
统计的过程中发现，数组中的数呈现「递增」趋势，因此可以使⽤「⼆分」来查找插⼊位置。

代码呈现：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> ret;
        ret.push_back(nums[0]);
        for (int i = 1; i < n; i++) 
        {
            if (nums[i] > ret.back()) // 如果能接在最后⼀个元素后⾯，直接放
            {
                ret.push_back(nums[i]);
            } else {
                // ⼆分插⼊位置
                int left = 0, right = ret.size() - 1;
                while (left < right) {
                    int mid = (left + right) >> 1;
                    if (ret[mid] < nums[i])
                        left = mid + 1;
                    else
                        right = mid;
                }
                ret[left] = nums[i]; // 放在 left 位置上
            }
        }
        return ret.size();
    }
};

2.6、第六题

题目链接：334. 递增的三元子序列 - 力扣（LeetCode）

题目描述：

算法思路：

不⽤⼀个数组存数据，仅需两个变量即可。也不⽤⼆分插⼊位置，仅需两次⽐较就可以找到插⼊位
置。

代码呈现：

class Solution {
public : bool increasingTriplet(vector<int>& nums) 
{
        int a = nums[0], b = INT_MAX;
        for (int i = 1; i < nums.size(); i++) 
        {
            if (nums[i] > b)
                return true;
            else if (nums[i] > a)
                b = nums[i];
            else
                a = nums[i];
        }
        return false;
    }
};