首页 > 编程语言 >代码随想录算法训练营第36期DAY37

代码随想录算法训练营第36期DAY37

时间:2024-05-25 16:01:40浏览次数:22  
标签:return int DAY37 随想录 36 vector res end points

DAY37

先二刷昨天的3道题目,每种方法都写:是否已完成:是。

报告:134加油站的朴素法没写对。原因是:在if中缺少了store>=0的判断,只给出了index==i的判断。前进法没写出来。因为忘记了总油量的判断。Sum。注意变量的初始化。分配糖果注意if里面放的是ratings;

860柠檬水找零

网上摘得思路,看来我还是得冷静下来多想多模拟,最好把文字思路写下来,慢慢打磨:

思路:

  1. 遇10元要消耗5元数量,遇到20元可消耗10元和5元数量,由于要保证后面还可能需要5元
    2. 那么,遇到20元时就要优先消耗10元的数量

  1. class Solution {
  2. public:
  3.     bool lemonadeChange(vector<int>& bills) {
  4.         int five=0,ten=0,twenty=0;
  5.         for(int bill:bills){
  6.             if(bill==5) five++;
  7.             else if(bill==10){
  8.                 if(five==0) return false;
  9.                 five--,ten++;
  10.             }
  11.             else if(bill=20){
  12.                 if(ten>0&&five>0){
  13.                     ten--,five--,twenty++;
  14.                 }
  15.                 else if(five>=3){
  16.                     five-=3,twenty++;
  17.                 }
  18.                 else 
  19.                     return false;
  20.             }
  21.         }
  22.         return true;
  23.     }
  24. };

406根据身高重建队列

想不出来,不知道该怎么模拟。

力扣博主Sunny的题解:

渔(套路):一般这种数对,还涉及排序的,根据第一个元素正向排序,根据第二个元素反向排序,或者根据第一个元素反向排序,根据第二个元素正向排序,往往能够简化解题过程。

在本题目中,我首先对数对进行排序,按照数对的元素 1 降序排序,按照数对的元素 2 升序排序。原因是,按照元素 1 进行降序排序,对于每个元素,在其之前的元素的个数,就是大于等于他的元素的数量,而按照第二个元素正向排序,我们希望 k 大的尽量在后面,减少插入操作的次数。

作者:Sunny

链接:https://leetcode.cn/problems/queue-reconstruction-by-height/solutions/486493/xian-pai-xu-zai-cha-dui-dong-hua-yan-shi-suan-fa-g/

来源:力扣(LeetCode)

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

讲得非常好,我们自己编程实现一下:

不会语法。

很好,学到新东西了,尤其是重载pair类运算符,还有insert记得传入res.begin()的写法:

  1. class Solution {
  2. public:
  3.     //注意person是vector<int> 不是pair.因为是对内部的元素排,而内部元素是vector<int>类型
  4.     static bool mycmp(vector<int>&a,vector<int>&b){
  5.         if(a[0]==b[0]) return a[1]<b[1];
  6.         return a[0]>b[0];
  7.     }
  8.     vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
  9.         vector<vector<int>> res;
  10.         sort(people.begin(),people.end(),mycmp);
  11.         for(auto person:people){
  12.             int size=(int)res.size();
  13.             if(person[1]>=size)
  14.                 res.push_back(person);
  15.             else 
  16.                res.insert(res.begin()+person[1],person); 
  17.             
  18.         }
  19.         return res;
  20.     }
  21. };

学习代码随想录的解法:

引用:

“本题有两个维度,h和k,看到这种题目一定要想如何确定一个维度,然后再按照另一个维度重新排列。在135. 分发糖果 (opens new window)我就强调过一次,遇到两个维度权衡的时候,一定要先确定一个维度,再确定另一个维度。”

思路一样的,但是讲解的话,力扣博主要更清晰易懂,以后优先看力扣博主的讲解,都吸收。

这里相当于再写一遍:

  1. class Solution {
  2. public:
  3.     static bool mycmp(vector<int>&a,vector<int>&b){
  4.         if(a[0]==b[0]) return a[1]<b[1];
  5.         return a[0]>b[0];
  6.     }
  7.     vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
  8.         vector<vector<int>> res;
  9.         sort(people.begin(),people.end(),mycmp);
  10.         for(auto person :people){
  11.             int size=(int)(res.size());
  12.             if(person[1]>=size) res.push_back(person);
  13.             else res.insert(res.begin()+person[1],person);
  14.         }
  15.         return res;
  16.     }
  17. };

还需要额外学习手写vector的insert操作:

  1. void insert(vector<int>& vec, int pos, int val) {
  2.     // Check if the position is valid
  3.     if (pos < 0 || pos > vec.size()) {
  4.         throw invalid_argument("Position is out of range.");
  5.     }
  6.     // Increase the size of the vector
  7.     vec.resize(vec.size() + 1);
  8.     // Move the elements after the position to create space for the new element
  9.     for (int i = vec.size() - 1; i > pos; i--) {
  10.         vec[i] = vec[i - 1];
  11.     }
  12.     // Insert the new element
  13.     vec[pos] = val;
  14. }

