基于阅读高畅大佬的《LeetCode 101：和你一起你轻松刷题（C++）》做的笔记
算法解释
贪心算法或贪心思想采用贪心的策略，保证每次操作都是局部最优的，从而使最 后得到的结果是全局最优的。
1、分配问题
1）455. Assign Cookies（Easy）
思路：
给最容易饱的孩子分配最小能饱腹的饼干。
题解：
给孩子和饼干进行排序，然后根据孩子分配饼干。
代码：
intfindContentChildren(vector<int>&children,vector<int>&cookies) {
sort(children.begin(),children.end());
sort(cookies.begin(),cookies.end());
intchild=0,cookie=0;
while(child<children.size()&&cookie<cookies.size()) {
if(children[child]<=cookies[cookie])++child;
++cookie;
}
returnchild;
}
2 ）135. Candy（Hard）
思路：
把所有孩子的糖果数初始化为 1； 先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的 糖果数加 1；再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数 不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加 1。
题解：
只考虑并更新相邻一 侧的大小关系
代码：
int candy(vector<int>& ratings) {
int size = ratings.size();
if (size < 2) {
return size;
}
vector 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 可以很方便
地求和
}
2、区间问题
1）435.Non-overlapping Intervals（Medium）
思路：
优先保留结尾小且不相交的区间。
题解：
先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选择的区间不重叠的区间。
代码：
int eraseOverlapIntervals(vector>& intervals){
if (intervals.empty()) {return 0;}
int n = intervals.size();
sort(intervals.begin(), intervals.end(), [](vectora, vector b) {
return a[1] < b[1];
});
int total = 0, prev = intervals[0][1];
for (int i = 1; i < n; ++i) {
if (intervals[i][0] < prev) {
++total;
} else {
prev = intervals[i][1];
}
}
return total;
}
