舟山网站开发,响应式购物网站设计,石家庄建设集团,芜湖哪些公司做公司网站题目1#xff1a;860 柠檬水找零
题目链接#xff1a;860 柠檬水找零
题意
一杯柠檬水5美元#xff0c;每位顾客只买一杯柠檬水#xff0c;支付5美玉#xff0c;10美元#xff0c;20美元#xff0c;必须正确找零
开始时并没有零钱 若可以正确找零#xff0c;则返回…题目1860 柠檬水找零
题目链接860 柠檬水找零
题意
一杯柠檬水5美元每位顾客只买一杯柠檬水支付5美玉10美元20美元必须正确找零
开始时并没有零钱 若可以正确找零则返回true反之返回false
贪心策略
尽可能保留5美元的零钱5更万能既能对10找零又能对20找零 优先使用10进行找零
代码
class Solution {
public:bool lemonadeChange(vectorint bills) {if(bills[0]!5) return false;int nums5 0;int nums10 0;int nums20 0;for(int i0;ibills.size();i){if(bills[i]5) nums5 5;if(bills[i]10){if(nums5!0){nums5 - 5;nums10 10;}else return false;}if(bills[i]20){if(nums10!0 nums5!0){nums10 - 10;nums5 - 5;}else if(nums515){nums5 - 15;}else return false;}}return true;}
};
时间复杂度: O(n)空间复杂度: O(1)
题目2406 根据身高重建队列
题目链接406 根据身高重建队列
题意
people[i][hiki] 表示第i个人的身高是hi前面有ki个身高大于等于hi的人按正确顺序重组队列
贪心策略
先确定一个维度先比较h的维度按照h从大到小排序然后再比较k的维度 按照k从小到大往前插入 数组
代码
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) {vectorvectorint queue;//身高按照降序排序从大到小排序sort(people.begin(),people.end(),cmp);//根据k插入到队列前面 注意是插入到队列哦不是peoplefor(int i0;ipeople.size();i) queue.insert(queue.begin()people[i][1],people[i]);return queue;}
};
时间复杂度O(nlog n n^2)空间复杂度O(n)
注意
使用vector是非常费时的C中vector可以理解是一个动态数组底层是普通数组实现的如果插入元素大于预先普通数组大小vector底部会有一个扩容的操作即申请两倍于原先普通数组的大小然后把数据拷贝到另一个更大的数组上。
所以使用vector动态数组来insert是费时的插入再拷贝的话单纯一个插入的操作就是O(n^2)了甚至可能拷贝好几次就不止O(n^2)了。
链表
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) {listvectorint que;//身高按照降序排序从大到小排序sort(people.begin(),people.end(),cmp);//根据k插入到队列前面 注意是插入到队列哦不是peoplefor(int i0;ipeople.size();i){int position people[i][1];std::listvectorint::iterator itque.begin();while(position--){it;}que.insert(it,people[i]);}return vectorvectorint(que.begin(),que.end());}
};
时间复杂度O(nlog n n^2)空间复杂度O(n)
题目3452 用最少数量的箭引爆气球
题目链接452 用最少数量的箭引爆气球
题意
points[i][xstartxend]表示水平直径在xstart和xend之间的气球y坐标未知
一支箭可以从垂直x轴的任意位置x处射出一直前进若xstartxxend气球会被引爆求最小弓箭数
贪心策略
重叠区间的气球用1个箭射中箭的数量最少 代码
class Solution {
public:static bool cmp(vectorint a, vectorint b){//左边界升序return a[0]b[0];}int findMinArrowShots(vectorvectorint points) {//对数组的左边界升序排序sort(points.begin(),points.end(),cmp);//收集弓箭数int result 1;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(nlog n)因为有一个快排空间复杂度O(1)有一个快排最差情况(倒序)时需要n次递归调用。因此确实需要O(n)的栈空间
