代码随想录day35 | 860.柠檬水找零 406. 根据身高重建队列 452. 用最少数量的箭引爆气球
860.柠檬水找零
思路
这道题看上去很复杂,其实只要把每种情况写下来,答案就已经解决了。
1.收到5
2.收到10
3.收到20
实现
点击查看代码
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int bill5 = 0;
int bill10 = 0;
for(int i = 0; i < bills.size(); i++) {
if(bills[i] == 5) {
bill5++;
}
else if(bills[i] == 10) {
if(bill5 > 0) {
bill5--;
bill10++;
}
else return false;
}
else {
if(bill10 > 0 && bill5 > 0) {
bill10--;
bill5--;
}
else if(bill5 >= 3) {
bill5 -= 3;
}
else return false;
}
}
return true;
}
};
复杂度分析
- 时间复杂度:O(n)
- 空间复杂度:O(1)
406. 根据身高重建队列
思路
需要两次贪心算法,第一次对身高进行排序,第二次按照名次进行插入。
本体可以用列表进行插入,从而减少时间复杂度,因为vector的扩容会增加时间。
实现
点击查看代码
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);
list<vector<int>> que;
for (int i = 0; i < people.size(); i++) {
int position = people[i][1];
auto it = que.begin();
while(position --) {
it++;
}
que.insert(it, people[i]);
}
return vector<vector<int>> (que.begin(), que.end());
}
};
####复杂度分析 * 时间复杂度:O(nlogn+n^n) * 空间复杂度:O(n)
452. 用最少数量的箭引爆气球
思路
本题的思路在于使得一只箭尽可能射中更多的气球。
1.使气球按照起始位置进行排序。
2.判断之后气球的起始位置是否超过当前箭射中气球的末尾位置。
特殊情况是如果该气球的末尾位置小于当前箭射中气球的末尾位置,需要对末尾位置进行更新。
实现
class Solution {
public:
int findMinArrowShots(vector<vector
>& points) {
sort(points.begin(), points.end());
int count = 1;
int end = points[0][1];
for(int i = 1; i < points.size(); i++) {
if(points[i][1] < end) {
end = points[i][1];
}
if(points[i][0] > end) {
++count;
end = points[i][1];
}
}
return count;
}
bool static cmp(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
};
复杂度分析
- 时间复杂度:O(nlogn)
- 空间复杂度:O(1)
原文地址:http://www.cnblogs.com/suodi/p/16852878.html
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。