【代码随想录】贪心
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 因为时两种不同的情况，并且不是互斥的所以不用else
if(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为1
int 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()-1
if(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记录每次跳跃的区间终点，当起点和终点重合之后，也就是该区间的最大的跳跃值已经比较完毕，然后去更新下一次的end
if(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.柠檬水找零
题目
三种情况：
- 5元直接接收
- 10元，用5元找零
- 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; 可以不用写20
for(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,而是符合不交叉条件的上一个 注意这里还是>=
//这里使用的切割点就是end
if(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 1
a=a/10; //12 1 0
if(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;
}
};
难点：
贪心的思路，如何遍历状态的推导