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