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());
}
};
452. 用最少数量的箭引爆气球
思路
本题的思路在于使得一只箭尽可能射中更多的气球。
1.使气球按照起始位置进行排序。
2.判断之后气球的起始位置是否超过当前箭射中气球的末尾位置。
特殊情况是如果该气球的末尾位置小于当前箭射中气球的末尾位置，需要对末尾位置进行更新。
实现
class Solution {
public:
int findMinArrowShots(vector<vector
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)