代码随想录刷题第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;
} else
return 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++;
else
points[i][1] = min(points[i - 1][1], points[i][1]);
}
return result;
}
};
原文地址:https://blog.csdn.net/weixin_74090791/article/details/136141883
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!