代码随想录刷题第34天

第一题是柠檬水找零https://leetcode.cn/problems/lemonade-change/，感觉并没有特别靠近贪心算法，可供讨论的情况非常少，5元收下，10元返5元，20元返15元，对各种找零情况讨论一下即可。

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

第二题是根据身高重建队列https://leetcode.cn/problems/queue-reconstruction-by-height/description/，两个维度，先确定身高，再确定人数，身高从大到小排列后对人数放心插入即可，因为前方都是大数，小数的插入并不影响第二维度。

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) {vector<vector<int>> queue;sort(people.begin(), people.end(), cmp);for (int i = 0; i < people.size(); i++){int position = people[i][1];queue.insert(queue.begin() + position, people[i]); }return queue;}
};

第三题是射气球https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/，想用最小的弓箭数射最多的气球，使气球尽可能重叠就可以了。所以需要将气球左区间进行排列，判断相邻气球的左右区间情况，若当前气球右区间大于上一气球左区间，则需要弓箭数加一。若不大于，则将两气球视为重叠气球，同时更新一下重叠气球的右区间，一遍判断与下一气球的重叠情况。

class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] < b[0];}int findMinArrowShots(vector<vector<int>>& points) {if (points.size() == 0)return 0;sort(points.begin(), points.end(), cmp);int result = 1;for (int i = 1; i < points.size(); i++) {if (points[i][0] > points[i - 1][1])result++;elsepoints[i][1] = min(points[i - 1][1], points[i][1]);}return result;}
};