【代码随想录】贪心

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()则就说明是最大的

懂了懂了！！！就是从ii+nums[i]之间的所有位置i都能到达，只不过i可以走一步，走两步…最大可以走i+nums[i]步，所以就在ii+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;}
};

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/475948.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

QWen2.5学习

QWen2.5学习

配置环境 pip install transformers 记得更新一下&#xff1a;typing_extensions pip install --upgrade typing_extensions 安装modelscope modelscope/modelscope: ModelScope: bring the notion of Model-as-a-Service to life. 下载这个仓库的代码上传到服务器解压 推…
阅读更多...
存算分离的过去、现在和未来

存算分离的过去、现在和未来

存算分离架构&#xff0c;作为数据处理领域的一个重要概念&#xff0c;从其最初的雏形到如今广泛应用&#xff0c;经历了多次迭代和变革。雁飞老师在分享中从过去的存算架构&#xff0c;逐步讲述存算分离的演进&#xff0c;现今的存算分离架构的优势及其在 Databend 中的体现&a…
阅读更多...
web——upload-labs——第九关——特殊字符::$DATA绕过

web——upload-labs——第九关——特殊字符::$DATA绕过

特殊字符::$DATA绕过 典型绕过场景 在一些系统中&#xff0c;::$DATA 被用于绕过文件路径的限制。比如&#xff1a; 路径过滤绕过&#xff1a;如果系统有某种机制来检查和限制文件路径&#xff08;例如&#xff0c;禁止访问某些系统目录或敏感文件&#xff09;&#xff0c;通…
阅读更多...
图的存储、遍历以及Dijkstra/Floyd/Kruskal/Prim/拓扑排序/关键路径(实验8--作业)

图的存储、遍历以及Dijkstra/Floyd/Kruskal/Prim/拓扑排序/关键路径(实验8--作业)

图–数据结构操作与算法全解析 一、引言 图作为一种重要的数据结构&#xff0c;在计算机科学与众多领域中都有着广泛的应用。它能够有效地描述和解决各种复杂的关系问题&#xff0c;如网络拓扑、路径规划、资源分配等。本文将详细介绍图的相关操作和知识点&#xff0c;包括图…
阅读更多...
利用Vue的相关特性，制作相册

利用Vue的相关特性，制作相册

目录 一、整体结构 1、设置一个div盒子 2、设置图片展示 3、页码按钮 4、翻页按钮 二、CSS样式 1、 .clear_ele::after 2、设置图片、按钮等属性的样式 三、JavaScript部分&#xff08;Vue&#xff09; 1、导入模块 2、创建Vue应用 ①定义响应式数据 ②定义事件处…
阅读更多...
优化表单交互：在 el-select 组件中嵌入表格显示选项

优化表单交互：在 el-select 组件中嵌入表格显示选项

介绍了一种通过 el-select 插槽实现表格样式数据展示的方案&#xff0c;可更直观地辅助用户选择。支持列配置、行数据绑定及自定义搜索&#xff0c;简洁高效&#xff0c;适用于复杂选择场景。完整代码见GitHub 仓库。 背景 在进行业务开发选择订单时&#xff0c;如果单纯的根…
阅读更多...
（C语言）文件操作

（C语言）文件操作

目录 文件 程序文件 数据文件 文件名 ​编辑数据文件的分类 文件的打开和关闭 流 标准流 1&#xff09;stdin 2&#xff09;stdout 3&#xff09;stderr 文件指针 文件的打开和关闭 对文件内容操作的函数 1&#xff09;fgetc&#xff0c;fputc 2&#xff09;fp…
阅读更多...
AI修改验证账号名正则表达式的案例

AI修改验证账号名正则表达式的案例

我有如下的一行老代码&#xff0c;今天复用的时候发现当时注释写错了&#xff0c;改好以后请AI再检查一遍。 因为这次AI的分析的思路很典范&#xff0c;所以拿出来分享一下。 提问&#xff1a; 请看一下这个正则和后面的注释是否匹配&#xff0c;现在的验证规则是否保证账号至…
阅读更多...
SQL进阶技巧：如何进行数字范围统计？| 货场剩余货位的统计查询方法

SQL进阶技巧：如何进行数字范围统计？| 货场剩余货位的统计查询方法

目录 0 场景描述 1 剩余空位区间和剩余空位编号统计分析 2 查找已用货位区间 3 小结 0 场景描述 这是在做一个大型货场租赁系统时遇到的问题&#xff0c;在计算货场剩余存储空间时&#xff0c;不仅仅需要知道哪些货位是空闲的&#xff0c;还要能够判断出哪些货位之间是连…
阅读更多...
彻底理解如何保证Redis和数据库数据一致性问题

彻底理解如何保证Redis和数据库数据一致性问题

