4.17--4.19刷題記錄（貪心）

第一部分：準備工作

代碼隨想錄中解釋為：貪心的本質是選擇每一階段的局部最優，從而達到全局最優。

而我的理解為：貪心實質上是具有最優子結構的一種算法。所有的解都能由當前最優的解組成。

第二部分：開始刷題

（1）455. 分發餅干 - 力扣（LeetCode）

代碼思路：首先對g和s進行排序，用count記錄胃口值，從前往后遍歷餅干大小，如果餅干能夠滿足胃口，則胃口++；這時候需要注意訪問超出的問題，故要加一個break判斷。

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int count=0;for(int i=0;i<s.size();i++){//遍歷每一個餅干，如果正好大于胃口，則直接賦值if(count==g.size()){break;}if(s[i]>=g[count]){count++;}}return count;}
};

（2）376. 擺動序列 - 力扣（LeetCode）

此題目有以下幾個難點：

首先要記錄差值，那么最初始化的時候ans=1
差值如何比較第一個和最后一個，這時候使用的是初始值0，和0進行比較
if邏輯：如果有平數據的話怎么處理：if判斷條件中一邊=0，另一邊不等于0
更新pre和cur，每一次進行翻轉的時候才進行保存

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {//首先計算兩個的差值，并且與前一個比較int pre=0,cur=0;int ans=1;for(int i=1;i<nums.size();i++){cur=nums[i]-nums[i-1];if(pre>=0&&cur<0||pre<=0&&cur>0){ans++;pre=cur;}}return ans;}
};

（3）53. 最大子數組和 - 力扣（LeetCode）

貪心思路：

如果count累加器比當前ans大，那么就更新。
如果為正數，那么就累加（因為后面進行累加的話可以理解為在0的基礎上進行累加，正數肯定比0大）
如果為負數，那么轉換為0，后面在0的基礎上加。

class Solution {
public:int maxSubArray(vector<int>& nums) {int count=0,ans=nums[0];for(int i=0;i<nums.size();i++){count+=nums[i];if(count>ans){ans=count;}if(count<0){count=0;}}return ans;}
};

（4）122. 買賣股票的最佳時機 II - 力扣（LeetCode）

貪心思路：

注意題目為可以同一天進行操作，也就是說可以同一天買賣
如果后一天比前一天利潤大，那么賣掉。因為如果后面有更大的，呢么可以買當前的后一個到時候再賣掉。其原理等于買現在賣后面更大的。

class Solution {
public:int maxProfit(vector<int>& prices) {int profit=0;for(int i=0;i<prices.size()-1;i++){int sub=prices[i+1]-prices[i];if(sub>0){profit+=sub;}}return profit;}
};

（5）55. 跳躍游戲 - 力扣（LeetCode）

貪心思路：

不斷更新自己能去的最大值，如果能夠到達隊尾，那么就返回true
初始值的設定，far一開始為0，表示自己的第一步
far>=n-1，表示到達末尾元素

class Solution {
public:bool canJump(vector<int>& nums) {int far=0;int n=nums.size();for(int i=0;i<=far;i++){far=max(far,nums[i]+i);if(far>=n-1)return true;}return false;}
};

（6）45. 跳躍游戲 II - 力扣（LeetCode）

貪心思路：

確定一個區間和一個值，區間表示這個范圍內可以到達的地方，值表示這個范圍內的下一步能夠到達的地方。

class Solution {
public:int jump(vector<int>& nums) {if(nums.size()==1)return 0;int count=0;int n=nums.size();int nextfar=0,curfar=0;for(int i=0;i<=curfar;i++){nextfar=max(nextfar,nums[i]+i);if(i==curfar){count++;curfar=nextfar;}if(curfar>=n-1)return count;}return 1;}
};

（7）1005. K 次取反后最大化的數組和 - 力扣（LeetCode）

貪心：將絕對值最大的進行翻轉。

方法一：一次排序

class Solution {
static bool cmp(int a,int b){return abs(a)>abs(b);
}
public:int largestSumAfterKNegations(vector<int>& A, int K) {sort(A.begin(), A.end(), cmp);       // 第一步for (int i = 0; i < A.size(); i++) { // 第二步if (A[i] < 0 && K > 0) {A[i] *= -1;K--;}}if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步int result = 0;for (int a : A) result += a;        // 第四步return result;}
};

方法二：兩次排序

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(),nums.end());int i;int result=0;for(i=0;i<nums.size()&&k>0;i++){if(nums[i]<0){nums[i]=-nums[i];k--;}}sort(nums.begin(),nums.end());if(k%2==1){nums[0]=0-nums[0];}for(int i:nums){result+=i;}return result;}
};

（8）134. 加油站 - 力扣（LeetCode）

貪心思路：

cur_rest表示當前的剩余量，如果累加和小于零就說明從舊的start無法到達當前的i。那么新的start就要從i+1開始
total_rest表示總和，如果他小于零則表示不管從哪兒開始都無法到達終點。
所以本題用貪心的思路就是選擇能夠滿足當前cur_rest的start，如果最后total大于等于零，那么就表示可達。（我的理解就是假如最后total=0，那么一定有一個分界點，使得后半部分的和能夠填滿前半部分的負數。那么就是這個start。如果總和為正數，那么就更好了。

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int start=0;int cur_rest=0,total_rest=0;for(int i=0;i<cost.size();i++){cur_rest+=gas[i]-cost[i];total_rest+=gas[i]-cost[i];if(cur_rest<0){cur_rest=0;start=i+1;}}if(total_rest<0)return -1;return start;}
};

（9）135. 分發糖果 - 力扣（LeetCode）

貪心策略：