452用最少数量的箭引爆气球

本题考察区间合并,在ACWING学了模版,但是已经记不起来了,还是得多学多做多复习(显然不太可能,尽力吧):

还是写不出来区间合并。仔细读题,这题并不是单纯的区间合并

复习ACWING区间合并,学习记忆ACWING模版,力扣高赞题解,代码随想录题解、COZE的解法(主要还是要学会区间合并,COZE的解法并不能走天下)。已完成。

COZE:

注意先sort再去取end;

  1. class Solution {
  2. public:
  3.     static bool mycmp(vector<int>&a,vector<int>&b){
  4.         return a[1]<b[1];
  5.     }
  6.     int findMinArrowShots(vector<vector<int>>& points) {
  7.         sort(points.begin(),points.end(),mycmp);
  8.         int res=1,end=points[0][1];
  9.         for(int i=1;i<points.size();i++){
  10.             if(points[i][0]<=end) continue;
  11.             res++;
  12.             end=points[i][1];
  13.         }
  14.         return res;
  15.     }
  16. };

Leetcode优质题解:

思路和上面一样:有交集就好,没交集就res++,并更新end;

代码随想录官方题解:

学到了:如果按左端点来排序,那么应当从后向前开始遍历。遇到重叠时候:重叠气球的最小右边界就是射箭地方。

  1. class Solution {
  2. public:
  3.     static bool mycmp(vector<int>&a,vector<int>&b){
  4.         return a[0]<b[0];
  5.     }
  6.     int findMinArrowShots(vector<vector<int>>& points) {
  7.         int result=1;
  8.         sort(points.begin(),points.end(),mycmp);
  9.         for(int i=1;i<points.size();i++){
  10.             //不重叠
  11.             if(points[i][0]>points[i-1][1]){
  12.                 result++;
  13.             }
  14.             //重叠
  15.             else{
  16.                 points[i][1]=min(points[i][1],points[i-1][1]);
  17.             }
  18.         }
  19.         return result;
  20.     }
  21. };

ACWING803区间合并

有很多细节:-2e9,注意负号的位置。

  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. using namespace std;
  5. const int N=100010;
  6. typedef pair<int,int> PII;
  7. vector<PII> segs;
  8. //看一下const N怎么用的?
  9. void mymerge(vector<PII>&segs){
  10.     sort(segs.begin(),segs.end());
  11.     vector<PII> res;
  12.     int st=-2e9,ed=-2e9;
  13.     for(auto seg:segs){
  14.         //无交集
  15.         if(ed<seg.first){
  16.             if(st!=-2e9) res.push_back({st,ed});
  17.             st=seg.first,ed=seg.second;
  18.         }
  19.         //有交集
  20.         else{
  21.             ed=max(seg.second,ed);
  22.         }
  23.     }
  24.     //防止空区间进入
  25.     if(st!=-2e9) res.push_back({st,ed});
  26.     segs=res;
  27. }
  28. int main(){
  29.     int n;
  30.     scanf("%d",&n);
  31.     while(n--){
  32.         int l,r;
  33.         scanf("%d%d",&l,&r);
  34.         segs.push_back({l,r});
  35.     }
  36.     mymerge(segs);
  37.     printf("%d\n",segs.size());
  38.     return 0;
  39. }

学习贪心算法:

来源:

[一个视频搞懂贪心算法]

(https://www.bilibili.com/video/BV1Hz4y117CP/?share_source=copy_web&vd_source=20ecc36fbdd0ac45969ae149b0333409)

  1. 分配问题。

分配饼干,因为饥饿度最小的孩子最容易吃饱,先考虑他。

做过了。

  1. 区间问题-Leetcode435 无重叠区间

在选择要保留区间时,区间的结尾十分重要:选择的区间结尾越小,余留给其它区间的空间就越大,就越能保留更多的区间。

因此,我们采取的贪心策略为,优先保留结尾小且不相交的区 间。具体实现方法为,先把区间按照结尾的大小进行增序排序,每次选择结尾最小且和前一个选 择的区间不重叠的区间。

给定多个区间,计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。

  1. class Solution {
  2. public:
  3.     static bool mycmp(vector<int>&a,vector<int>&b){
  4.         return a[1]<b[1];
  5.     }
  6.     int eraseOverlapIntervals(vector<vector<int>>& intervals) {
  7.         int remove=0;
  8.         sort(intervals.begin(),intervals.end(),mycmp);
  9.         int end=intervals[0][1];
  10.         for(int i=1;i<intervals.size();i++){
  11.             if(intervals[i][0]<end) {
  12.                 remove++;
  13.                 continue;
  14.             }
  15.             end=intervals[i][1];
  16.         }
  17.         return remove;
  18.     }
  19. };

做出来了!不会也别怕,做过类似的就增长能力了,下次就能举一反三。

  1. 买卖股票的最佳时机 Leetcode121,简单

又不会了,因为当时没彻底弄懂吧。

朴素法,超时了:

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         int res=INT_MIN;
  5.         for(int i=0;i<prices.size()-1;i++){
  6.          int j=i+1;
  7.          while(j<prices.size()){
  8.             int tmp=prices[j]-prices[i];
  9.             if(tmp>res) res=tmp;
  10.             j++;
  11.          }
  12.         }
  13.         if(res<0) return 0;
  14.         return res;
  15.     }
  16. };

