第一题是柠檬水找零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;}
};