860.柠檬水找零
试了好几个方法没做出来。然后休息了一会，结果就想出来了。
我之前一直在顾虑会不会出现我用一种方法去找零20元，再下一个20元又需要找零的时候就没有足够的钱找零了。但其实这个顾虑是可以避免的：我们优先把十元钱找零出去，然后再找零五元。这样的话，就不会有本可以找的开，但是提前把小额的钱用出去的下场。
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int count_five_bills = 0;
int count_ten_bills = 0;
int count_twenty_bills = 0;
for(int i=0;i<bills.size(); i++){
if(bills[i] == 5){
count_five_bills++;
}
else if(bills[i] == 10){
count_ten_bills++;
if(count_five_bills>=1){
count_five_bills--;
}
else{
return false;
}
}
else{
if(count_ten_bills>=1 && count_five_bills>=1){
count_ten_bills--;
count_five_bills--;
}
else if(count_five_bills>=3){
count_five_bills = count_five_bills - 3;
}
else{
return false;
}
}
}
return true;
}
};
406.根据身高重建队列
早上的时候看会了昨天分糖果那道题。但是这道题还是没想出来。看了Carl的题解也是一知半解。真不知道出这种题的意义是什么。
class Solution {
public:
static bool 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>> res;
for(int i=0; i<people.size(); i++){
int pos = people[i][1];
res.insert(res.begin()+pos,people[i]);
}
return res;
}
};
这道题Carl还给出了用list来实现答案的办法。这个办法的好处就是利用了list善于insert的特性。我看了Carl的解释里说道vector数组在这道题里会反反复复的扩容（因为insert）。所以用list链表的话会省很多资源。
452. 用最少数量的箭引爆气球
按照自己的想法写出来了，可是他妈的超时了。
class Solution {
public:
static bool cmp(vector<int>a, vector<int>b){
if(a[0] == b[0]){
return a[1] < b[1];
}
return a[0] < b[0];
}
int findMinArrowShots(vector<vector<int>>& points) {
if(points.size() == 0){
return 0;
}
sort(points.begin(),points.end(),cmp);
int index = 0;
vector<vector<int>> range_list;
range_list.push_back(points[0]);
for(int i=1; i<points.size(); i++){
if(points[i][0] > range_list[index][1]){
range_list.push_back(points[i]);
index++;
}
else if(points[i][0] == range_list[index][1]){
range_list[index][0] = points[i][0];
range_list[index][1] = points[i][0];
}
else{
range_list[index][0] = max(points[i][0],range_list[index][0]);
range_list[index][1] = min(points[i][1],range_list[index][1]);
}
}
return range_list.size();
}
};
