在电脑上怎么做网站,菏泽市住房和城乡建设路网站,网络安装,网站开发_运行及维护860.柠檬水找零 题目链接
思路
三种情况#xff0c;一种贪心#xff0c;在bill为20时#xff0c;有一次贪心选择#xff1a;优先考虑先找105#xff0c;再考虑找3*5#xff0c;因为5可以用于bill10和bill20两种情况
解题方法
第一种#xff1a;bill5,直接收
第二种… 860.柠檬水找零 题目链接
思路
三种情况一种贪心在bill为20时有一次贪心选择优先考虑先找105再考虑找3*5因为5可以用于bill10和bill20两种情况
解题方法
第一种bill5,直接收
第二种bill10若five0five--ten否则return false;
第三种bill20(优先考虑)若five0ten0,five--,ten--;若five2,five-3否则return false;
for循环结束后上述false都没有遇到return true;
Code
class Solution {
public:bool lemonadeChange(vectorint bills) {int five0;int ten0;for(int bill:bills){if(bill5)five;if(bill10){if(five0)return false;else {five--;ten;}}if(bill20){if(five0ten0){five--;ten--;}else if(five2){five-3;}else return false;}}return true;}
};
复杂度
时间复杂度
O(n)
空间复杂度
O(1)
406.根据身高重建队列 题目链接
思路
两种情况先排身高从大到小还是先排K值从小到大
选择先排身高然后排k从小到大
解题方法
先排身高再排k,则从后往前插入时就不需要再考虑身高k值就插入到和数组下标相同的位置
Code
class Solution {
public:static bool cmp(const vectorinta,const 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);vectorvectorintqueue;for(int i0;ipeople.size();i){int positionpeople[i][1];queue.insert(queue.begin()position,people[i]);}return queue;}
};
复杂度
时间复杂度
O(nlognn^2)
空间复杂度
O(n)
452. 用最少数量的箭引爆气球 题目链接
思路
当气球出现重叠的区域一起射用箭最少
解题方法 如果气球重叠了更新i的右边界为i和i-1的右边界的最小值如果没有result。
Code
class Solution {
private:static bool cmp(const vectorinta,const vectorintb){return a[0]b[0];}
public:int findMinArrowShots(vectorvectorint points) {int result1;if(points.size()0)return 0;sort(points.begin(),points.end(),cmp);for(int i1;ipoints.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;}
};
复杂度
时间复杂度
O(nlogn)
空间复杂度
O(1)
