专题：贪心算法（已完结）

1.分发饼干

方法一：用最大的胃口 找到最大的饼干（先遍历胃口）

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {// 主要思路 用最大的饼干找最大的胃口sort(g.begin(),g.end());sort(s.begin(),s.end());int j = s.size()-1;int count =0;for(int i=g.size()-1;i>=0;i--){if(j>=0&&g[i]<=s[j]){count++;j--;}}return count;}
};

方法二.用最大的饼干找最大的胃口（先遍历饼干）

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {// 主要思路 用最大的饼干找最大的胃口sort(g.begin(),g.end());sort(s.begin(),s.end());int j =g.size()-1;int count = 0;for(int i =s.size()-1;i>=0;i--){// 遍历饼干while(j>=0&&s[i]<g[j]){//找到合适的胃口j--;}if(j>=0&&s[i]>=g[j]){count++;j--;}}return count;}
};

2.摆动序列

3.最大子序和
思路：之前的和小于0就直接放弃 如果大于0就保持继续累加 比较这能够累加的和的最大值即可

class Solution {
public:int maxSubArray(vector<int>& nums) {// 主要思路是  之前的和小于0就直接放弃 如果大于0就保持继续累加 比较这能够累加的和的最大值即可int sumMax = nums[0];int sum = nums[0];;for(int i=1;i<nums.size();i++){if(sum<0){sum=nums[i];}else{sum=sum+nums[i];}sumMax=max(sumMax,sum);}return sumMax;}
};

4.买卖股票的最佳时机 II
方法一：贪心 主要思路 当天如果与前一天的差值大于0就代表可以这天卖前一天买 累加这种情况即可
方法二：动态规范

方法一：

class Solution {
public:int maxProfit(vector<int>& prices) {// 主要思路 当天如果与前一天的差值大于0就代表可以这天卖前一天买 累加这种情况即可int sum=0;for(int i =1;i<prices.size();i++){if(prices[i]>prices[i-1]){sum=sum+(prices[i]-prices[i-1]);}}return sum;}
};

方法二：

class Solution {
public:int maxProfit(vector<int>& prices) {// 动态规划// 1.定义 dp[i][0] 第i天持有股票的最大利润  dp[i][1] 第i天不持有股票的最大利润// 2.动态转移方程// dp[i][0] = max(dp[i-1][1]-prices[i],dp[i-1][0]);// dp[i][1] = max(dp[i-1][0]+prices[i],dp[i-1][1]);// 3.初始化// dp[0][0] = -prices[0];// dp[0][1]=0;// 4.遍历顺序 从左到右// 返回值 max(dp[prices.size()-1][0],dp[prices.size()-1][1]);vector<vector<int>> dp(prices.size(),vector<int>(2,0));dp[0][0] = -prices[0];dp[0][1]=0;for(int i=1;i<prices.size();i++){dp[i][0] = max(dp[i-1][1]-prices[i],dp[i-1][0]);dp[i][1] = max(dp[i-1][0]+prices[i],dp[i-1][1]);}return max(dp[prices.size()-1][0],dp[prices.size()-1][1]);}
};

5.跳跃游戏
主要思路 就是每次能够跳跃的最远下标位置 如果这个下标位置 刚开始就是无法到达的直接返回false

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

6.跳跃游戏 II
主要思路 这里需要记录每次count发生变化的时候 在nextDis 范围内的最大距离是多少。

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

7.K次取反后最大化的数组和
主要思路：先将绝对值最大的负数去取反 然后如果还剩下剩余取反次数 直接将这些取反次数作用于绝对值最小的正数

class Solution {
public:static bool cmp(int a,int b){return abs(a)>abs(b);};int largestSumAfterKNegations(vector<int>& nums, int k) {// 主要思路是 先将绝对值最大的负数去取反 然后剩余取反次数作用于绝对值最小的正数sort(nums.begin(),nums.end(),cmp);for(int i=0;i< nums.size(); i++){if(nums[i]<0&&k>0){nums[i]=-nums[i];k--;}}if(k%2==1){nums[nums.size()-1]=-nums[nums.size()-1];}int sum=0;for(auto num:nums){sum=sum+num;}return sum;}
};

8.加油站
1.主要思路 首先要明确是否有解 如果总加油量小于总耗油量 无论从哪个站点都不能绕一圈

       if(totalGas<totalCost){return -1;}

2.在有解的情况下面 如果当前 的sum<0 则下一个站点可能就是解

