C++数据结构与算法——贪心算法简单题

C++第二阶段——数据结构和算法，之前学过一点点数据结构，当时是基于Python来学习的，现在基于C++查漏补缺，尤其是树的部分。这一部分计划一个月，主要利用代码随想录来学习，刷题使用力扣网站，不定时更新，欢迎关注！

一、455.分发饼干

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int count=0;
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int startIndex = s.size()-1;
        for(int i=g.size()-1;i>=0;i--){
            if (startIndex>=0 && s[startIndex]>=g[i]){
                count++;
                startIndex--; // 用过的饼干不能再用
            }
        }
        return count;
    }
};

二、1005.K次取反后最大化的数组和

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        // 确定负数的个数
        int count =0;
        int result=0;
        int minabs =INT_MAX; 
        for(int i=0;i<nums.size();i++){
            if(nums[i]<0){
                count++;
            }
            if(abs(nums[i])<minabs){
                minabs = abs(nums[i]);
            }
        }
        if(count<k){
            for(int i=0;i<nums.size();i++){
                result+= abs(nums[i]);
            }
            if((k-count)%2==1){
                result -= 2* minabs; // 把正数取反
            }
        }
        else{
            for(int i=0;i<nums.size();i++){
                // 前k取负
                if(i<k){
                    result+= -nums[i];
                }
                else{
                    result+= nums[i];
                }
            }
        }
        return result;
    }
};

三、860.柠檬水找零

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five =0;
        int ten =0;
        int twenty =0;
        for(int bill:bills){
            if(bill==5){
                five++;
            }
            else if(bill==10){
                if(five==0){
                    // 没有五块找了
                    return false;
                }
                else{
                    five--;
                    ten++;
                }
            }
            else{
                // 20,优先找10+5
                if(ten>0&&five>0){
                    ten--;
                    five--;
                    twenty++;
                }
                else if(five>=3){
                    five-=3;
                    twenty++;
                }
                else{
                    // 找不开
                    return false;
                }
            }
        }
        return true;
    }
};