860.柠檬水找零 题目链接
思路
三种情况,一种贪心,在bill为20时,有一次贪心选择:优先考虑先找10+5,再考虑找3*5,因为5可以用于bill=10和bill=20两种情况
解题方法
第一种:bill=5,直接收
第二种;bill=10,若five>0,five--,ten++;否则return false;
第三种:bill=20,(优先考虑)若five>0&&ten>0,five--,ten--;若five>2,five-=3;否则return false;
for循环结束后,上述false都没有遇到,return true;
Code
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five=0;
int ten=0;
for(int bill:bills)
{
if(bill==5)five++;
if(bill==10)
{
if(five==0)return false;
else {
five--;
ten++;
}
}
if(bill==20)
{
if(five>0&&ten>0)
{
five--;
ten--;
}
else if(five>2){
five-=3;
}
else return false;
}
}
return true;
}
};
复杂度
时间复杂度
O(n)
空间复杂度
O(1)
406.根据身高重建队列 题目链接
思路
两种情况:先排身高(从大到小),还是先排K值(从小到大)
选择先排身高,然后排k(从小到大)
解题方法
先排身高,再排k,则从后往前插入时,就不需要再考虑身高,k值就插入到和数组下标相同的位置
Code
class Solution {
public:
static bool cmp(const vector<int>&a,const 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>>queue;
for(int i=0;i<people.size();i++)
{
int position=people[i][1];
queue.insert(queue.begin()+position,people[i]);
}
return queue;
}
};
复杂度
时间复杂度
O(nlogn+n^2)
空间复杂度
O(n)
452. 用最少数量的箭引爆气球 题目链接
思路
当气球出现重叠的区域,一起射,用箭最少
解题方法
如果气球重叠了,更新i的右边界为i和i-1的右边界的最小值,如果没有,result++。
Code
class Solution {
private:
static bool cmp(const vector<int>&a,const vector<int>&b)
{
return a[0]<b[0];
}
public:
int findMinArrowShots(vector<vector<int>>& points) {
int result=1;
if(points.size()==0)return 0;
sort(points.begin(),points.end(),cmp);
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;
}
};
复杂度
时间复杂度
O(nlogn)
空间复杂度
O(1)