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

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.     }
7.     // Increase the size of the vector
8.     vec.resize(vec.size() + 1);
10.     // Move the elements after the position to create space for the new element
11.     for (int i = vec.size() - 1; i > pos; i--) {
12.         vec[i] = vec[i - 1];
13.     }
15.     // Insert the new element
16.     vec[pos] = val;
17. }

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. }
29. int main(){
30.     int n;
31.     scanf("%d",&n);
32.     while(n--){
33.         int l,r;
34.         scanf("%d%d",&l,&r);
35.         segs.push_back({l,r});
36.     }
37.     mymerge(segs);
38.     printf("%d\n",segs.size());
39.     return 0;
40. }

学习贪心算法：

来源：

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

(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. };