动态规划:画图!

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         int pastprice=INT_MAX,res=0;
  5.         for(int price:prices){
  6.             res=max(res,price-pastprice);
  7.             pastprice=min(price,pastprice);
  8.         }
  9.         return res;
  10.     }
  11. };

  1. 买卖股票的最佳时机ii,中等

画图发现,[1,4,6]不管是{1买入,4卖出;4买入,6卖出}还是{1买入,6卖出}结果一样,所以每日res>0的话就加入到结果中:如果今天买明天卖能赚钱,那么就今天买入。

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         if(prices.size()==1) return 0;
  5.         int pro=0;
  6.         for(int i=1;i<prices.size();i++){
  7.             int res=prices[i]-prices[i-1];
  8.             if(res>0) pro+=res;
  9.         }
  10.         return pro;
  11.     }
  12. };

标签:return,int,DAY37,随想录,36,vector,res,end,points
From: https://blog.csdn.net/illuosion7/article/details/139160480

相关文章

  • 代码随想录——二叉树的所有路径(Leetcode257)需要回顾
    题目链接BFS+队列维护一个队列,存储节点以及根到该节点的路径。一开始这个队列里只有根节点。在每一步迭代中,我们取出队列中的首节点,如果它是叶子节点,则将它对应的路径加入到答案中。如果它不是叶子节点,则将它的所有孩子节点加入到队列的末尾。当队列为空时广度优先搜......
  • 代码随想录算法训练营第一天 | 977.有序数组的平方;
    代码随想录算法训练营第一天|977.有序数组的平方;977题链接:https://leetcode.cn/problems/squares-of-a-sorted-array/代码随想录链接:https://programmercarl.com/0977.有序数组的平方.html#思路209题链接:https://leetcode.cn/problems/minimum-size-subarray-sum/submission......
  • 代码随想录算法训练营第第17天 | 110.平衡二叉树、257. 二叉树的所有路径、404.左叶子
    三道题都没想出来,还是要加强递归的练习110.平衡二叉树(优先掌握递归)再一次涉及到,什么是高度,什么是深度,可以巩固一下。题目链接/文章讲解/视频讲解:https://programmercarl.com/0110.平衡二叉树.htmlfunctiongetHeight(node){if(node===null)return0;letleftH......
  • 新定义RD8T36P48使用USCI0的TWI功能点亮OLED
    时间不多,因此先只给出工程,等有时间再添加详细说明现象这是从之前的一个51单片机的程序移植过来的,主要修改了IIC启动和停止,以及数据发送的代码,我现在还不是很满意的一点是发送过程中要等待上一个字节发送完才能接着发送本次字节。我使用的是while循环等待发送完成标志位,......
  • 新定义RD8T36P48点亮LED--汇编
    其实汇编和C语言差不多,简单的东西用汇编挺好,中等及以上复杂度的程序还是C语言更灵活直接在keil新建好工程,选好芯片型号和下载方式,再创建一个.asm文件并添加到工程,工程创建完如图工程配置代码 ORG0000H LJMPMAIN ORG0100HMAIN: MOVA,9AH ORLA,#20H;让P05为......
  • 算法随想录打卡第三天|链表
    //203移除链表元素publicListNoderemoveElements(ListNodehead,intval){//创建虚拟头指针不对//ListNoderes=head;//创建一个虚拟头结点ListNoderes=newListNode(val-1);res.next=head;ListNodeprev=res;......
  • 代码随想录算法训练营第一天 | 704.二分查找;27. 移除元素
    代码随想录算法训练营第一天|704.二分查找(红蓝模板法);27.移除元素(双指针法)704题链接:https://leetcode.cn/problems/binary-search/description/二分查找:https://programmercarl.com/0704.二分查找.html#其他语言版本二分查找红蓝法笔记:二分查找为什么总是写错?_哔哩哔哩_bil......
  • 代码随想录算法训练营第十五天 | 层序遍历 、226.翻转二叉树、101.对称二叉树
    层序遍历题目链接:学会二叉树的层序遍历,可以一口气打完以下十题:102.二叉树的层序遍历107.二叉树的层次遍历II199.二叉树的右视图637.二叉树的层平均值429.N叉树的层序遍历515.在每个树行中找最大值116.填充每个节点的下一个右侧节点指针117.填充每个节点的下一个右侧节点......
  • 代码随想录算法训练营第三十六天|860.柠檬水找零、406.根据身高重建队列、452. 用最少
    860.柠檬水找零文档讲解:代码随想录题目链接:.-力扣(LeetCode)注意看提示:bills[i] 不是 5 就是 10 或是 20 场景较为固定遇到了20,优先消耗10classSolution:deflemonadeChange(self,bills:List[int])->bool:total={5:0,10:0,20:0}......
  • MySQL大师课:36秘技解锁数据库性能与管理新高度?
     ......