【算法学习】day3

文章目录

• 贪心算法
• • 柠檬水找零
  • 将数组和减半的最小操作数

贪心算法

柠檬水找零

思路：先遍历记录各个数值的张数，如果收入5那就收下，five++，如果收入10，找回5，five–，ten++，如果five==0，返回false，如果收入20.找回15，如果有5和10，five–，ten–，没有10,5的数量大于等于3，five-=3，如果都没有返回false，最后返回true。
代码实现：

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)
                { five--;
                ten++;
                }
                else return false;
            }
            else{
                if(five&&ten)
                {
                    ten--;
                    five--;
                }
                else if(five>=3)
                {
                    five-=3;
                }
                else return false;
            }
        }
        return true;

    }
};

将数组和减半的最小操作数

思路：每次选取最大的一个数除2，这就需要大堆，所以我们定义一个优先级队列priority_queue，先进行遍历将数组和求出来，先将和/2,这样在循环的时候只要sun<0就达到了要求，在利用循环，每次取堆顶除2，删除堆顶，和减去这个数，计数器ret++，在入堆，最后循环结束返回ret。
代码实现：

class Solution {
public:
    
    int halveArray(vector<int>& nums) {
         priority_queue<double> q;

         double sum=0.0;
         int ret=0;
         for(auto x:nums)
         {
            sum+=x;
            q.push(x);
         }
        sum/=2.0;
        while(sum>0)
        {
            double t=q.top()/2;
            q.pop();
            sum-=t;
            ret++;
            q.push(t);
        }
        return ret;
    }
};