一.背景 系统中缓存最常用的策略是&#xff1a;服务端需要同时维护 DB 和 Cache 并且是以 DB 的结果为准&#xff0c;那么就可能出现 DB 和 Cache 数据不一致的问题。 二.读数据 逻辑如下&#xff1a; 当客户端发起查询数据的请求&#xff0c;首先回去Redis中查看没有没该数据&…
阅读更多...
后仿真中的SDF语法之关键字 IOPATH 用法详解

后仿真中的SDF语法之关键字 IOPATH 用法详解

在后仿真中&#xff0c;SDF&#xff08;Standard Delay Format&#xff09;文件用于描述设计的时序信息&#xff0c;而IOPATH是SDF中的一个关键结构&#xff0c;用于定义单元间的路径延迟。以下是IOPATH关键字的用法及其相关内容的详细介绍&#xff1a; IOPATH结构旨在将延迟数…
阅读更多...
Springboot 整合 Java DL4J 搭建智能问答系统

Springboot 整合 Java DL4J 搭建智能问答系统

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/literature?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;…
阅读更多...
基于SpringBoot的“网上书城管理系统”的设计与实现（源码+数据库+文档+PPT)

基于SpringBoot的“网上书城管理系统”的设计与实现（源码+数据库+文档+PPT)

基于SpringBoot的“网上书城管理系统”的设计与实现&#xff08;源码数据库文档PPT) 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBoot 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 系统功能结构图 系统首页界面图 用户注册界面…
阅读更多...
测评部署和管理 WordPress 最方便的面板

测评部署和管理 WordPress 最方便的面板

新版宝塔面板快速搭建WordPress新手教程 - 倚栏听风-Morii - 博客园 初学者使用1Panel面板快速搭建WordPress网站 - 倚栏听风-Morii - 博客园 可以看到&#xff0c;无论是宝塔还是1Panel&#xff0c;部署和管理WordPress都有些繁琐&#xff0c;而且还需要额外去配置Nginx和M…
阅读更多...
网络安全问题概述

网络安全问题概述

1.1.计算机网络面临的安全性威胁 计算机网络上的通信面临以下的四种威胁&#xff1a; (1) 截获——从网络上窃听他人的通信内容。 (2) 中断——有意中断他人在网络上的通信。 (3) 篡改——故意篡改网络上传送的报文。可应用于域名重定向&#xff0c;即钓鱼网站。 (4) 伪造——伪…
阅读更多...
视觉顶会论文 | 基于Swin Transformer的轴承故障诊断

视觉顶会论文 | 基于Swin Transformer的轴承故障诊断

往期精彩内容&#xff1a; Python-凯斯西储大学&#xff08;CWRU&#xff09;轴承数据解读与分类处理 Pytorch-LSTM轴承故障一维信号分类(一)-CSDN博客 Pytorch-CNN轴承故障一维信号分类(二)-CSDN博客 Pytorch-Transformer轴承故障一维信号分类(三)-CSDN博客 三十多个开源…
阅读更多...
Altenergy电力系统控制软件 status_zigbee SQL注入漏洞复现(CVE-2024-11305)

Altenergy电力系统控制软件 status_zigbee SQL注入漏洞复现(CVE-2024-11305)

0x01 产品简介 Altenergy电力系统控制软件是Altenergy Power System推出的一款专业软件。旨在为用户提供全面、高效、安全的电力系统控制解决方案。广泛应用于各类电力系统领域，如电力调度中心、发电厂、变电站、工业园区等。通过该软件的应用，用户可以实现对电力系统的全面…
阅读更多...
java: spire.pdf.free 9.12.3 create pdf

java: spire.pdf.free 9.12.3 create pdf

可以用windows 系统中文字体&#xff0c;也可以从文件夹的字体文件 /*** encoding: utf-8* 版权所有 2024 ©涂聚文有限公司* 许可信息查看&#xff1a;言語成了邀功盡責的功臣&#xff0c;還需要行爲每日來值班嗎* 描述&#xff1a;* # Author : geovindu,Geovin Du 涂…
阅读更多...
AUTOSAR网络管理中的主动唤醒与被动唤醒

AUTOSAR网络管理中的主动唤醒与被动唤醒

文章目录 1、主动/被动唤醒源、主动/被动唤醒节点2、网络拓扑说明 1、主动/被动唤醒源、主动/被动唤醒节点 休眠唤醒需要有一个触发源来进行触发&#xff0c;我们常用的NM报文是其中的载体之一。休眠唤醒的触发源又分为主动唤醒源和被动唤醒源。 主动唤醒源&#xff0c;就是能…
阅读更多...
索贝融媒体 Sc-TaskMonitoring/rest/task/search SQL注入漏洞复现

索贝融媒体 Sc-TaskMonitoring/rest/task/search SQL注入漏洞复现

0x01 产品简介 索贝融媒体产品是成都索贝数码科技股份有限公司（简称索贝）为各级电视台和媒体机构打造的一套集互联网和电视融合生产的解决方案。其代表产品为MCH2.0融合媒体生产业务系统，该系统带来了媒体领域一种全新的融合生产流程和工作机制，具有全方位的资源汇聚能力、…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023