算法解释：
贪心算法的策略是：保证每一次的操作都是局部最优的，从而使得最后得到的结果是全局最优的。
例如：A和B喜欢吃苹果，A可以吃5个，B可以吃3个，一直苹果不限量，那么求两人一共最多吃多少个苹果，这个显而易见，5+3，这就是局部最优导致的整体最优，这就是贪心的策略。
分配问题：
难度简单
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 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.
复制代码AC代码：
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int g1 =0 ,s1 =0;
while(g1<g.size()&&s1<s.size()){
if(g[g1]<=s[s1]) g1++;
s1++;
}
return g1;
}
};
复制代码思路：
首先，我们已知孩子的个数和需要的食物，还有每个食物的大小，以及每一个孩子只能吃一个食物。那么我们为了让更多的孩子吃饱，那么肯定不能从吃的多的孩子开始喂食物，那么我们要从吃的最少的孩子开始喂。而一直我们从吃的最少的孩子开始喂，那么肯定不能一开始就喂吃的少的孩子比较大的食物，所以要从食物的最小块来与最小饥饿度的孩子进行对比，这样才能使最多孩子吃饱。
难度困难
老师想给孩子们分发糖果，有
N
个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
- 每个孩子至少分配到 1 个糖果。
- 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
示例 1：
输入：[1,0,2]
输出：5
解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。
复制代码示例 2：
输入：[1,2,2]
输出：4
解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
复制代码AC代码:
class Solution {
public:
int candy(vector<int>& ratings) {
int size=ratings.size();
if(size<2){
return size;
}
vector<int> num(size,1);
for(int i=1;i<size;i++){
if(ratings[i]>ratings[i-1]){
num[i]=num[i-1]+1;
}
}
for(int i=size-1;i>0;i--){
if(ratings[i]<ratings[i-1]){
num[i-1]=max(num[i]+1,num[i-1]);
}
}
return accumulate(num.begin(), num.end(), 0); // std::accumulate 可以很方便 地求和
}
};
复制代码思路：
已知每一个孩子最少发一个糖果，所以给每一个孩子一个糖果，再从左到右进行遍历，遍历完再从右到左，注意第二次遍历未开始时，由于第一次遍历，每个孩子的糖果数可能差距较大，所以，不能再简单的用num[i]=num[i-1]+1;，我们要用max得出比较双方最大的数，如果两个数一样大，那么结果要+1。
PDD二面算法题
给你一个数组，其中数组中的每个值与相邻元素之间的差值是m，现在给你一个目标值k，找到数组中所有等于k的元素的索引，使用集合返回。
遍历的元素越少越好，无序
List fun(List list,int m,int k)
就比如[1,2,3,2,1,0,-1,0,1] m=1 k=3 返回[2] ，k一定是数组中的某个值
我写的参考代码：
class Solution {
public:
int getK(vector<int>& list,int m,int k) {
int index=0;
int len=list.size();
while(index<len){
int cur=list[index];
int step=Math.abs(cur-k)/m;
if(step==0){
return ++index;
}
else{
index+=step;
};
}
}
复制代码思路：首先这是大厂的算法题，我感觉考察的差不多就是贪心，不太懂是个啥，反正思路很清晰。
这个无序数组里面相邻元素之间相差为m，那么我们从第一个元素开始看起，只要当前元素减去目标元素不等于0就继续查找下去，这个代码是利用m来进行跳步，也就是index+=step；这样大大减少了遍历次数，符合面试官要求。
难度中等
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
- 可以认为区间的终点总是大于它的起点。
- 区间 [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
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
复制代码AC代码：
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return 0;
}
sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {
return u[1] < v[1];
});
int count=0,cur=intervals[0][1],size=intervals.size();
for(int i=1;i<size;++i){
if(intervals[i][0]<cur){
++count;
}
else{
cur=intervals[i][1];
}
}
return count;
}
};
复制代码思路：
这题很多大佬都是用动态规划，但是用贪心也还成。已知题目需要输出最少移除几个数组，所以我们从这里找到这题的贪心策略：将每个数组的第二个元素进行排序，然后依次对比相邻数组的第一个元素。
难度简单
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。
示例 1：
输入：flowerbed = [1,0,0,0,1], n = 1
输出：true
复制代码示例 2：
输入：flowerbed = [1,0,0,0,1], n = 2
输出：false
复制代码AC代码：
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
for(int i=0; i<flowerbed.size(); i++) {
if(flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] == 0) && (i == flowerbed.size()-1 || flowerbed[i+1] == 0)) {
n--;
if(n <= 0) return true;
flowerbed[i] = 1;
}
}
return n <= 0;
}
};
复制代码思路：
这题的贪心策略很简单，就是能种花就种花，而种花的条件就那么几个：自身为零且右边为零且在最左边，自身为零且左边为零且在最右边，自身为零且左右两边都为零，这样就能保证插最多的花了。
难度中等456
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end， 且满足 xstart ≤ x ≤ x``end，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
示例 1：
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
复制代码示例 2：
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
复制代码示例 3：
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
复制代码示例 4：
输入：points = [[1,2]]
输出：1
复制代码示例 5：
输入：points = [[2,3],[2,3]]
输出：1
复制代码AC代码：
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return 0;
}
sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {
return u[0] < v[0];
});
int count=1,size=intervals.size();
for(int i=1;i<size;++i){
if(intervals[i][0]<=intervals[i-1][1]){
intervals[i][1]=min(intervals[i-1][1],intervals[i][1]);
}
else{
++count;
}
}
return count;
}
};
复制代码思路：
这题的策略是以每个气球的起始位置来排序，再判断相邻气球的起始终止位置是否合适，一旦两个气球可以一起炸，那么这两个气球的终止位置要取最小值，再判断下一个气球是不是也能一起炸。
难度中等
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例：
输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
复制代码AC代码：
class Solution {
public:
vector<int> partitionLabels(string s) {
int map[26]={0},cur=0,pre=0;
vector<int> arr;
for(int i=0;i<s.size();i++){
map[s[i]-'a']=i;
}
for(int i=0;i<s.size();i++){
cur=max(cur,map[s[i]-'a']);
if(i==cur){
arr.push_back(cur-pre+1);
pre=cur+1;
}
}
return arr;
}
};
复制代码思路：
面对这种问题，我们对于每个字母的最后一次出现位置是最敏感的，因为如果不知道这个位置，那你这最小数组怎么找，所以顺其自然搜找每个字母的最后出现位置，再由第一个字母出发，组成一个闭合数组，利用pre和cur算出长度。
难度中等1355
给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
复制代码示例 2:
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
复制代码示例 3:
输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
复制代码AC代码：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int count=0;
for(int i=0;i<prices.size()-1;i++){
if(prices[i]<prices[i+1]){
count+=prices[i+1]-prices[i];
}
}
return count;
}
};
复制代码思路：
这种题细想不容易得结果，但是如果从贪心的角度看，为了获得最大的利润，我甚至可以每过一天都进行一次买入或者卖出，在价格下降的时候不进行操作，从而达到利润最大化。
难度中等
假设有打乱顺序的一群人站成一个队列，数组 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]]
输出：[[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：
输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
复制代码AC代码：
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
vector<vector<int>> arr;
sort(people.begin(), people.end(), [](const auto& u, const auto& v) {
if (u[0] == v[0]) return u[1] < v[1];
return u[0] > v[0];
});
for(int i=0;i<people.size();i++){
if(arr.size()<=people[i][1]) arr.push_back(people[i]);
else{
arr.insert(arr.begin() +people[i][1], people[i]);
}
}
return arr;
}
};
复制代码思路：
这题的贪心思想实在是，先对身高降序排序，身高相同的话第二个参数升序排序。这样的话，对于前面有几个比这个人高的人，我们可以有一个明确的判断，首先，我们先放高的，将第二个参数作为他们的索引，再让后面的人根据第二个参数往前插，为什么能这样做呢？因为当你后面的人进到这个二维数组中，你就会发现，每一个已经落座的人都比你高，所以这时你的第二个参数可以作为索引，让你直接插队。
难度中等608
给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。
示例 1:
输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
复制代码示例 2:
输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
复制代码AC代码：
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
if (nums.size() <= 1) {
return true;
}
int cnt = 0;
for (int i = 1; i < nums.size() && cnt < 2; i++) {
if (nums[i-1] <= nums[i]) {
continue;
}
cnt++;
if (i-2>=0 && nums[i-2] > nums[i]) {
nums[i] = nums[i-1];
}else {
nums[i-1] = nums[i];
}
}
return cnt <= 1;
}
};
复制代码思路：
这题难度较大，考虑情况较多，主要思想是：已知一个元素小于它的前一个元素，如果它的再前一个元素不存在的话，那么就使前一个元素等于这个元素，倘若再前一个元素存在，且这个元素大于本元素的话，那么使本元素等于前一个元素；如果再前一个元素小于本元素的话，使前一个元素等于本元素，就可以完美解决问题。
贪心算法看似简单，其实无固定套路，补充一张图，以后刷题还要再回来看一遍：
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
