代码随想录算法训练营Day33 || leetCode 860.柠檬水找零 || 406.根据身高重建队列 || 452. 用最少数量的箭引爆气球

860.柠檬水找零 

贪心的思路就是，先把最没用的钱给找出去。本题中，20元没法花出去，只有10和5能找零，但10只能找零20，而5可以找零10与20，所以就想办法把10先花出去即可。之后按照收入顺序来记录钱数并选择找零。如果某次钱的数目变为负数，则说明无法找零，输出错误。

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

406.根据身高重建队列 

先根据第一项排序，然后根据第二项的大小来插入数组

class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {if (a[0] == b[0]) return a[1] < b[1];return a[0] > b[0];}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort (people.begin(), people.end(), cmp);vector<vector<int>> que;for (int i = 0; i < people.size(); i++) {int position = people[i][1];que.insert(que.begin() + position, people[i]);}return que;}
};

452. 用最少数量的箭引爆气球

将数组按照右边界排序，只有当前的最小右边界比下一个左边界大，那就只需要一箭，反之则需要两只箭，之后再更新右边界，继续判断。

class Solution {
public:static bool cmp(const vector<int>& a,const vector<int>& b){return a[1] < b[1];}int findMinArrowShots(vector<vector<int>>& points) {if (points.empty()) return 0;sort(points.begin(),points.end(),cmp);int pos = points[0][1];int ans = 1;for (auto& a: points){if (a[0] > pos){pos = a[1];ans++;}}return ans;}
};