         sum=sum+(gas[i]-cost[i]);if(sum<0){sum = 0;resultIndex = i+1;}

完整代码如下

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int totalGas = 0;for(auto g:gas){totalGas=totalGas+g;}int totalCost = 0;for(auto c:cost){totalCost=totalCost+c;}//    cout<<"totalGas:"<<totalGas<<"   totalCost:"<<totalCost<<endl;if(totalGas<totalCost){return -1;}int resultIndex = 0;int sum = 0;for(int i=0;i<gas.size();i++){sum=sum+(gas[i]-cost[i]);if(sum<0){sum = 0;resultIndex = i+1;}}return resultIndex;}
};

9.分发糖果
主要思路：
1.先从前往后遍历 保证当前高的孩子比前一个孩子糖果多1; preCount
2.再从后往前遍历 保证当前高的孩子比后一个孩子糖果多1; aftercount
3.结合 前preV以及afterV 取最大值即可

class Solution {
public:int candy(vector<int>& ratings) {// 主要思路：// 1.先从前往后遍历 保证当前高的孩子比前一个孩子糖果多1; preCount// 2.再从后往前遍历 保证当前高的孩子比后一个孩子糖果多1; aftercount// 3.结合 前preV以及afterV 取最大值即可//1.前往后遍历vector<int> preCount(ratings.size(),1);for(int i =1;i<ratings.size();i++){if(ratings[i]>ratings[i-1]){preCount[i]=preCount[i-1]+1;}// 默认就是1//   else{//     preCount[i]=1;//   }}//2.从后往前遍历vector<int> aftercount(ratings.size(),1);for(int i =ratings.size()-2;i>=0;i--){if(ratings[i]>ratings[i+1]){aftercount[i]=aftercount[i+1]+1;}// 默认就是1//   else{//     aftercount[i]=1;//   }}//3.结合int count = 0;for(int i=0;i<preCount.size();i++){count=count+max(preCount[i],aftercount[i]);}return count;}
};

10.柠檬水找零

主要思路
客户付款金额 5 美元、10 美元或 20 美元
当客户给5元的时候 不用找 coutFive++;
当客户给10元的时候 找5元 没有5元直接返回false
当客户给20元的时候 优先找一个10元和一个5元 没有的话再找三个5元 还是没有的话 直接false;

```cpp
class Solution {
public:bool lemonadeChange(vector<int>& bills) {//客户付款金额 5 美元、10 美元或 20 美元// 当客户给5元的时候 不用找 coutFive++;// 当客户给10元的时候  找5元 没有5元直接返回false// 当客户给20元的时候  优先找一个10元和一个5元 没有的话再找三个5元 还是没有的话 直接false;int countFive=0,countTem=0,countTwenty=0;for(auto bill: bills){if(bill==5){countFive++;}else if(bill==10){if(countFive==0){return false;}countFive--;countTem++;}else if(bill==20){if(countTem>=1&&countFive>=1){countTem--;countFive--;countTwenty++;}else if(countFive>=3) {countFive=countFive-3;}else{return false;}}}return true;}
};

11.根据身高重建队列
主要思路/：这里有两个维度一个身高h 一个前面大于该元素的个数k 先固定一个元素 例如h 再比较k（插入元素）
先排序

    static bool cmp(vector<int> vec1,vector<int> vec2){// 这里有两个维度一个身高h 一个前面大于该元素的个数k 先固定一个元素 例如h 再比较k（插入元素）if(vec1[0]==vec2[0]){return vec1[1]<vec2[1];}return vec1[0]>vec2[0];}

完整代码

class Solution {static bool cmp(vector<int> vec1,vector<int> vec2){// 这里有两个维度一个身高h 一个前面大于该元素的个数k 先固定一个元素 例如h 再比较k（插入元素）if(vec1[0]==vec2[0]){return vec1[1]<vec2[1];}return vec1[0]>vec2[0];}
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(),people.end(),cmp);vector<vector<int>>  result;for(int i=0;i<people.size();i++){int index = people[i][1];result.insert(result.begin()+index,people[i]);}return result;}
};

12.用最少数量的箭引爆气球
主要思路：先排序 每次比较的是当前元素的左边和上个元素的右边界 发现边界有重复 直接更新当前元素的右边界（在原数据中修改） 没有重复就得增加🗡的个数

          if(points[i][0]<=points[i-1][1]){points[i][1] = min(points[i-1][1],points[i][1]);}else{count++;}

完整代码

class Solution {
public:static bool cmp(vector<int> point1,vector<int> point2){return point1[0]<point2[0];} int findMinArrowShots(vector<vector<int>>& points) {// 先排序 每次比较的是当前元素的左边和上个元素的右边界 发现边界有重复 直接更新当前元素的右边界（在原数据中修改）  没有重复就得增加🗡的个数 sort(points.begin(),points.end(),cmp);int count = 1;for(int i=1;i<points.size();i++){if(points[i][0]<=points[i-1][1]){points[i][1] = min(points[i-1][1],points[i][1]);}else{count++;}}return count;}
};

当然 也可以不直接修改原来的数组数据 直接用一个变量记录右边界即可 下面还直接从数据下表index=0开始遍历了 curRightBoundary 要设置长整数型最小值 因为测试用例中有普通整数型最小值

long int curRightBoundary =LONG_MIN;

class Solution {
public:static bool cmp(vector<int> point1,vector<int> point2){return point1[0]<point2[0];} int findMinArrowShots(vector<vector<int>>& points) {// 先排序 发现边界有重复 更新左边界 没有重复就得增加🗡的个数sort(points.begin(),points.end(),cmp);if(points.size()==1){return 1;}long int curRightBoundary =LONG_MIN;int count = 0;for(int i=0;i<points.size();i++){if(points[i][0]<=curRightBoundary){curRightBoundary = min(curRightBoundary,(long int)points[i][1]);}else{count++;curRightBoundary=points[i][1];}}return count;}
};

13.无重叠区间

class Solution {
public:static bool cmp(vector<int> interval,vector<int> interva2){return interval[0]<interva2[0];} int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end(),cmp);// for(auto point:intervals){//     cout<<point[0]<<"    "<<point[1]<<endl;;// }int count =0;for(int i=1;i<intervals.size();i++){if(intervals[i][0]<intervals[i-1][1]){// 有重叠count++;intervals[i][1]=min(intervals[i][1],intervals[i-1][1]);}else{////    没有重叠 不需要更新边界// count++;}}return count;}
};

14.划分字母区间
主要思路 首先记录s里面每个元素的最远位置 遍历的时候 当如果当前元素到达这个这个元素的最远位置（包含这个元素）的时候 这是一个结果 同时更新左边界

           if(rightBoundary==i) {result.push_back(rightBoundary-leftBoundary+1);leftBoundary = i+1;}

完整代码

class Solution {
public:vector<int> partitionLabels(string s) {//  主要思路 首先记录s里面每个元素的最远位置 遍历的时候 当如果当前元素到达这个这个元素的最远位置（包含这个元素）的时候 这是一个结果 同时更新左边界unordered_map<char,int> mymap;for(int i=0;i< s.size();i++){mymap[s[i]]=i;}int leftBoundary =0;int rightBoundary = 0;vector<int> result{};for(int i=0;i< s.size();i++){rightBoundary=max(rightBoundary,mymap[s[i]]);if(rightBoundary==i) {result.push_back(rightBoundary-leftBoundary+1);leftBoundary = i+1;}}return result;}
};

15.合并区间
主要思路：先按照左边界进行排序 从小到大 遍历intervals 如果当前元素和上个元素存在重叠区间 进行合并 否则直接push

class Solution {static bool cmp(vector<int> interval1,vector<int> interval2){return interval1[0]<interval2[0];}
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {// 先按照左边界进行排序 从小到大 遍历intervals 如果当前元素和上个元素存在重叠区间 进行合并 否则直接pushsort(intervals.begin(),intervals.end(),cmp);vector<vector<int>> result{};for(int i=0;i<intervals.size();i++){if(!result.empty()&&intervals[i][0]<=result.back()[1]){result.back()[1]=max(result.back()[1], intervals[i][1]);}else{result.push_back(intervals[i]);}}return result;}
};

16.单调递增的数字
主要思路 从后往前进行遍历 如果当前元素 大于后一个元素 则记录下个元素的位置（这个位置需要变成9） 并且当前元素的值-1（可以直接用to_string进行遍历 以及stoi进行结果输出）

class Solution {
public:int monotoneIncreasingDigits(int n) {// 主要思路 从后往前进行遍历 如果当前元素 大于后一个元素 则记录下个元素的位置（这个位置需要变成9） 并且当前元素的值-1（可以直接用to_string进行遍历 以及stoi进行结果输出）string s = to_string(n);int index=s.size();for(int i=s.size()-2;i>=0;i--){if(s[i]>s[i+1]){index = i+1;s[i]=s[i]-1;}}// cout<<"index:"<<index<<endl;for(int i=index;i<s.size();i++){s[i] = '9';}return stoi(s);}
};

17.监控二叉树
在二叉树章节进行查阅