1.860柠檬水找零
贪心策略:先找大钱,再找小钱,20的不参与找钱
思路:用five,ten存放5元和10元的个数,初始化都是0,如果给的钱是5元,直接five++,如果给的是10元,只能找5,判断此时有没有5,有就找,没有就返回false,如果给的钱是20,分三种情况,1:有10元先找十元再找5元。2.没有10元,找三个5元。3.如果5元,10元都不够,返回false.
class Solution {
public:
//贪心算法先找大钱,再找小钱
bool lemonadeChange(vector<int>& bills) {
int five = 0,ten = 0;//代表两种的个数,因为20是就算你有也不能参与找零
int n = bills.size();
for(int i = 0;i<n;i++){
if(bills[i] == 5){
five++;
}else if(bills[i] == 10){
if(five==0){
return false;
}else{
five--;
}
ten++;
}else if(bills[i] == 20){
if(ten>0){
ten--;
if(five>0){
five--;
}else{
return false;
}
}else{
if(five>=3){
five = five - 3;
}else{
return false;
}
}
}
}
return true;
}
};
2.406根据身高重建队列
贪心策略:分为两次贪心。
第一次贪心:第一次贪心按照身高从高到低进行排列(如果同样的身高,那么个数小的在前面)
第二次贪心:遍历,按照个数的大小进行插入(由于前面的遍历保证了你前面的数一定是比你大的数,所以你只需要找到第i个位置插入即可)。
重点:比较器的设计
附加知识点:vector的扩容花费的时间比较长。所以另外一种方法使用list来做,相对来说花费时间比较少。
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>> result;
for(int i = 0;i<people.size();i++){
int position = people[i][1];
result.insert(result.begin()+position,people[i]);
}
return result;
}
};
3.用最少数量的箭引爆气球
贪心策略:【left,right】一个right能够覆盖更多的left。
思路:按照先left,再right的方式进行升序排列,然后直到遇到了一个position[i][0]>right此时计数+1的同时更新[left,right].
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];
}
//思路:先进行排序,然后按照顺序遍历,找到第i个位置能射的最多的个数
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(),points.end(),cmp);
int n = points.size();
if(n == 0)return 0;
int left = points[0][0];
int right = points[0][1];
int val = 1;
for(int i = 0;i<n;i++){
left = points[i][0];//由于这个是递增的,所以这个就是左边的最大值
right = min(right,points[i][1]);//代表这一块的右边的最小值
if(left>right){//代表超过了,此时对应的射箭次数就要+1
val++;
right = points[i][1];//此时要更新右边的位置
}
}
return val;
}
};