【算法训练 day37 柠檬水找零、长度最小的子数组、用最少数量的箭引爆气球】

本文主要是介绍【算法训练 day37 柠檬水找零、长度最小的子数组、用最少数量的箭引爆气球】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 一、柠檬水找零-LeetCode 860
    • 思路
    • 实现代码
    • 个人问题
    • 总结
  • 二、根据身高重建队列-LeetCode 406
    • 思路
    • 实现代码
    • 个人问题
    • 总结
  • 三.用最少数量的箭引爆气球-LeeCode 406
    • 思路
    • 实现代码
    • 个人问题
    • 总结


一、柠檬水找零-LeetCode 860

Leecode链接: leetcode 860
文章链接: 代码随想录
视频链接: B站

在柠檬水摊上,每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。

每位顾客只买一杯柠檬水,然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5 美元。

注意,一开始你手头没有任何零钱。

给你一个整数数组 bills ,其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零,返回 true ,否则返回 false 。

示例:

输入:bills = [5,5,5,10,20]
输出:true
解释:
前 3 位顾客那里,我们按顺序收取 35 美元的钞票。
第 4 位顾客那里,我们收取一张 10 美元的钞票,并返还 5 美元。
第 5 位顾客那里,我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零,所以我们输出 true。

思路

对数组的元素进行计数,如果是5就加1,如果是10,就判断5的个数是否大于0,大于0就将5的个数减一并将10的个数加一否则就返回false。如果是20,就判断5的个数是否大于3或者有1个5跟一个10,否则返回false。

实现代码

//cpp
class Solution {
public:bool lemonadeChange(vector<int>& bills) {int count5 = 0;int count10 = 0;for(int i = 0;i<bills.size();i++){if(bills[i] == 5){count5++;}else if(bills[i] == 10){if(count5 <= 0){return false;}count10 ++;count5 --;}else{if(count5>0&&count10>0){count5 --;count10--;}else if(count5>=3){count5 -= 3;}else {return false;}}}return true;}
};

个人问题

无。

总结

整体比较简单。


二、根据身高重建队列-LeetCode 406

Leecode链接: LeetCode 406
文章链接: 代码随想录
视频链接: B站

假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ,前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ,其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性(queue[0] 是排在队列前面的人)。

示例:

输入: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]]
解释:
编号为 0 的人身高为 5 ,没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ,没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ,有 2 个身高更高或者相同的人排在他前面,即编号为 01 的人。
编号为 3 的人身高为 6 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。
编号为 4 的人身高为 4 ,有 4 个身高更高或者相同的人排在他前面,即编号为 0123 的人。
编号为 5 的人身高为 7 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

思路

题目首先对数组的首个元素按照从大到小排序,如果相同,则按照第二个元素从小到大排序。排完序后再根据第二个元素从小到大进行排序。至于理由可以这么考虑,第一次排完序后,最后面的首个元素肯定是最小的,这也就意味着它可以直接根据它自身的第二个元素挑选要插入的位置,反正他前面都是比他大的,需要插的位置直接按照第二个元素来就行。

实现代码

//cpp
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) {list<vector<int>> que;sort(people.begin(),people.end(),cmp);for(int i = 0;i<people.size();i++){int p = people[i][1];std::list<vector<int>>::iterator it = que.begin();// while(p--){//     it++;// }advance(it,p);que.insert(it,people[i]);}return vector<vector<int>>(que.begin(),que.end());}
};

个人问题

没有想到怎么做。

总结

题目思路很巧妙,还是需要进行两次的排序,属于想不到就做不出来。


三.用最少数量的箭引爆气球-LeeCode 406

Leecode链接: LeetCode 406
文章链接: 代码随想录
视频链接: B站

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭,若有一个气球的直径的开始和结束坐标为 xstart,xend, 且满足 xstart ≤ x ≤ xend,则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后,可以无限地前进。

给你一个数组 points ,返回引爆所有气球所必须射出的 最小 弓箭数 。
示例:

输入:points = [[10,16],[2,8],[1,6],[7,12]]
输出:2
解释:气球可以用2支箭来爆破:
-在x = 6处射出箭,击破气球[2,8][1,6]-在x = 11处发射箭,击破气球[10,16][7,12]

思路

初始设置res为1,因为第一个气球一定需要一枚箭。i初始值为1,循环检查第i个气球跟第i-1个气球是否重合,重合了就将第i个气球的右坐标更新为第i-1个气球的右坐标,没有重合就将res自加1,并开始下一个循环。

实现代码

//cpp
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) {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;}
};

个人问题

思路有但是代码没写出来。

总结

思路有但是卡在了如何保存上一个重叠气球的坐标值上,解决办法是如果重合了,就保存在本次循环i表示的右坐标上,因为下次对比所对比的就是上一次循环的右节点的右坐标是否大于本次循环的左坐标。

这篇关于【算法训练 day37 柠檬水找零、长度最小的子数组、用最少数量的箭引爆气球】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/996408

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];