代码随想录算法训练营Day34 | 860.柠檬水找零 406.根据身高重建队列 452. 用最少数量的箭引爆气球
LeetCode 860.柠檬水找零
题目链接:LeetCode 860.柠檬水找零
思路:
三种情况:
- 5元直接收下;
- 10元直接找5元;
- 20元优先找10元+5元,其次找3个5元
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0, twenty = 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(five >=3){
five -= 3;
}
else return false;
}
}
return true;
}
};
注意 :
- 注意 找钱时需判断是否足够,否则return false
LeetCode 406.根据身高重建队列
题目链接:LeetCode 406.根据身高重建队列
思路:
- vector实现和linklist实现
class Solution {
public:
bool static cmp(vector<int> a, 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);
vector<vector<int>> que;
for(int i=0; i<people.size(); i++){
que.insert(que.begin()+people[i][1], people[i]);
}
return que;
}
};
// 链表实现
class Solution {
public:
bool static cmp(vector<int> a, 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];
list<vector<int>>::iterator it = que.begin();
while (position--) { // 寻找在插入位置
it++;
}
que.insert(it, people[i]);
}
return vector<vector<int>>(que.begin(),que.end()) ;
}
};
LeetCode 452. 用最少数量的箭引爆气球
题目链接:LeetCode 452. 用最少数量的箭引爆气球
思路:
左区间和右区间最小值判断重叠。
class Solution {
public:
bool static cmp(vector<int>& a, vector<int>& b){
return a[0] < b[0];
}
int findMinArrowShots(vector<vector<int>>& points) {
if(points.size() <=1) return points.size();
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;
}
};