柠檬水 蚂蚁庄园,柠檬水店
墨初 知识笔记 123阅读
个人主页Sherry的成长之路
学习社区Sherry的成长之路个人社区
专栏链接练题
长路漫漫浩浩万事皆有期待
文章目录 柠檬水找零根据身高重建队列用最少数量的箭引爆气球总结
柠檬水找零
860. 柠檬水找零 - 力扣LeetCode
每一杯柠檬水5块钱能收到的面额只有510和20三种金额的钱币。一开始我没有记录怎么找零将三者都化为了自己得到了多少钱然后判断是否能找零。后来发现不对劲必须要记录下来你获得的钱币各面额的都是多少但是实际上20元的钱我们可以不做记录因为20块钱的一张纸币找不了钱最大人家就给20块钱而五块钱和十块钱能找开10块钱和20块钱的我们需要将它们分别记录下来一共有多少张。如何存钱的思路明确了就好办了每次遇到需要找钱的时候我们判断一下有没有零钱就可以了。
class Solution {public: bool lemonadeChange(vector<int>& bills) { int target0; map<int,int>hash_map; for(int i0;i<bills.size();i){ if(bills[i]5)hash_map[5]; else if(bills[i]10)hash_map[10]; targetbills[i]-5; if(target5){ if(hash_map[5])hash_map[5]--; else return false; } else if(target15){ if(hash_map[10]&&hash_map[5]){ hash_map[10]--;hash_map[5]--; } else if(hash_map[5]>3){ hash_map[5]-3; } else return false; } } return true; }};这里我用了数组vecor来存储五元钱和十元钱都获得了几张并且需要注意的是如果我们碰到20元需要找15的时候应该尽量使用先看有没有10元纸币的策略如果没有再找三个五元因为十元只能找开20元要合理使用避免找10元时候5元不够。
当然了为了提高效率我们可以在存储纸币有多少的时候用整形int来代替也是可以的。
根据身高重建队列406. 根据身高重建队列 - 力扣LeetCode
这道题的排序部分和上一期的分发糖果差不多的思路上一个题只不过不是那么明确但是这道题明确的给出了两个不同属性的值我们要根据两个不同属性的值来对数据进行排序。上一个题是当前分发糖果的孩子可能要同时比较左孩子和右孩子的分数再进行排序调整所以理论上也都是两次排序。
思路是这样的我们先按照身高排序如果先按照前面有几个数的k排序是不对的因为k的值是固定的题的言外之意是我们先确定好身高后排序k看前面有几个数据而不能先排序k这样会造成两个属性都没办法合理排序浪费时间。我们先按照身高进行排序排降序把身高高的排在数组的前面然后再按照第二个属性k将数据插入进去如果两个人身高相等那么k值低的在前面高的在后面。
class Solution {public:static bool cmp(vector<int>a,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>>result; for(int i0;i<people.size();i){ int pospeople[i][1]; result.insert(result.begin()pos,people[i]); } return result; }};我们再进行第一个属性的排序时候先不把数据整个压到数组内部先对其进行排序因为什么不像那道分发糖果一样直接放入数组然后用来调整呢因为我们要返回的这个数组里面包含多个数组我们在进行第一步排列时候就将内容加到返回数组里了在第二次排序调整的时候数据很难再从结果数组里进行排序了因为我们每次排序的是一个数组。正确的做法是第一次按照身高排完序后第二次排序的时候确定了再压入数组中实际上这里的第二次排序是很有讲究的第一次排序的时候我们已经按照数据排了对身高的降序这个时候我们再用一个变量来保存它这个当前值的k值它决定了我们这个数组插入到哪个位置。
我们首先将如果数据一样k值小的排在了前面所以一般来说第一个数据就是插在0这个位置上的以此类推都是根据k值来调整插入的顺序而为什么要先排序大的数据呢因为我们先将身高大的数据插进去了这样我们身高小的数据插入时候会把身高大的数据向后面挤当身高小的数据k值也小的时候身高大的前面有身高小的是没有任何问题的当身高大的前面有0个人时或前面有比他大的身高所以我们才进行这样的排序如果身高小的数据k值也小的话那它自然就插入到后面了这个是很容易理解的。
总的来说思路听巧妙的但是用数组做存储并不方便会增加运行的负担vector的插入函数运行效率不高而且vector底层是数组实现如果要插入数据过大它要开辟一个两倍于当前大小然后将数据拷贝进来再操作如果它总是拷贝会大大影响效率。
我们可以将其改为用链表来操作将数据用链表连接保存然后返回时候再化为数组。
class Solution {public:static bool cmp(vector<int>a,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); list<vector<int>>result; for(int i0;i<people.size();i){ int pospeople[i][1]; list<vector<int>>::iterator itresult.begin(); while(pos--)it; result.insert(it,people[i]); } return vector<vector<int>>(result.begin(),result.end()); }};注意:这里的it并不是多此一举c里的list的insert函数并不是随机迭代访问器不能像操作数组那样加加减减的我们需要调整迭代器的位置之后再进行传入。
452. 用最少数量的箭引爆气球 - 力扣LeetCode
贪心算法中的重叠问题两个气球都有其所在的范围也就是所谓的直径将两个气球放在一个xy的平面上如果两个气球x部分有重叠那么一支箭就可以射爆两个气球题目给出箭从x轴垂直向上射出可以无限距离的走也就是说路径上只要有气球都可以射爆需要注意的一点是如果两个气球的边界是紧挨着的那么一支箭从两气球中间穿过去也就是边界处也是可以将两个气球同时射爆的。
解题思路如何判断两气球是否有重叠部分第二个气球的最左端的坐标如果小于第一个气球的最右端说明存在重叠部分即使等于也可以这就是上面所说的紧挨着的情况但是如果大于了则说明没有重叠部分需要另一只箭值得注意的是如果有两气球重叠判断第三只气球也是否可以一起射爆的时候我们需要判断的有可能不再是第一个气球的末尾处有可能是第二个气球的末尾处由于前两个气球已经重叠可以看作一个整体如果第二个气球过小完全被第一个气球所包含那么我们下一次的判断边界应该是两气球中的较小的那一个下标来缩小其范围如果这时候还用第一个下标那么就可能出现射爆一三气球而射不到第二个气球的情况这一点需要额外注意。
class Solution {public:static bool cmp(vector<int>&a,vector<int>&b){ return a[0]<b[0];} int findMinArrowShots(vector<vector<int>>& points) { if(points.size()0)return 0; int result1; sort(points.begin(),points.end(),cmp); for(int i1;i<points.size();i){ if(points[i][0]>points[i-1][1]) result; else points[i][1]min(points[i-1][1],points[i][1]); } return result; }};代码还算简单但是思路很难在没有做过的时候想出来。
写判断标准的cmp时候一定要传入数组引用不要只单独传入数组因为数组过大的时候直接传入它需要先对数组整个进行复制传入很费时。
为什么要先将数组排序后再做处理呢这是为了方便寻找区间重叠让可能重叠的区间挨在一起。
总结今天我们完成了柠檬水找零、根据身高重建队列、用最少数量的箭引爆气球三道题相关的思想需要多复习回顾。接下来我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。
当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~