【代码随想录】贪心

455. 分发饼干

题目
随想录
本质：
对于每个孩子，使用可以满足该孩子的最小的饼干。所以对孩子胃口和饼干进行sort排序，依次将大的饼干满足给孩子。
贪心策略：
想一下局部最优，想一下全局最优，如果局部最优可以推出全局最优，就可以考虑贪心。

• 局部最优：对每个孩子使用满足该孩子胃口的最小的饼干
• 全局最优：尽可能满足更多的孩子

技巧：
这里没有使用两个for循环，而是采用了index自减的方式。

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int index=s.size()-1;int result=0;for(int j=g.size()-1;j>=0;j--){if(index>=0&&s[index]>=g[j])//这里index必须>=0{index--;result++;}}return result;}
};

也可以小饼干先喂饱小胃口
错误的：
从小到大喂的话，是根据饼干来的，如果按照孩子来for循环，则同时孩子胃口在增大，饼干也在增大，eg:
[10,9,8,7]
[5,6,7,8]
正确输出是2，但是这里输出了0；因为不是找到第一个饼干，该饼干可以满足最小的孩子胃口。所以从小到大喂应该for循环遍历饼干。而从大到小喂饱，就应该遍历孩子，找到第一个孩子可以满足饼干大小的，然后依次往后遍历。

//错误的
class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int index=0;int result=0;for(int j=0;j<g.size();j++){if(index<s.size()&&s[index]>=g[j]){index++;result++;}}   return result;}
};

正确的从小到大喂：
不用设置result,最后的index就是孩子的数量

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int index=0;for(int j=0;j<s.size();j++){if(index<g.size()&&s[j]>=g[index]){index++;}}   return index;}
};

376. 摆动序列

题目
随想录：
方法一：贪心
用图形的思路：即波峰

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if(nums.size()<=1) return nums.size();int curdif=0;int predif=0;int result=1;for(int i=0;i<nums.size()-1;i++){curdif=nums[i+1]-nums[i];if((curdif>0&&predif<=0)||(curdif<0&&predif>=0)){result++;predif=curdif;}     }return result;        }
};

方法二：动态规划 待学。。。

53. 最大子数组和

题目
方法一：贪心
本题关键是：贪心贪在哪？（局部最优）当前面序列累加为负数时就直接清空sum，从头开始累加，这里就是体现了贪。
全局最优：选取最大的连续和
对比暴力法：利用连续何是否为负数不断调整开始的位置，每次记录最大和调整结束的位置。
我看的随想录思路写的：

