算法训练营第35天|LeetCode 860.柠檬水找零 406.根据身高重建队列 452.用最少数量的箭引爆气球
LeetCode 860.柠檬水找零
题目链接：
LeetCode 860.柠檬水找零
解题思路：
枚举法，写出所有找零的情况。
代码:
class Solution {
public:bool lemonadeChange(vector<int>& bills) {if(bills[0]!=5) return false;unordered_map<int,int>map_count={{5,0},{10,0},{20,0}};map_count[bills[0]]++;for(int i=1;i<bills.size();i++){if(bills[i]==5){map_count[bills[i]]++;}else if(bills[i]==10){if(map_count[5]>0){map_count[5]--;map_count[10]++;}else{return false;break;}}else{if(map_count[10]>0&&map_count[5]>0){map_count[10]--;map_count[5]--;}else if(map_count[5]>=3){map_count[5]-=3;}else{return false;break;}}}return true;}
};LeetCode 406.根据身高重建队列
题目链接：
LeetCode 406.根据身高重建队列
解题思路：
先按第一位从大到小排序，之后根据第二位决定插入位置。
代码:
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>>que;for(int i=0;i<people.size();i++){int Index = people[i][1];que.insert(que.begin()+Index,people[i]);}return que;}
};LeetCode 452.用最少数量的箭引爆气球
题目链接：
LeetCode 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) {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],points[i-1][1]);}}return result;}
};