1.找錢問題

本題的貪心策略在于我們希望就可能的保留作用大的5元

class Solution {
public:bool lemonadeChange(vector<int>& bills) {std::map<int ,int> _map;for(auto ch:bills){if(ch == 5) _map[ch]++;else if(ch == 10){if(_map[5] == 0) return false;else{_map[5]--;_map[ch]++;}}else if(ch == 20){//這里的判斷_map [5]!= 0 && _map[10] != 0其實是貪心我用10元代替兩張5if(_map [5]!= 0 && _map[10] != 0){_map[5]--;_map[10]--;_map[ch]++;}else if(_map[5] >= 3){_map[5] -= 3;_map[ch]++;}else return false;}}return true;}
};

題目鏈接：860. 檸檬水找零 - 力扣（LeetCode）

2.最大數

這道題涉及一個知識點：一個數比另一個數大那么轉換為字符串以后對應的大小關系并不會改變

那么對于 string A = "12"? string B = "23"? string C = "14".如果進行排序由于BA大于AB故B位于A的前面由于CA大于AC所以C位于A的前面? ? 故順序為：B C A那么BCA是不是他們組成的最大數呢這里顯然是，但是要以此類推就能知道這題我們只需要重載排序規則就能完成，當然這題還存在一些便捷條件比如如個排序數組的開頭是“0”說明這些數著的最大值就是0

class Solution {
public:static bool compare(int a,int b){std::string A = std::to_string(a);std::string B = std::to_string(b);std::string AB = A+B;std::string BA = B+A;return AB>BA;} string largestNumber(vector<int>& nums) {sort(nums.begin(),nums.end(),compare);string ret;for(auto ch:nums) ret+=std::to_string(ch);return ret[0] == '0'?"0":ret;}
};

題目鏈接：179. 最大數 - 力扣（LeetCode）

3.擺動序列

這個題目可以理解為找到一個子序列，滿足子序列內的元素時先增在減或者先減在增的，就類似正弦函數。

我們怎么才能找到最長的滿足條件的子序列呢，我先做了一個我就找極大值和極小值來組成這個子序列，然后就過了，很神奇，然后看了看題解才明白為什么

看這張圖，我們發現其實有三條可選擇的路徑但是其實本質上都是一樣的，都是上升區間取一個值然后在相鄰的下降區間取一個比自己小的數

那么我們的貪心策略就是直接去上升區間和下降區間的端點也就是極大值和極小值。

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int left = 0,right = 0;int ret = 0;for(int i = 0;i<nums.size()-1;i++){right = nums[i+1]-nums[i];if(right == 0) continue;else if(right*left<=0){left = right;ret++;}else continue;}return ret+1;}
};