【刷题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;}
};