深圳建网站制作维护,苏州网站建站,免费自助建站软件,电商网站开发平台实验目录#xff1a;
解题及思路学习
860. 柠檬水找零
在柠檬水摊上#xff0c;每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品#xff0c;#xff08;按账单 bills 支付的顺序#xff09;一次购买一杯。
每位顾客只买一杯柠檬水#xff0c;然后向你付 5 美元、10 美…目录
解题及思路学习
860. 柠檬水找零
在柠檬水摊上每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品按账单 bills 支付的顺序一次购买一杯。
每位顾客只买一杯柠檬水然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零也就是说净交易是每位顾客向你支付 5 美元。
注意一开始你手头没有任何零钱。
给你一个整数数组 bills 其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零返回 true 否则返回 false 。
示例 1
输入bills [5,5,5,10,20]
输出true思考对于bills如果支付的为5则刚好。如果支付的为10则找5如果支付20则可以找一个10一个5 或者 三个5。所以尽可能找零大的钱币。
局部最优遇到账单20优先消耗美元10完成本次找零。全局最优完成全部账单的找零。
class Solution {
public:bool lemonadeChange(vectorint bills) {int five 0, ten 0, twenty 0;for (int bill : bills) {if (bill 5) five;else if (bill 10) {if (five 0 ) return false;five--;ten;}else {if (ten 0 five 0) {ten--;five--;twenty;}else if (five 3) {five - 3;twenty;}else return false;}}return true;}
};时间复杂度: O(n)空间复杂度: O(1)
遇到感觉没有思路的题目可以静下心来把能遇到的情况分析一下只要分析到具体情况了一下子就豁然开朗了。
406. 根据身高重建队列
假设有打乱顺序的一群人站成一个队列数组 people 表示队列中一些人的属性不一定按顺序。每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi 前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue 其中 queue[j] [hj, kj] 是队列中第 j 个人的属性queue[0] 是排在队列前面的人。
示例 1
输入people [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]思考如果身高相同那么后面一个数字大的排在后面。如果后面数字相同则身高越低的排在前面。
在按照身高从大到小排序后
局部最优优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优最后都做完插入操作整个队列满足题目队列属性
class Solution {static bool cmp(const vectorint a, const vectorint b) {if (a[0] b[0]) return a[1] b[1];return a[0] b[0];}public:vectorvectorint reconstructQueue(vectorvectorint people) {sort(people.begin(), people.end(), cmp);listvectorint que;for (int i 0; i people.size(); i) {int position people[i][1];std::listvectorint::iterator it que.begin();while(position--) {it;}que.insert(it, people[i]);}return vectorvectorint(que.begin(), que.end());}
};时间复杂度O(nlog n n^2)空间复杂度O(n)
遇到两个维度权衡的时候一定要先确定一个维度再确定另一个维度。
如果两个维度一起考虑一定会顾此失彼。
452. 用最少数量的箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points 其中points[i] [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭若有一个气球的直径的开始和结束坐标为 xstartxend 且满足 xstart ≤ x ≤ xend则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后可以无限地前进。
给你一个数组 points 返回引爆所有气球所必须射出的 最小 弓箭数 。
示例 1
输入points [[10,16],[2,8],[1,6],[7,12]]
输出2思考先对数组进行排序之后遍历过程中将两个区间合并成一个区间。从第二区区间开始遍历如果前一个区间的最右边值小于该区间的最左值则需要一个弓箭。否则更新当前区间和前一个区间合并后的最右值。
局部最优当气球出现重叠一起射所用弓箭最少。全局最优把所有气球射爆所用弓箭最少。
class Solution {static bool cmp(const vectorint a, const vectorint b) {if (a[0] b[0]) return a[1] b[1];return a[0] b[0];}
public:int findMinArrowShots(vectorvectorint points) {sort(points.begin(), points.end(), cmp);int result 1;for (int i 1; i points.size(); i) {if (points[i - 1][1] points[i][0]) result;else if (points[i - 1][1] points[i][0]) {points[i][1] min(points[i - 1][1], points[i][1]);}}return result;}
};时间复杂度O(nlog n)因为有一个快排空间复杂度O(1)有一个快排最差情况(倒序)时需要n次递归调用。因此确实需要O(n)的栈空间
复盘总结
个人反思
1、区间问题很多都可以想想是不是需要进行先排序再处理。
2、遇到两个维度权衡的时候一定要先确定一个维度再确定另一个维度。
如果两个维度一起考虑一定会顾此失彼。
3、遇到感觉没有思路的题目可以静下心来把能遇到的情况分析一下只要分析到具体情况了一下子就豁然开朗了。