一次是從左到右遍歷，只比較右邊孩子評分比左邊大的情況。
一次是從右到左遍歷，只比較左邊孩子評分比右邊大的情況。

class Solution {
public:int candy(vector<int>& ratings) {int n=ratings.size();vector<int>candies(n,1);int count=0;for(int i=0;i<n-1;i++){if(ratings[i]<ratings[i+1]){candies[i+1]=candies[i]+1;}}for(int i=n-1;i>0;i--){if(ratings[i]<ratings[i-1]){candies[i-1]=max(candies[i]+1,candies[i-1]);}}for(int i=0;i<n;i++){count+=candies[i];}return count;}
};

（10）860. 檸檬水找零 - 力扣（LeetCode）

貪心思路：此題比較簡單，要分三種情況進行討論

五塊的：直接++
十塊的：十塊++，五塊--
二十塊的：優先十塊--+五塊--或者五塊直接減三

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

（11）406. 根據身高重建隊列 - 力扣（LeetCode）

貪心思路：

首先明確有兩個維度，分別是身高以及位置。如果保證位置有序的話，沒有辦法同時保證身高的有序性。那么就只能確定身高這一個維度，從而進一步確定位置
貪心的思路就是保證當前序列的有序性，那么如何保證呢？就不斷取當前元素進行插入。

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) {sort(people.begin(),people.end(),cmp);vector<vector<int>>queue;for(int i=0;i<people.size();i++){int position=people[i][1];queue.insert(queue.begin()+position,people[i]);}return queue;}
};

（12）452. 用最少數量的箭引爆氣球 - 力扣（LeetCode）

貪心思路：

首先進行排序，按照每一個氣球的直徑的最遠距離進行從小到大的排序。
貪心策略為：使用最少的針扎掉盡可能多的氣球

class Solution {
public:static bool cmp(vector<int>&a,vector<int>&b){return a[1]<b[1];}int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(),points.end(),cmp);int arrow=1;int end=points[0][1];for(int i=1;i<points.size();i++){if(points[i][0]<=end){continue;}else{arrow+=1;end=points[i][1];}}return arrow;}
};

（13）435. 無重疊區間 - 力扣（LeetCode）

貪心思路：和上題思路一樣，秒掉

class Solution {
public:static bool cmp(vector<int>&a,vector<int>&b){return a[1]<b[1];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end(),cmp);int ans=1;int end=intervals[0][1];for(int i=1;i<intervals.size();i++){if(intervals[i][0]<end){continue;}else{ans+=1;end=intervals[i][1];}}return intervals.size()-ans;}
};

（14）763. 劃分字母區間 - 力扣（LeetCode）

貪心思路：給不同的字符設置最晚出現位置，在這個區間內不不斷進行擴展，如果i到達了最遠位置并沒有繼續向前擴展，則說明這是一個區間間隔。

class Solution {
public:vector<int> partitionLabels(string s) {vector<int>ans;unordered_map<char,int>cnt;for(int i=0;i<s.size();i++){cnt[s[i]]=i;}int left=0,right=0;for(int i=0;i<s.size();i++){right=max(right,cnt[s[i]]);if(i==right){ans.push_back(right-left+1);left=right+1;}}return ans;}
};

（15）56. 合并區間 - 力扣（LeetCode）

貪心思路：整體來講思路沒有問題，只是處理最后一個vector的時候存在一些問題。以及最后ans.push_back({start,end});使用的是方括號，因為這是數組初始化的一個方式。

class Solution {
public:static bool cmp(vector<int>&a,vector<int>&b){return a[0]<b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>>ans;sort(intervals.begin(),intervals.end(),cmp);int start=intervals[0][0],end=intervals[0][1];for(int i=1;i<intervals.size();i++){if(intervals[i][0]<=end){end=max(end,intervals[i][1]);}else{ans.push_back({start,end});start=intervals[i][0];end=intervals[i][1];}}ans.push_back({start,end});return ans;}
};

（16）738. 單調遞增的數字 - 力扣（LeetCode）

貪心思路：從后往前遍歷，flag記錄從當前位置開始到結尾一直為0的數字

class Solution {
public:int monotoneIncreasingDigits(int n) {string num=to_string(n);int flag=num.size();for(int i=num.size()-1;i>0;i--){if(num[i]<num[i-1]){flag=i;//不是flag--num[i-1]--;}}for (int i = flag; i < num.size(); i++) {num[i] = '9';}return stoi(num);}
};

（17）968. 監控二叉樹 - 力扣（LeetCode）

貪心思路：

節點一共有三種性質：第一種性質：未覆蓋0；第二種性質：已覆蓋2；第三種性質：裝攝像頭1
情況一共分為九種，00->1,01->1,02->1,10->1,11->2,12->2,20->1,21->2,22->0
進行分類可得：
第一類（根節點返回0）：22->0，只有一種情況，當左右兩個節點都已經被當前節點的下層所監控到，根節點表示未被監控到
第二類（根節點裝攝像頭，返回1）：00->1,01->1,02->1,10->1,20->1，有五種情況，只要左子樹或右子樹里面有一個0，未被覆蓋到就可以
第三類（根節點被監控到，返回2）：11->2,12->2,21->2，有三種情況，只要左子樹或者右子樹有一個1，并且都沒有零即可

class Solution {
public:int ans=0;int dfs(TreeNode *root){if(root==nullptr)return 2;int left=dfs(root->left);int right=dfs(root->right);if(left==0||right==0){ans++;return 1;}else if(left==1||right==1){return 2;}else if(left==2&&right==2){return 0;}//其實根本不會遍歷到以下這個東西，所有情況都已經被包含在if中return 2;}int minCameraCover(TreeNode* root) {if(dfs(root)==0)ans++;return ans;}
};