class Solution {
public:int maxSubArray(vector<int>& nums) {int max=INT_MIN;int sum=0;int j;for(j=0;j<nums.size();j++){	if(nums[j]>=0)break;else {if(nums[j]>max)max=nums[j];}}if(j<nums.size())max=nums[j];for(int i=j;i<nums.size();i++){sum+=nums[i];if(sum>0){	if(sum>max)max=sum;}else sum=0; //因为这里用的是else 所以当样例全为负数时，就不可行了。对比随想录，随想录是这里用了两个if，而不是当sum为正数时才赋值给max,所以包含了负数，我写的这种没有包含负数，所以在上面判断了全部都是负数的情况，也就是从第一个不为负数的值开始计数}return max;}
};

随想录：

class Solution {
public:int maxSubArray(vector<int>& nums) {int max=INT_MIN;int sum=0;for(int i=0;i<nums.size();i++){sum+=nums[i];//这里的逻辑要细品！！为何不用else 因为时两种不同的情况，并且不是互斥的所以不用elseif(sum>max)max=sum;if(sum<=0) sum=0;}return max;}
};

方法二：暴力法

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN;int count = 0;for (int i = 0; i < nums.size(); i++) { // 设置起始位置count = 0;for (int j = i; j < nums.size(); j++) { // 每次从起始位置i开始遍历寻找最大值count += nums[j];result = count > result ? count : result;}}return result;}
};

方法三：动态规划

122. 买卖股票的最佳时机 II

题目
方法一：贪心

误区：

• 想的是差值最大，差值对应的元素是不同的；错误原因：这里不是不能重复，而是买入卖出，所以是可以重复的当天买，当天卖也是可以的。
  注意：只有一只股票，只不过这只股票是在不断变化的；
  分解的思维：将整体的利润分解为每天的利润。eg:将0~3天的利润prices[3]-prices[0]转化为(prices[3]-prices[2])+(prices[2]-prices[1])+(prices[1]-prices[0]),

随想录拾取正区间的值，就是很巧妙的将整体的最优解转化成了找局部的最优解，如何转化呢，就是根据【分解的思维】，并且这种不是说跳着找到下一个比当前值大的，因为这种是聚焦到一天，即计算出当前天和之后哪一天卖出利润最大，相当于是每次在这n天中找了两天，而正确的思路是同时计算利用局部最优推出全局最优，局部最优就是相邻两天的最大，而全局最优就是将所有相邻中的正数都拾取。
官方题解思路:
由于股票的购买没有限制，因此整个问题等价于寻找 x个不相交的区间 (l_i,r_i] 使得如下的等式最大化.这也是我思路不清晰的原因。
评论区的思路：
把所有的上坡都用sum累加收集。

贪心算法偏向的是题解的算法而不是数据结构算法
看了随想录思路写的：

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

随想录：只需要一次for循环

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

方法二：动态规划

55. 跳跃游戏

题目
要看官方题解去理解。。。。
max(i+nums[i],cover)使用的是i+nums[i]而不是用从0累加，这里也很巧妙
当i>cover就说明跳不到了，所以在for循环里写的是i<=cover
这里有一点很关键：就是为什么要更新最大范围，即通过最大范围来判断是否会跳到最后一格？
因为本题不是纠结如何跳，而是关注能不能跳到。如3 1 2 2 1 1从0开始跳，跳到其最大范围3，如果3<=3，说明是可以跳到3这个位置的，然后在这个基础上，继续往后跳，（注意”这个基础上“，因为每跳到一个地方就说明一定可以，然后再更新最大的覆盖范围，这样一直往前，直到最大范围超过了最后一个下标）
根据官方题解：如何判断位置x可不可以到达y，只要x+nums[x]>=y则说明可以到达，推广到每一个x，即对于每一个可以到达的位置x
说明x都满足了其上一个的nums[x0]+x0,这里的上一个就是任意一个可以到达位置x0，
所以对于每一个可以到达的x，它使得x+1,x+2，…，x+nums[i]都可以到达
反思：
我自己一直纠结怎么走，而不是判断是否走到，没有搞清楚最大步数与贪心之间的关系
随想录：

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

官方题解：

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

45. 跳跃游戏 II

题目

在该下标可以跳跃的最大长度
困惑的点：贪心贪在哪？每次是跳最大的还是最小的，但是又有很多种组合。

如果是最大的一直跳，跳到最后停止的地方的下标大于等于最后一个下标就说明可以，如果不行，则倒着减一个，再继续跳，直到第一个起始位置只跳一步

以最小的步数增加覆盖范围，覆盖范围一旦大于了nums.size()则就说明是最大的

懂了懂了！！！就是从i_{i+nums[i]之间的所有位置i都能到达，只不过i可以走一步，走两步…最大可以走i+nums[i]步，所以就在i}i+nums[i]中找到最大的数，也就是下一次的跳跃起点。
例如，对于数组 [2,3,1,2,4,2,3]，初始位置是下标 0，从下标 0 出发，最远可到达下标 2。下标 0 可到达的位置中，下标 1 的值是 3，从下标 1 出发可以达到更远的位置，因此第一步到达下标 1。

从下标 1 出发，最远可到达下标 4。下标 1 可到达的位置中，下标 4 的值是 4 ，从下标 4 出发可以达到更远的位置，因此第二步到达下标 4。

因此可以用maxPox记录下一个最远可达的下标位置，然后step++

贪心贪在哪？每跳一次下一次的增加都是最大的，即保证了step++一次，跳的最远。
这里每跳一步尽可能的多走体现了贪心思想
不管怎么跳i~i+nums[i]之间的位置是都能跳到的，以最小的步数增加覆盖范围，当移动下标走到了最大覆盖范围的边界时就step++

我的错误点：将最大步数nums[i]和maxPos没有搞清楚，实际上是一个东西
错误:

//错误
class Solution {
public:int jump(vector<int>& nums) {int maxPos=0;int maxStep=0;int step=0;for(int i=0;i<nums.size();){maxStep=0;for(int j=i;j<i+nums[i]&&j<nums.size();j++){//    maxStep=max(maxStep,nums[j]);if(maxStep<=nums[j]){maxPos=j;maxStep=nums[j];}}           step++;i=maxPos;}return step;}
};

看的这个大神的解析：解析
这里是用start和end来控制区间的
可以看出for循环实际上是从头到尾遍历了一遍nums，所以可以合成一个遍历
这里的区间是左闭右开[start,end)

class Solution {
public:int jump(vector<int>& nums) {int maxPos=0;int start=0;int end=1;//因为是[ ),所以end为1int step=0;while(end<nums.size()){maxPos=0;for(int j=start;j<end;j++){maxPos=max(maxPos,j+nums[j]);}      start=end;end=maxPos+1;   step++;}return step;}
};

合成一个遍历：
随想录方法一：

class Solution {
public:int jump(vector<int>& nums) {int maxPos=0;int end=0;int step=0;//这里j<nums.size()for(int j=0;j<nums.size();j++){maxPos=max(maxPos,j+nums[j]);if(j==end) {//需要判断j是否覆盖到了最后一个位置nums.size()-1if(j<nums.size()-1){end=maxPos;   step++;if(end>=nums.size()-1) break;//看后面的下一步是否到了最后一个位置}else break;}}return step;}
};

随想录方法二
这里的区间相当于是左闭右闭[j,end] 每次j都会走到end
关于j<nusm.szie()-1就停下来可以看随想录的方法二解析。

class Solution {
public:int jump(vector<int>& nums) {int maxPos=0;int end=0; //[ ]所以end从0开始int step=0;//因为end是从0开始的，在起始位置时，start==end，所以step就加了1，相当于跳了一步了，所以这里j<nums.size()-1,相当于最后一步不用跳了，因为在起始位置就加了1了，跳到倒数第二个位置就好了（因为题目说了一定可以跳到重点，所以倒数第二个位置不为0）for(int j=0;j<nums.size()-1;j++){maxPos=max(maxPos,j+nums[j]);//j相当于是起点，end记录每次跳跃的区间终点，当起点和终点重合之后，也就是该区间的最大的跳跃值已经比较完毕，然后去更新下一次的endif(j==end) {end=maxPos;   step++;}}return step;}
};

1005. K 次取反后最大化的数组和

题目
我的误区：
刚开始想的是将所有的都sort一下，从小到大排列，然后找出前k个，变成正数，想把数组中的数字尽可能多的变成正数
忽略了一个条件就是一个负数可以被一直±±。忽略了k与负数的个数比较，然后又想到下面这个：
k>负数个数时，且数组中有0时，就将多余的k弄到0身上；如果没有0，且k为奇数，则弄到最小的那个负数身上；k为偶数时，就k<=负数个数，就直接从小到大将k个负数弄成正数；如果K还大于0，那么反复转变数值最小的元素，将K用完

正确思路：
随想录：
按照绝对值大小从大到小排列，最后进行消耗k的是绝对值最小的元素，不管该数原来是正数还是负数还是0

• 按照绝对值从大到小进行排列，并从前往后进行遍历，见到负数就变正数，并k–

• 然后检查k是否消耗完了，如果没有消耗完，则在绝对值最小的数字上nums[nums.size()-1]，不断±±，直到k消耗完
  贪心：
  局部最优：负数变为正数，当前数字最大
  全局最优：整个的和最大

  如果将所有负数都变为正数了，k还没有消耗完，则此时问题变为了一个正数的序列，如何改变正负来使整体的和最大。又一次用到了贪心：
  局部最优: 找到绝对值最小的数字，变为负数，反转消耗剩余的k，使得当前的相对值最大（1反转为-1，5反转为-5，-1大于-5）
  全局最优：整个的和最大

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) //这里k>0必须加上，因为最多就是将k个负数变为正数，{nums[i]*=-1;k--;}		  }if(k>0){while(k--)nums[nums.size()-1]*=-1;}int sum=0;for(int j=0;j<nums.size();j++){sum+=nums[j];}return sum;}
};

134. 加油站

题目
方法一：暴力法
模拟环：
for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历，要善于使用while！
错误点：

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int sum=0;for(int j=0;j<gas.size();j++){int i=j;//(1)while(i!=j) //这里是肯定进不来的，因为i一定等于j在（1）处{sum+=gas[i];sum-=cost[i];i++;i=i%gas.size();}if(sum>=0&&i==j)return i;}return -1;}
};

暴力法：【随想录】
暴力法模拟一圈对while循环使用要熟练

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {for (int i = 0; i < cost.size(); i++) {int rest = gas[i] - cost[i]; // 记录剩余油量int index = (i + 1) % cost.size();while (rest > 0 && index != i) { // 模拟以i为起点行驶一圈rest += gas[index] - cost[index];index = (index + 1) % cost.size();}// 如果以i为起点跑一圈，剩余油量>=0，返回该起始位置if (rest >= 0 && index == i) return i;}return -1;};

随想录:贪心方法二
思路：
整个的大思路破解口是：如果整个的gas-cost剩余量>=0说明一定可以走完一圈的；如果小于0，说明从任意一点出发都不可能走完一圈。同理推广到局部的数组，如果在[i,j)内的剩余量<0,说明在[i,j]内的任意一点出发都不可能走完一圈，所以返回的起始点start从j+1开始。
这里必须将整个的剩余油量sum和每个小区间的剩余油量ans分开。
局部最优：
当前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1，因为从j开始一定不行。
全局最优：
找到可以跑一圈的起始位置。

随想录：可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
同理，推到局部：相当于是一个小数组
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。

class Solution {public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int ans=0;int start=0;int sum=0;//  for(int i=0;i<gas.size();i++)//  {// 	 ans+=gas[i]-cost[i];//  }//   if(ans<0)  return -1;//这里使用一个for循环即可for(int i=0;i<gas.size();i++){ans+=gas[i]-cost[i];sum+=gas[i]-cost[i];if(ans<0){//i++;start=i+1;ans=0;}}if(sum<0) return -1;return start;}};

随想录贪心方法一：没懂，为什么要从后往前填平min?
贪心一

135. 分发糖果。。。。。。

题目

860.柠檬水找零

题目
三种情况：

1. 5元直接接收
2. 10元，用5元找零
3. 20元，用5+10或者5*3找零（需要讨论的就是这一种情况）

误区：

• 题意要弄清楚！不能进行排序
• 刚开始还用sum，其实不准确，应该单独分开然后思路更加清晰

涉及的贪心：
遇到20的情况，应该先利用10+5的组合，而不是5*3的组合，因为5元可以找零10和20 ，更加玩万能；否则就会有测试样例过不去

class Solution {
public:bool lemonadeChange(vector<int>& bills) {        //  sort(bills.begin(),bills.end()); 不能排序！！int five=0;int ten=0;//   int twenty=0; 可以不用写20for(int i=0;i<bills.size();i++){if(bills[i]==5){five++;}else if(bills[i]==10){if(five>0){five--;ten++;}else return false;}else if(bills[i]==20){if(five>=1&&ten>=1){five--;ten--;}else if(five>=3){five=five-3;}else return false;}}return true;}
};

406. 根据身高重建队列

题目
思路:
【随想录】
两个维度技巧：确定一边，然后贪心另一边
本题也是两个维度，和分糖果那道题差不多，也是先确定一个维度的排序，再去确定另一个维度的排序。
如果按照后面的k排序，排出的结果没有啥用；所以先对身高进行从大到小的排序，再根据k进行插入排序，注意插入排序就是只看k的大小就好，因为是在身高从大到小的顺序上进行的所以，前面的排序不会干扰后面的排序。
贪心：
局部最优：按照身高从大到小进行排序并按照k的大小进行插入排序，使people满足了队列的属性
全局最优：使整个people满足队列的属性

class Solution {
public:static bool cmp(vector<int>&a,vector<int>&b){if(a[0]>b[0]){return true;}else if(a[0]==b[0]){return a[1]<b[1];}return false;}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 pos=people[i][1];result.insert(result.begin()+pos,people[i]);}return result;}
};

使用vector和list的不同之处：
vector的底层是使用的list，vector每次插入元素当大于capacity时就会扩容到两倍，因此会效率不高，使用list会效率高

list版本

class Solution {
public:static bool cmp(vector<int>&a,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);list<vector<int>> result;for(int i=0;i<people.size();i++){list<vector<int>>::iterator it=result.begin();int k=people[i][1];while(k--){it++;}result.insert(it,people[i]);}return   vector<vector<int>>(result.begin(),result.end());}
};

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

题目

思路：
【随想录】
按起点排序或者终点排序都可以，这里用起点从小到大进行，每次就检查前一个的终点和后一个的起点是否重叠，如果不重叠就新射一箭result++,如果重叠了，就更新最小有边界，因为每次都是比较上一个的有边界！
新学习到的：画图！题目是需要知道个数，模拟时不需要真的去移除，而是像之前换零钱一样，直接计数即可

class Solution {
public:// static bool cmp(vector<int>&a,vector<int>&b)// {//     if(a[1]==b[1])//        return a[0]<b[0];//     return a[1]>b[1];// }static bool cmp(vector<int>&a,vector<int>&b){return a[0]<b[0];}int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(),points.end(),cmp);int result=1;for(int i=1;i<points.size();i++){//没有重叠if(points[i][0]>points[i-1][1]){result++;}else {//更新最小的有边界，画图可以看出！！points[i][1]=min(points[i-1][1],points[i][1]);}}return result;}
};

435. 无重叠区间

题目
贪心法则：

• 如果是右边界从小到大进行排列，则从前往后遍历，贪心体现在尽量右边界越小越好，这样会给后面的元素留下更多的空间
• 如果是按照左边界从小到大进行排列，则从后往前遍历，贪心体现在尽量左边界越大越好，这样会给前面的元素留下更多的空间。

这里用的是有边界从小到大进行排列，从前向后进行遍历。
技巧：
贪心中的逆向思维：求一个最小值，可以用总数减去它相反的最大值
因此这里将找最少的可去区间变成了，找最多的不重叠的区间，再用总数减去最多的不重叠区间。

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 sum=1;int end=intervals[0][1];for(int i=1;i<intervals.size();i++){//这里不是intervals[i][0]>intervals[i-1][1];直接用end记录上一个的最后一个边界，这里的上一个不是i-1,而是符合不交叉条件的上一个 注意这里还是>=//这里使用的切割点就是endif(intervals[i][0]>=end){sum++;    end=intervals[i][1];}}return intervals.size()-sum;}
};

763. 划分字母区间

题目
就是统计每一个字符最后出现的位置，用哈希，然后再遍历字符串，设置一个start和end，表示分割的区间，当遍历i==区间最大值时则是分割点。如下图：第一个区间的最大值是8，当遍历到8时说明前面区间最大值已经到头了，所以找到了第一个分割点。

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

随想录：
字母哈希可以直接用a[27]来映射

class Solution {
public:vector<int> partitionLabels(string s) {vector<int>result;int hash[27]={0};for(int i=0;i<s.size();i++){hash[s[i]-'a']=i;}int end=0;int start=0;for(int i=0;i<s.size();i++){end=max(end,hash[s[i]-'a']);if(end==i){result.push_back(end-start+1);start=i+1;}}return result;}
};

随想录补充
根据打气球和无重叠区间的思路来解，找到每一个字符的开始和结束区间，然后再根据左边界从小到大进行排列，从左向右遍历，目标是找到不重叠的区间，判断条件：当下一个的左边界大于前面的最大有边界时，就说明是找到了不重叠的区间，也就是分割点了。

class Solution {
public:static bool cmp(vector<int> &a, vector<int> &b) {return a[0] < b[0];}// 记录每个字母出现的区间vector<vector<int>> countLabels(string s) {vector<vector<int>> hash(26, vector<int>(2, INT_MIN));vector<vector<int>> hash_filter;for (int i = 0; i < s.size(); ++i) {if (hash[s[i] - 'a'][0] == INT_MIN) {hash[s[i] - 'a'][0] = i;}hash[s[i] - 'a'][1] = i;}// 去除字符串中未出现的字母所占用区间for (int i = 0; i < hash.size(); ++i) {if (hash[i][0] != INT_MIN) {hash_filter.push_back(hash[i]);}}return hash_filter;}vector<int> partitionLabels(string s) {vector<int> res;// 这一步得到的 hash 即为无重叠区间题意中的输入样例格式：区间列表// 只不过现在我们要求的是区间分割点vector<vector<int>> hash = countLabels(s);// 按照左边界从小到大排序sort(hash.begin(), hash.end(), cmp);// 记录最大右边界int rightBoard = hash[0][1];int leftBoard = 0;for (int i = 1; i < hash.size(); ++i) {// 由于字符串一定能分割，因此,// 一旦下一区间左边界大于当前右边界，即可认为出现分割点if (hash[i][0] > rightBoard) {res.push_back(rightBoard - leftBoard + 1);leftBoard = hash[i][0];}rightBoard = max(rightBoard, hash[i][1]);}// 最右端res.push_back(rightBoard - leftBoard + 1);return res;}
};

56. 合并区间

题目
我的：根据上一道题目的随想录补充的思路写的，当出现不重叠的区间时就加入到result中，然后用right不断地记录最大的右边界。
这里和随想录的解析有点不一样，需要再看一下随想录的解析
随想录解析，以及最后一个区间，何时加入！

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) {sort(intervals.begin(),intervals.end(),cmp);int left=intervals[0][0];int right=intervals[0][1];vector<vector<int>> result;for(int i=1;i<intervals.size();i++){if(intervals[i][0]>right){result.push_back({left,right});left=intervals[i][0];}        	right=max(right,intervals[i][1]);}//最后一个区间result.push_back({left,right});return result;}
};

738. 单调递增的数字

题目
方法一：暴力法
自己写的：超时

class Solution {
public:bool judge(int a){int t=INT_MAX;int b=0;while(a){b=a%10; //3 2 1a=a/10;  //12 1 0if(t<b) return false;t=b; }return true;}int monotoneIncreasingDigits(int n) {if(judge(n))return n;while(n--){if(judge(n)){return n;}}return 0;}
};

随想录：
思路：从后往前遍历，当遇到前一个字符s[i-1]比当前字符s[i]大时就将前一个字符减去一，s[i-1]–,将当前字符变为9,s[i]=‘9’.eg： 98，则变成了89.
使用flag记录第一个需要改变的位置，然后从该位置起将字符改为9.
直接将flag赋值为s.size()，如果s直接是递增整数，就不用改9了
单个数字字符（0-9，两位的就不行了，因为0-9才有ascii码）直接–可以得到小一个的数，但是其他不能保证

class Solution {
public:int monotoneIncreasingDigits(int N) {string strNum = to_string(N);// flag用来标记赋值9从哪里开始// 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行int flag = strNum.size();for (int i = strNum.size() - 1; i > 0; i--) {if (strNum[i - 1] > strNum[i] ) {flag = i;strNum[i - 1]--;}}for (int i = flag; i < strNum.size(); i++) {strNum[i] = '9';}return stoi(strNum);}
};

我写的：看的思路

class Solution {
public:int monotoneIncreasingDigits(int n) {string s=to_string(n);int flag=0;for(int i=s.size()-1;i>=1;i--){if(s[i-1]>s[i]){s[i-1]=to_string((s[i-1]-'0')-1)[0];flag=i;}}if(flag!=0){for(int i=flag;i<s.size();i++)s[i]='9';}return atoi(s.c_str());}
};

714. 买卖股票的最佳时机含手续费

题目
方法一：贪心
看了官方解
思路：
每次买入的时候交手续费
buy表示你手上的股票买入的最低价格，初始化为price[0]+free
当前的price[i]+free<buy时，说明遇到了一个比现在手上股票还低的股票，这个时候应该与其用现在手上的buy买股票，还不如用当前的price[i]+free买,所以将buy更新为buy=price[i]+free;
如果当前股票price[i]>buy，说明可以卖出并获得price[i]-buy的收益，但是该结果不一定是最优的，因为后面可能会出现比price[i]还高的价格，所以可以看成是当前我用price[i]买了一只股票，即将buy更新为price[i]-free，后面如果出现了新的高的价格即price[i+1]>price[i]时，就会累加收益price[i+1]-buy (buy=price[i]),相当于是price[i+1]-price[i]
其余的情况，当price[i]在[buy-free,buy]之间，表示当前股票没有低到让我们去买，也没有高到让我们去卖，就什么也不做

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int buy=prices[0]+fee;int result=0;for(int i=1;i<prices.size();i++){if(prices[i]+fee<buy) buy=prices[i]+fee;else if(prices[i]>buy) {//注意这里是else !!!因为第一个if已经改变了buy的值result+=prices[i]-buy;//buy=prices[i]+fee;buy=prices[i];//因为只需要减一次fee,eg：相当于下一次直接是累加result后为price[i+1]=price[i];}}return result;}
};

方法二：动态规划 待学。。。

968. 监控二叉树

题目
随想录思路：
题目破解口：摄像头不能安装到叶子节点上。
因此：从下往上进行遍历，每一个结点有三种状态:
0: 没有被覆盖
1：有摄像头
2：被覆盖了
使用后序遍历，从下向上进行，根据左右子树的状态确定当前结点的状态：

• 如果左右子树中都被覆盖了if(left= =2&&right= =2)，说明他们的父节点没有被覆盖（从下往上进行的），返回0；
• 如果左右子树中有一个没被覆盖或者都没被覆盖if(left= =0||right= =0)，说明他们的父节点该安装摄像头了，所以就result++，将其返回1；
• 如果左右子树全有一个有摄像头if(left= =1||right= =1)，说明父节点一定被覆盖了，返回2；
• 最后还要判断头结点是否被覆盖，如果没有则给头结点安装摄像头result++

随想录解析

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int result=0;int postOrder(TreeNode* root){if(root==NULL) return 2;int left=postOrder(root->left);int right=postOrder(root->right);if(left==0||right==0) {result++;return 1;}if(left==2&&right==2){return 0;}if(left==1||right==1){return 2;}return -1;}int minCameraCover(TreeNode* root) {if(postOrder(root)==0)result++;return result;}
};

难点：
贪心的思路，如何遍历状态的推导