有趣的地方

有趣的地方

【算法】贪心算法练习一

题目

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

1. 贪心算法的介绍

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

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

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

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

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

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

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

有问题请指出,大家一起进步!!!

发表评论:

Powered By Z-BlogPHP 1.7.3

© 2018-2020 有趣的地方 粤ICP备18140861号-1 网站地图