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