【刷题26】贪心—柠檬水找0、将数组和减半的最少操作次数、最大数

一、柠檬水找0

题目：

思路：

• 分别用3个变量来充当5元、10元和20元张数的计数器
• 如果数组的第一个不是5元，直接返回False
• 遍历数组，是5元，five++
• 是10元，five-1，ten++
• 是20元，要尽可能保留多的5元，所以有10元就先用10元

代码：

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        if(bills[0] == 10 || bills[0] == 20) 
        {
            return false;
        }
        int five = 0, ten = 0, twenty = 0;
        for(auto& e : bills)
        {
            if(e == 5) five++;
            else if(e == 10)
            {
                five--;
                ten++;
            }
            else
            {
                if(ten > 0 && five > 0)
                {
                    ten--;
                    five--;
                    twenty++;
                }
                else if(five >= 3)
                {
                    five -= 3;
                    twenty++;
                }
                else return false;
            }
        }
        return true;
    }
};

二、将数组和减半的最少操作次数

题目：

思路：

• 数组和计算出来，然后数组和减去数组中的最大元素的一半为一次操作，当数组和减到原来数组和的一半或者小于原来的一半，就返回操作次数
• 用大堆放入数组元素

代码：

class Solution {
public:
    int halveArray(vector<int>& nums) {
        priority_queue<double> pq;
        double sum = 0;
        for(auto &e : nums) 
        {
            pq.push(e);
            sum += e;
        }
        double k = sum / 2.0;
        int ret = 0;
        while(sum > k)
        {
            double tmp = pq.top();
            tmp /= 2.0;
            pq.pop();
            pq.push(tmp);
            sum -= tmp;
            ret++;
        }
        return ret;
    }
};

三、最大数

题目：

思路：

• ab > ba，a在前，b在后；ba > ab，b在前，a在后；相等顺序无所谓
• 数组元素转换为字符串
• 最后细节处理，如果第一个字符为0，就返回字符串0，因为后面一定是字符串0

代码：

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> strs;
        for(int i=0; i<nums.size(); i++)
        {
            string s = to_string(nums[i]);
            strs.push_back(s);
        }
        //
        sort(strs.begin(), strs.end(), [](string& s1, string& s2){
            return s1+s2 > s2+s1;
        });
        //
        string ret;
        for(auto& e : strs) ret += e;
        if(strs[0] == "0") return "0";
        return ret;
    }
};

原文地址：https://blog.csdn.net/2301_77459845/article/details/145192351

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！