上海信息科技有限公司软件网站开发,wordpress文章不显示发布时间,品牌注册号是哪个,网站和做游戏860.柠檬水找零
本题看上好像挺难#xff0c;其实挺简单的#xff0c;大家先尝试自己做一做。 https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html 题目大意#xff1a; 在柠檬水摊上#xff0c;每一杯柠檬水的售价为 5 美元。
顾客排…860.柠檬水找零
本题看上好像挺难其实挺简单的大家先尝试自己做一做。 https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html 题目大意 在柠檬水摊上每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品按账单 bills 支付的顺序一次购买一杯。
每位顾客只买一杯柠檬水然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零也就是说净交易是每位顾客向你支付 5 美元。
注意一开始你手头没有任何零钱。
如果你能给每位顾客正确找零返回 true 否则返回 false 。 思路
情况一账单是5直接收下。情况二账单是10消耗一个5增加一个10情况三账单是20优先消耗一个10和一个5如果不够再消耗三个5
class Solution {
public:bool lemonadeChange(vectorint bills) {int five 0, ten 0, twenty 0;for (int bill : bills) {// 情况一if (bill 5) five;// 情况二if (bill 10) {if (five 0) return false;ten;five--;}// 情况三if (bill 20) {// 优先消耗10美元因为5美元的找零用处更大能多留着就多留着if (five 0 ten 0) {five--;ten--;twenty; // 其实这行代码可以删了因为记录20已经没有意义了不会用20来找零} else if (five 3) {five - 3;twenty; // 同理这行代码也可以删了} else return false;}}return true;}
};时间复杂度: O(n) 空间复杂度: O(1)
406.根据身高重建队列
本题有点难度和分发糖果类似不要两头兼顾处理好一边再处理另一边。 https://programmercarl.com/0406.%E6%A0%B9%E6%8D%AE%E8%BA%AB%E9%AB%98%E9%87%8D%E5%BB%BA%E9%98%9F%E5%88%97.html 题目大意假设有打乱顺序的一群人站成一个队列数组 people 表示队列中一些人的属性不一定按顺序。每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi 前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue 其中 queue[j] [hj, kj] 是队列中第 j 个人的属性queue[0] 是排在队列前面的人。 思路 局部最优优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优最后都做完插入操作整个队列满足题目队列属性
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];}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;}
};时间复杂度O(nlog n n^2) 空间复杂度O(n)
使用链表
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底层是链表实现插入效率比vector高的多for (int i 0; i people.size(); i) {int position people[i][1]; // 插入到下标为position的位置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. 用最少数量的箭引爆气球
本题是一道 重叠区间的题目好好做一做因为明天三道题目都是 重叠区间。 https://programmercarl.com/0452.%E7%94%A8%E6%9C%80%E5%B0%91%E6%95%B0%E9%87%8F%E7%9A%84%E7%AE%AD%E5%BC%95%E7%88%86%E6%B0%94%E7%90%83.html 题目大意在二维空间中有许多球形的气球。对于每个气球提供的输入是水平方向上气球直径的开始和结束坐标。由于它是水平的所以纵坐标并不重要因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭若有一个气球的直径的开始和结束坐标为 xstartxend 且满足 xstart ≤ x ≤ xend则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后可以无限地前进。我们想找到使得所有气球全部被引爆所需的弓箭的最小数量。
给你一个数组 points 其中 points [i] [xstart,xend] 返回引爆所有气球所必须射出的最小弓箭数。
思路局部最优当气球出现重叠一起射所用弓箭最少。全局最优把所有气球射爆所用弓箭最少。
class Solution {
private:static bool cmp(const vectorint a, const vectorint b) {return a[0] b[0];}
public:int findMinArrowShots(vectorvectorint points) {if (points.size() 0) return 0;sort(points.begin(), points.end(), cmp);int result 1; // points 不为空至少需要一支箭for (int i 1; i points.size(); i) {if (points[i][0] points[i - 1][1]) { // 气球i和气球i-1不挨着注意这里不是result; // 需要一支箭}else { // 气球i和气球i-1挨着points[i][1] min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界}}return result;}
};时间复杂度O(nlog n)因为有一个快排 空间复杂度O(1)有一个快排最差情况(倒序)时需要n次递归调用。因此确实需要O(n)的栈空间
