【算法】贪心算法练习一-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】贪心算法练习一。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

个人主页 ： zxctscl
如有转载请先通知

1. 贪心算法的介绍

一、贪心策略：解决问题的策略，局部最优->全局最优

把解决问题的过程分为若干步；
解决每一步的时候，都选择当前看起来“最优的”解法；
希望得到全局最优。

二、贪心策略的正确性
因为有可能“贪心策略”是一个错误的方法
正确的贪心策略，是需要证明的

常见的证明方法就是在数学中见过的所有证明方法。

三、学习贪心算法的方向
遇到不会的贪心题，很正常，把心态放平。

前期学习的时候，把重点放在贪心的策略上，把这个策略当做经验吸收。
如何证明贪心策略是正确的

2. 860. 柠檬水找零

【算法】贪心算法练习一,算法,贪心算法,算法

2.1 分析

一、题目解析
题目已经提到：一开始你手头没有任何零钱，如果第一个顾客给的钱超过了5美元，那么就没有零钱找，就返回false。
考虑当前的顾客时候，是不考虑后面的顾客。

二、算法原理
分情况讨论：第一种：当顾客给了5美元，就直接收下；
第二种，当顾客给了10美元，先判断一下有没有5美元，有就收下，没有就返回false;
第三种：20美元的找零，可以分一张10和一张5；还可以找三种5块钱，有分歧的时候就得判断一下哪一个找零更好，是10+5，还是5+5+5，所以对于5块钱的作用很大的时候，就把5块钱保留。

【算法】贪心算法练习一,算法,贪心算法,算法

2.2 代码

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {

        int five=0,ten=0;
        for(auto x: bills)
        {
            if(x==5) five++;
            else if(x==10)
            {
                if(five==0) return false;
                five--;ten++;
            }
            else
            {
                if(ten&&five)
                {
                    ten--;five--;
                }
                else if(five>=3)
                {
                    five-=3;
                }
                else return false;
            }
        }
        return true;

    }
};

3. 2208. 将数组和减半的最少操作次数

【算法】贪心算法练习一,算法,贪心算法,算法

3.1 分析

一、题目解析
题目要求返回将 nums 数组和至少减少一半的最少操作数，看一下例1：
【算法】贪心算法练习一,算法,贪心算法,算法
数组和是33，一半就是16.5，先选择19减半就是9.5，此时数组和没有小于16.5；然后继续选择9.5减半为4.75，此时数组和没有小于16.5；再选择8减半为4，此时此时数组和小于16.5，总共就三次减半。

二、算法原理
每次挑选当前数组中，最大的那个数，然后减半，最大的数减半，才有可能最快减到数组和减少到至少一半。
为了选择最大的数，遍历一遍数组的时间复杂度太高了，所以就用一个大根堆，每次堆顶的元素就是最大的数。

【算法】贪心算法练习一,算法,贪心算法,算法

3.2 代码

class Solution {
public:
    int halveArray(vector<int>& nums) {
        priority_queue<double> heap;
        double sum=0;
        for(auto x:nums)
        {
            heap.push(x);
            sum+=x;
        }
        sum/=2.0;

        int count=0;
        while(sum>0)
        {
            double t=heap.top()/2;
            heap.pop();
            sum-=t;
            count++;
            heap.push(t);

        }
        return count;
    }
};

4. 179. 最大数

【算法】贪心算法练习一,算法,贪心算法,算法

4.1 分析

一、题目解析
题目已经提到：
要得到最大的拼接数，就得先把这些数先拼接起来，然后比较找到最大的那一个就行。

二、算法原理
这里就得排序，确定元素的先后顺序：谁在前，谁在后
给这个数组排序，比如[a,b]：如果ab>ba,那么a前,b后；如果ab=ba，那么顺序无所谓；如果ab<ba,那么b前，a后。
比较数的拼接大小比较麻烦，可以把数转换为字符串，然后拼接字符串，比较字典序。
如果传[0,0]，那么就会出现前导0的情况，所以在最后的结果中，就直接返回0。
【算法】贪心算法练习一,算法,贪心算法,算法

4.2 代码

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;
    }
};