本文介绍: 找零只用分三种情况即可需要注意的是情况三,对20找零时应该先判断一个10和一个5的情况,因为5是万能的,先把5用完的话情况二就不能满足了。
860.柠檬水找零
题目链接:柠檬水找零
找零只用分三种情况即可
- 情况一:账单是5,直接收下。
- 情况二:账单是10,消耗一个5,增加一个10
- 情况三:账单是20,优先消耗一个10和一个5,如果不够,再消耗三个5
需要注意的是情况三,对20找零时应该先判断一个10和一个5的情况,因为5是万能的,先把5用完的话情况二就不能满足了。
// 时间复杂度: O(n)
// 空间复杂度: O(1)
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int f = 0, t = 0, tw = 0;
if (bills[0] != 5) return false;
for (int i = 0; i < bills.size(); ++i)
{
if (bills[i] == 5)
{
f++;
}
if (bills[i] == 10)
{
if (f != 0)
{
f--;
t++;
}
else
{
return false;
}
}
if (bills[i] == 20)
{
if (f != 0 && t != 0)
{
f -= 1;
t -= 1;
tw++;
}
else if (f >= 3)
{
f -= 3;
tw++;
}
else
{
return false;
}
}
}
return true;
}
};
406.根据身高重建队列
题目链接:根据身高重建队列
思路:现根据身高由大到小排序,相同身高按比他身高高的人数由少到多排序。遍历排序后的people数组,按身高高的人数插入队列,因为身高已经由大到排序了,身高低的人插到前面不会影响后面的判断结果。
// 时间复杂度:O(nlog n + n^2)
// 空间复杂度:O(n)
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 pos = people[i][1];
queue.insert(queue.begin() + pos, people[i]);
}
return queue;
}
};
452. 用最少数量的箭引爆气球
题目链接:用最少数量的箭引爆气球
思路:先按每个区间的最小值对这些区间由小到大排序,判断前一个区间的最大值是否大于当前区间的最小值,若小于等于则需要加一根箭,若大于则更新前一个区间的最大值,更新为这两个区间中最大值较小的那个(以满足两个以上区间重叠的情况),然后继续向后遍历。
// 时间复杂度:O(nlog n),因为有一个快排
// 空间复杂度:O(1),有一个快排,最差情况(倒序)时,需要n次递归调用。因此确实需要O(n)的栈空间
class Solution {
public:
static bool cmp (const vector<int>& a, const vector<int>& b)
{
return a[0] < b[0];
}
int findMinArrowShots(vector<vector<int>>& points) {
if (points.size() == 0) return 0;
sort(points.begin(), points.end(), cmp);
int ret = 1;
for (int i = 1; i < points.size(); ++i)
{
if (points[i - 1][1] < points[i][0])
{
ret++;
}
else
{
points[i][1] = min(points[i - 1][1], points[i][1]); // 更新右边界
}
}
return ret;
}
};
原文地址:https://blog.csdn.net/qq_41943352/article/details/136018049
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_65913.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。