假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 1: 输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。 所以你应该输出1。
示例 2: 输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出2.
提示：
思路：贪婪：意思是渴望而不知满足。在我们算法中，贪婪就是最优全局解，什么最优全局解？比如以上的这道题：最优全局解就是尽可能大的孩子数量。如何实现全局最优解？就要实现局部最优解？就拿分饼干来说，我们要让大饼干喂胃口大的人。这就是局部最优，如果你拿大饼干喂小胃口，那么满足的孩子数量就会减少，【1，3】【1，2，3】如果你拿3，喂孩子，就只能满足一个孩子。对孩子胃口与饼干大小按递增的顺序排序，从后往前遍历，然后就要保证s[j]>=s[i]。
//编码技巧，如果有两个循环的话，我们可以设置一个循环，令另外一个直接循环内递减就可以了。
class Solution {
public:
int findContentChildren(vector& g, vector& s) {
int number=0;
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int index=s.size()-1;
for(int i=g.size()-1;i>=0;i--){
if(index>=0&&s[index]>=g[i]){
number++;
index--;
}
}
return number;
}
};
Leetcode.376.摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例 1：
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
示例 2：
输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
示例 3：
输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2
提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
思路：这道题我们可以使用物理里的波峰与波谷的原理，来解决，最长子序列=波峰数量+波谷数量+两头的数量。为什么可以这么想，要实现波动，意味着波峰与波谷之间不能有数字。我们只统计波峰与波谷的数量的就可以忽略波峰与波谷中间的数字。同时我们还要思考两个特殊情况，第一：只有一个数字，就返回1，如果有两个数字，那么就要返回2，如何才能得到一个这样的数字呢？比如【2，3】，我们可以想象它为【2，2，3】，同时我们设当前的坡度为cur=3-2=1,那么pre(前一坡度)就为0. 当cur>0且pre<=0的时候我们我们就可以递增result(波峰波谷数)，同理当遇到【3，2】时 当cur<0,pre>=0时我们就可以递加结果数。同时我们设置初始的result就为1.
综上所述：
class Solution {
public:
int wiggleMaxLength(vector& nums) {
if(nums.size()==1)return nums.size();
int result=1;//为啥要设置为1，这是针对只有两个数时候，在其他情况也适合，因为总数=波峰+波谷+两端数
int pre=0;
int cur=0;
for(int i=0;i0)||(pre>=0&&cur<0)){
result++;
pre=cur;//更新前一坡度。
}
}
return result;
}
};
Leetcode.53.最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [0]
输出：0
示例 4：
输入：nums = [-1]
输出：-1
示例 5：
输入：nums = [-100000]
输出：-100000
提示：
1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
思路：
一开始我想是暴力，双循环，结果超出时间限制，蒙蔽了。之后学习一一种放大，贪心，所谓局部最优就是每次的和都必须大于0，这样整体才能最大，然后如果和小于零，那么总和就会变小。于是我们必须保证每次和都要大于零，一旦和不大于0，那么就把重新求和。令和为0，从下一个数字开始重新递归，同时我们要保存每一次的和，以防出现，下一次的数是最后一个数，且数字小于之前的总和。
class Solution {
public:
int maxSubArray(vector& nums) {
int result=INT32_MIN;
int count=0;
for(int i=0;iresult)result=count;
if(count<=0){
count=0;
}
}
return result;
}
};
Leetcode.122.买卖股票的最佳时机II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1: 输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2: 输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
思路：这是一只股票，你只要在卖出后，才能重新购买这只股票。我们一只股票的交易最小天数为2.如何才能获得最大利润呢？比如对于 7 1 5 3 6 4 这只股票。局部最优解是什么呢？我们可以把股票的利润分解到每一天。比如第1天购入股票，第三卖去，那么利润为-4=(prices[3]-priecs[2])+(prices[2]-prices[1])+prices[1]-prices[0].这样就可以得到每天的利润，只要把所有的正利润加起来，就是最大利润,从而实现全局最优解
class Solution {
public:
int maxProfit(vector& prices) {
int res=0;
for(int i=0;i0){
res+=prices[i+1]-prices[i]
}
}
return res;
}
};
Leetcode.55.跳跃游戏
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示：
1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105
思路：在覆盖范围内，计算出覆盖范围内的元素的覆盖范围能够大于等于nums.size().什么是覆盖范围，比如数组 2，3，1，1，4，。当i=0的时候他的最远覆盖距离为2，它只能到2，3，1.在这个返回内计算出每个元素的覆盖范围，比如i=1在覆盖范围内，所以更新之后的覆盖范围，就是1+3=4。就能到达最后位置，返回true。如果到不到最后的位置，那么就是就继续求下一个元素的覆盖范围，如果前面的n-1哥元素都不能到达，就返回false。
class Solution {
public:
bool canJump(vector& nums) {
int cover=0;
if(nums.size()==1)return true;
for(int i=0;i<=cover;i++){
cover=max(i+nums[i],cover);
if(cover>=nums.size()-1){
return true;
}
}
return false;
}
};
Leetcode.45.跳跃游戏二
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示:
1 <= nums.length <= 104
0 <= nums[i] <= 1000
思路：我们回顾一下跳跃游戏Ⅰ，我们使用了一个叫覆盖范围。什么是覆盖范围呢？覆盖范围就是在i+nums[i],就是你最远能够跳跃的范围。我们在覆盖范围内求取每个元素的覆盖范围，当覆盖范围大于等于数组大小的时候。我我们就说第一个元素能跳到最后一个元素。这道题我们采用覆盖范围的形式。我们要想什么时候我们会跳跃，当在一个覆盖范围内的所有元素他们的覆盖范围都没有到达最后一个元素。我们这时就要跳到该范围的最后一个元素，
这样就可以减少跳跃的次数。所以我们需要3 个参数，第一，当前元素的范围，下一个元素的范围。第三跳跃次数。当i==cur范围的时候说明前面的所以元素的覆盖范围都没到达最后一个元素，所以我们呢就必须跳跃。更新最大的覆盖范围。
class Solution {
public:
int jump(vector& nums) {
if(nums.size()==1)return 0;
int cur=0;//当前覆盖最远下表
int next=0;//下一元素的覆盖的最远下表
int ans=;//跳跃次数
for(int i=0;i=nums.size()-1) break;//如果下一个元素的最远覆盖下标直接到达最后一个位置，
}
else break;//当前的最远覆盖下标到达最后位置。
}
}
return ans;
}
};
方法2
每次当i等于当前最远覆盖范围的下标的时候，就意味着我们需要跳跃。所以我们将i 给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。） 以这种方式修改数组后，返回数组可能的最大和。 示例 1： 输入：A = [4,2,3], K = 1 输入：A = [3,-1,0,2], K = 3 输入：A = [2,-3,-1,5,-4], K = 2 提示： 1 <= A.length <= 10000 思路：我们一开始可以想到的就是，把所有的-变为+，但是其实我们应该是把尽可能的把最大的-变为+。然后如果之后如果k!=0那我们可以继续把-变为+，之后如果看看看k!=0的话那我们就把最小正数变为复数。所以这道题运用了两道贪心思路：第一个贪心思路是尽可能的把最大复数变为正数，从而实现最优解，第二个在全部是正数的情况下且k还不为0，我们尽可能让最小整数变为复数。所以如果才能让最大-变为+，我们可以对其进行按绝对值的大小从大往小排序。 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。 如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。 说明: 如果题目有解，该答案即为唯一答案。 输入: 输出: 3 解释: 输入: 输出: -1 解释: 思路： 如何才能走完一圈呢？第一总油量大于总消耗。第二，在行驶的过程中，不能出现在前面几站[i,j]存下来的油不能满足下一站所需要的油。如果出现这种情况的话，那么前面几站都不能作为出发点，所以出发点应该就是j+1.所以局部最优解是：在这一站的gas-cost要大于0，才能作为出发点，如果没有就继续往后找，全局解：就是直到找到可以跑完一圈的gas-cost的出发点（当然这是确保在第一个条件的基础上的） 我发现了leetcode的一个题解发的题的另外一种解读很有意思： 有一个环形路上有n个站点； 每个站点都有一个好人或一个坏人； 好人会给你钱，坏人会收你一定的过路费，如果你带的钱不够付过路费，坏人会跳起来把你砍死； 问：从哪个站点出发，能绕一圈活着回到出发点? 首先考虑一种情况：如果全部好人给你 的钱加起来 小于 坏人收的过路费之和，那么总有一次你的钱不够付过路费，你的结局注定会被砍死。 假如你随机选一点 start 出发，那么你肯定会选一个有好人的站点开始，因为开始的时候你没有钱，遇到坏人只能被砍死； 现在你在start出发，走到了某个站点end，被end站点的坏人砍死了，说明你在 [start, end) 存的钱不够付 end点坏人的过路费，因为start站点是个好人，所以在 (start, end) 里任何一点出发，你存的钱会比现在还少，还是会被end站点的坏人砍死； 于是你重新读档，聪明的选择从 end+1点出发，继续你悲壮的征程； 终于有一天，你发现自己走到了尽头（下标是n-1)的站点而没有被砍死； 此时你犹豫了一下，那我继续往前走，身上的钱够不够你继续走到出发点Start? 当然可以，因为开始已经判断过，好人给你的钱数是大于等于坏人要的过路费的，你现在攒的钱完全可以应付 [0, start) 这一段坏人向你收的过路费。 这时候你的嘴角微微上扬，眼眶微微湿润，因为你已经知道这个世界的终极奥秘：Start就是这个问题的答案。 在柠檬水摊上，每一杯柠檬水的售价为 5 美元。 顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。 每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。 注意，一开始你手头没有任何零钱。 如果你能给每位顾客正确找零，返回 true ，否则返回 false 。 示例 1： 输入：[5,5,5,10,20] 输出：true 解释： 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。 由于所有客户都得到了正确的找零，所以我们输出 true。 示例 2： 输入：[5,5,10] 输出：true 示例 3： 输入：[10,10] 输出：false 示例 4： 输入：[5,5,10,10,20] 输出：false 解释： 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。 由于不是每位顾客都得到了正确的找零，所以答案是 false。 提示： 思路：注意在找零20的时候优先找会10和5，因为5可以用来找5和10，10只能用来找20的，所以尽可能少用5， 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。 你需要按照以下要求，帮助老师给这些孩子分发糖果： 那么这样下来，老师至少需要准备多少颗糖果呢？ 示例 1: 输入: [1,0,2] 输出: 5 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。 示例 2: 输入: [1,2,2] 输出: 4 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果，这已满足上述两个条件。 思路：局部最优解：两次遍历，从左至右遍历，确保右孩子评分高的糖果数大于左孩子，在从右至左遍历，确保左孩子评分高的糖果数大于有孩子， 从而实现全局最优解，得分高的孩子的糖果数比左右孩子高。 要解决的问题：问题一： 为什么从右至左遍历：如果从左至右遍历的话，rating[i]由rating[i+1]确定无法利用上一次比较的结果，例如 分数1，2，2，5，4，3，2，从左至右的第一次遍历为1，2，1，2，1，1，1.如果再按照从左至右遍历的话，就是 1 2 1 3 2 2 1.产生了错误。 问题二：再第二次遍历的时候为什么要去取得 fruitnum[i + 1] + 1 和 fruitnum[i] 最大的糖果数量？只有这样才能保持fruitnum[i] 比右边大，同时比左边大。例如：1，2，3，4，5，2，1 第一次，1，2，3，4，5，1，1.第二次，1，2，3，4，5，2，1。如果再5与2之间比较比取最大的话，那么就会取3.编程1，2，3，4，3，2，1.不符合题目条件 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。 请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。 示例 1： 输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] 思路：这道题给了两个属性，一个是h身高，k:在这个人前面身高大于等于h 有多少个。所以我们可以先将身高排序，我们就知道在people[i]前面都是比我们大的人。我们只需要根据下标k把对应的人插入道对应的位置就可以了。注意：在排序的时候如果两个人的身高相同，那么小的k在前面。 一般拿到两个维度，可以首先确定一个维度 在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。 一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。 给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。 示例 1： 输入：points = [[10,16],[2,8],[1,6],[7,12]] 输入：points = [[1,2],[3,4],[5,6],[7,8]] 输入：points = [[1,2],[2,3],[3,4],[4,5]] 输入：points = [[1,2]] 输入：points = [[2,3],[2,3]] 提示： 1 <= points.length <= 104 思路： 当气球重叠的时候一起射那么就可以用最少数量的弓箭？如何处理射击重叠气球呢？就是前一个一起的最右与后一个气球的最左边是否重合。如果不重合就弓箭数量+1，如果重合，那么就更新重叠气球的最小右边界，继续循环，看下一个气球的最左边界是否小于重叠气球的最小右边界。如果小于，那么这3个气球都是重合的，否则就只有前两个气球重合。 注意：至少有一个气球所以，弓箭数量至少唯一；第二：我们应该进行排序，确保最多的重叠气球。 https://leetcode-cn.com/problems/non-overlapping-intervals/ 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。 示例 1: 输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。 示例 2: 输入: [ [1,2], [1,2], [1,2] ] 输出: 2 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。 示例 3: 输入: [ [1,2], [2,3] ] 输出: 0 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。 思路：这道题与上面的那道射击气球的题非常的相似。上面那道题是判断两个气球是不是重复的。重复的气球只需要打一枪，“两个气球=一个气球”，而这道题求移除区间的数量，这个不就是重复气球中的一个气球吗？所以换个思路想考，我们要求移除区间，就要用总的区间数-非重叠的区间数。非重叠的区间数也就是我们要求射击气球的最小数量【但是需要一点点的修改：原来[ 1, 2] [2.3]在气球哪里是重复的，算做一枪，但是在这道题中，不算覆盖重叠】 思路：右边界排序，从左往右遍历，让左边的空间经可能的小，让右边的空间经可能的大。这样就能保证使重叠区间数增加，需要删除的空间数减少 。 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。 示例： 输入：S = “ababcbacadefegdehijhklij” 输出：[9,7,8] 解释： 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。 提示： 思路：统计每个字符出现最远的位置的下标，同时遍历这个字符串，找到下标在字符串中的位置从而确定片段 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。 示例 1： 输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输入：intervals = [[1,4],[4,5]] 提示： 1 <= intervals.length <= 104 思路：本题我采用的左排序（），从左往右遍历，你可能会说为什么不从右往左遍历，在前面的题中我们采用从右往左遍历是为了确保左边界足够的大，给右空间足够的空间，减少覆盖空间。这道题我们是为了合并重叠区间，所以右边界足够的大，确保重叠区间足够的大。同时左边界足够的小，确保区间尽可能的重叠 给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。 （当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。） 示例 1: 输入: N = 10 输入: N = 1234 输入: N = 332 思路：举一个例子，98，我们如何将其变为递增，要使x-1<=x.所以我们只有将小的那个数变为9，大的那个数减一，这样才能确保得到最大的整数。知道这个之后我们思考因该需要遍历这个数字，那该如何遍历呢，从前往后，还是重后往前。举个例子332如果从前往后遍历得到329.不满住题意，【442，552，662，都会遇到这样的情况，后面的遍历没有用到前面的遍历结果】所以我们应该从后往前遍历. 技巧：为了我们能够修改数字，我们先把数字转化为字符串。 给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。 你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。 返回获得利润的最大值。 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。 示例 1: 输入: prices = [1, 3, 2, 8, 4, 9], fee = 2 输出: 8 解释: 能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8. 注意: 思路：在lc122的那个题中，我们不需要搞清楚买入时间，卖出时间。我们是把交易分解为每天的交易来计算，把所有的正利润相加就是整体的最大利润。而我们这到题含手续费，就需要考虑买入时间，与卖出时间。因为每笔交易要缴纳手续费，同时可能存在每天的利润不够交易费的情况。所以我们分了以下3种情况考虑 第一：如果存在后面一天的价格小于最低价格就更新最低价格。 第二：如果后面一天的价格大于最低价格，但是后面的价格小于最低价格加手续费，说明如果在这一天购买就会亏，或者不亏不赚，那么就不需要操作，继续遍历。 第三：如果后面一天的价格大于最低价格加手续费，那么就要计算利润。同时更新最小价格为当前价格减去fee【防止下一天的价格大于当天价格我们，我们需要在下一天买出多减去一个fee.比如，13289.我们在8价格出，打算出售股票，可是9号价格更高，所以我们的利润还要加上9-8，但是在更新的时候还要减去fee,这就是多减去了一个fee,所以我们更新最小值的时候要再减去一个fee，为了下次少减去一个fee】 给定一个二叉树，我们在树的节点上安装摄像头。 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。 计算监控树的所有节点所需的最小摄像头数量。 示例 1： 输入：[0,0,null,0,0] 输入：[0,0,null,0,null,0,null,null,0] 提示： 给定树的节点数的范围是 [1, 1000]。 思路：本题的关键问题就是二叉树的遍历以及如果隔两个节点放摄像头。我们可以采用后序遍历，因为，如果我们重上往下遍历之后省了一个摄像头，而重下往上可以省指数数量的摄像头。 我们发现一个节点只有3种状态：有覆盖2，有摄像头1，无覆盖0。于是我们开始遍历二叉树，分4种情况 第一：遇到null返回2有覆盖，这样我们就可省下摄像头，把摄像头安装在叶子节点的父节点上。 第二：如果有一个左右节点为无覆盖，那么他的父节点一定是摄像头，这里面包括很多情况，比如左无覆盖，右摄像头，左无覆盖，右有覆盖，左右都无覆盖等等 第三：左右都有覆盖 返回 0，上面的节点就无覆盖 第四：左右有一个有摄像机，那么返回2，有覆盖 最后：检查头节点有无覆盖class Solution {
public:
int jump(vector
输出：5
解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。
示例 2：
输出：6
解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。
示例 3：
输出：13
解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。
1 <= K <= 10000
-100 <= A[i] <= 100class Solution {
private:
static bool cmp(const int a,const int b){
return abs(a)>abs(b);
}
public:
int largestSumAfterKNegations(vector
Leetcode.134.加油站
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。
示例 1:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
示例 2:
gas = [2,3,4]
cost = [3,4,3]
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。class Solution {
public:
int canCompleteCircuit(vectorclass Solution {
public:
bool lemonadeChange(vector
Leetcode.135.分发糖果
class Solution {
public:
int candy(vector
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
示例 2：
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]class Solution {
private:
static bool cmp(const vector
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
示例 2：
输出：4
示例 3：
输出：2
示例 4：
输出：1
示例 5：
输出：1
points[i].length == 2
-231 <= xstart < xend <= 231 - 1class Solution {
private:
static bool cmp(const vector
Leetcode.435.无重复区间
class Solution {
public:
// 按照区间右边界排序
static bool cmp (const vector
class Solution {
public:
// 按照区间右边界排序
static bool cmp (const vector
Leetcode.763.划分字母区间
class Solution {
public:
vector
Leetcode.56.合并区间
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
intervals[i].length == 2
0 <= starti <= endi <= 104class Solution {
public:
vector
Leetcode.738.单调递增的数字
输出: 9
示例 2:
输出: 1234
示例 3:
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。class Solution {
public:
int monotoneIncreasingDigits(int n) {
string str=to_string(n);
int flag=str.size();//设置将数字转化为9的起始点，同时防止本来是递增数字，而不需要修改字符的情况
for(int i=str.size()-1;i>0;i--){
if(str[i-1]>str[i]){
flag=i;
str[i-1]--;
}
}
for(int i=flag;iclass Solution {
public:
int maxProfit(vector
Leetcode.968.监控二叉树
输出：1
解释：如图所示，一台摄像头足以监控所有节点。
示例 2：
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
每个节点的值都是 0。class Solution {
private:
int res;
int trval(TreeNode* cur){
if(cur==NULL){
return 2;
}
int right=trval(cur->right);
int left=trval(cur->left);
if(right==0||left==0){
res++;
return 1;
}
if(right==1||left==1)return 2;
if(right==2&&left==2)return 0;
return -1;
}
public:
int minCameraCover(TreeNode* root) {
res=0;
if(trval(root)==0){
res++;
}
return res;
}
};
