企业营销网站有哪些,太白 网站建设,固定链接 wordpress 不起作用,wordpress 当前分类id文章目录 Leetcode 860.柠檬水找零Leetcode 406.根据身高重建队列Leetcode 452. 用最少数量的箭引爆气球 Leetcode 860.柠檬水找零
题目链接#xff1a;Leetcode 860.柠檬水找零 题目描述#xff1a; 在柠檬水摊上#xff0c;每一杯柠檬水的售价为 5 美元。顾客排队购买你的… 文章目录 Leetcode 860.柠檬水找零Leetcode 406.根据身高重建队列Leetcode 452. 用最少数量的箭引爆气球 Leetcode 860.柠檬水找零
题目链接Leetcode 860.柠檬水找零 题目描述 在柠檬水摊上每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品按账单 bills 支付的顺序一次购买一杯。
每位顾客只买一杯柠檬水然后向你付 5 美元、10美元或 20 美元。你必须给每个顾客正确找零也就是说净交易是每位顾客向你支付 5 美元。
注意一开始你手头没有任何零钱。
给你一个整数数组 bills 其中 bills[i]是第 i 位顾客付的账。如果你能给每位顾客正确找零返回 true 否则返回 false 。 思路 本题还是很简单的我们只需要分情况讨论
对于5美元的顾客直接收下即可对于10美元的顾客我们需要判断5美元的零钱是否大于等于1张对于20美元的顾客我们先判断能否使用105的组合再判断5美元的零钱是否大于等于3张这里体现了贪心思想
代码如下
class Solution {
public:bool lemonadeChange(vectorint bills) {int five 0, ten 0; //只需记录这两种钞票用于找零for (int bill : bills) {if (bill 5) {five;}if (bill 10) {if (five 0)return false;ten;five--;}if (bill 20) {if (five 0 ten 0) { //贪心策略优先使用10来找零ten--;five--;} else if (five 3) {five - 3;} elsereturn false;}}return true;}
};时间复杂度: O ( n ) O(n) O(n)空间复杂度: O ( 1 ) O(1) O(1)
Leetcode 406.根据身高重建队列
题目链接Leetcode 406.根据身高重建队列 题目描述 假设有打乱顺序的一群人站成一个队列数组 people 表示队列中一些人的属性不一定按顺序。每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi 前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue 其中 queue[j] [hj, kj] 是队列中第 j 个人的属性queue[0] 是排在队列前面的人。 思路 本题和Leetcode135 分发糖果这道题很像都是需要考虑两个维度而对于两个维度的贪心题目我们需要先确定一个维度再确定另一个维度。 如果按照k来从小到大排序排完之后会发现k的排列并不符合条件身高也不符合条件两个维度哪一个都没确定下来。
那么按照身高h来排序呢身高一定是从大到小排身高相同的话则k小的站前面让高个子在前面。此时我们可以确定一个维度了就是身高前面的节点一定都比本节点高再按照k为下标重新插入队列就可以了。 局部最优优先按身高高的people的k来插入。插入操作过后的people满足队列属性 全局最优最后都做完插入操作整个队列满足题目队列属性
代码如下
class Solution {
public://按照身高从大到小排序身高相同则k小的在前面static bool cmp(const vectorint a, 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);vectorvectorint que;for (int i 0; i people.size(); i) {int position people[i][1];que.insert(que.begin() position, people[i]);}return que;}
};由于动态数组vector底层是普通数组实现的我们都知道在数组内插入删除元素效率很低因此可以考虑用链表list优化。
代码如下利用链表list提高插入效率
class Solution {
public://按照身高从大到小排序身高相同则k小的在前面static bool cmp(const vectorint a, 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);listvectorint que; // list底层是链表插入效率高for (int i 0; i people.size(); i) {int position people[i][1];auto it que.begin();while (position--) { //寻找插入位置it;}que.insert(it, people[i]);}return vectorvectorint(que.begin(), que.end());}
};时间复杂度 O ( n l o g n n 2 ) O(nlog n n^2) O(nlognn2)空间复杂度 O ( n ) O(n) O(n)
Leetcode 452. 用最少数量的箭引爆气球
题目链接 Leetcode 452. 用最少数量的箭引爆气球 题目描述 在二维空间中有许多球形的气球。对于每个气球提供的输入是水平方向上气球直径的开始和结束坐标。
一支弓箭可以沿着 x轴从不同点完全垂直地射出。在坐标 x 处射出一支箭若有一个气球的直径的开始和结束坐标为 xstartxend 且满足 xstart ≤ x ≤ xend则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后可以无限地前进。我们想找到使得所有气球全部被引爆所需的弓箭的最小数量。
给你一个数组 points 其中 points [i] [xstart,xend] 返回引爆所有气球所必须射出的最小弓箭数。 思路 本题看似是二维空间实际上只需考虑气球的横坐标范围是否重叠就行了纵坐标只是方便描述弓箭射出的出题背景。首先对气球左边界排序然后遍历横坐标判断当前的i和i-1是否重叠如果不重叠result重叠则更新右边界。 这里有一个关键点就是如何更新右边界我们需要对points[i]和points[i-1]的右边界取最小值只有这样才方便后续继续判断是否重叠。
代码如下
class Solution {
public:static bool cmp(const vectorint a, const vectorint b) {if (a[0] b[0])return a[1] b[1];return a[0] b[0];}int findMinArrowShots(vectorvectorint points) {if (points.size() 0)return 0;int result 1;sort(points.begin(), points.end(), cmp); //按照左边界大小进行排序for (int i 1; i points.size(); i) {if (points[i][0] points[i-1][1]) { //如果没有重叠则弓箭数1result;} else { //否则更新右边界points[i][1] min(points[i - 1][1], points[i][1]);}}return result;}
};时间复杂度 O ( n l o g n ) O(nlog n) O(nlogn)空间复杂度 O ( 1 ) O(1) O(1) 不过快速排序的空间复杂度还体现在递归上了 最优的情况下空间复杂度为 O ( l o g n ) O(logn) O(logn)每一次都平分数组的情况 最差的情况下空间复杂度为 O ( n ) O( n ) O(n) 退化为冒泡排序的情况 总结 很多贪心类题目第一次做几乎不太可能想到因此需要多做题拓宽视野多复习巩固
最后如果文章有错误请在评论区或私信指出让我们共同进步
