我要评论贪心算法笔记
一、算法简介
（一）特性
贪心算法顾名思义就是每一次做选择时贪婪地选择当前最优解的算法，它的本质就是将问题划分成多个子选择问题，在每一次选择中选择局部最优解，从而达到“全局最优解”。显然，局部最优并不永远等于全局最优，所以贪心算法并不是一种完备的算法（不一定能够找到全局最优解）。
（二）应用领域
- 序列问题
- 股票问题
- 两个维度权衡问题
- 区间问题
（三）基本步骤
- 将原问题拆解成多个子问题
- 制定合适的价值选择标准（选择何种参数作为评判“最优”的标准）
- 逐个求解每一个子问题的局部最优解
- 将局部最优解累积成全局最优解
二、简单的贪心算法问题
（一）分发饼干
455.分发饼干（leetcode）
题目要求：
示例：
提示：
解题思路：
根据题意，有以下要点：
- 每一次分发饼干都要求饼干的尺寸大于等于小孩的胃口
- 大饼干既可以分给胃口大的孩子，也可以分给胃口小的孩子，小饼干只能分给胃口小的孩子
- 如果把大饼干分给胃口小的孩子，剩下的小饼干不能分给胃口大的孩子就会造成浪费
- 所以尽量将大饼干给胃口大的孩子，把小饼干分给胃口小的孩子才能尽可能充分地利用所有饼干，实现满足人数最大化
为了尽可能将大饼干分给胃口大的孩子，需要先将饼干数组和孩子数组进行排序，然后从后往前遍历孩子数组，把手中最大的饼干分给胃口最大且小于饼干尺寸的孩子。该算法只需要遍历一次孩子数组，时间复杂度为o(n)。
代码示例：
class solution {
public:
int findcontentchildren(vector<int>& g, vector<int>& s) {
if(s.size() == 0) return 0;
sort(g.begin(), g.end());
sort(s.begin(), s.end());
// 优先分配大的饼干给胃口大的孩子
int cookie = s.size() - 1;
for(int i = g.size() - 1; i >= 0; i--) {
if(cookie < 0) return s.size();
if(g[i] <= s[cookie]) {
cookie--;
}
}
return s.size() - cookie - 1;
}
};
（二）最大子数组的和
53.最大子数组和（leetcode）
题目要求：
示例：
提示：
解题思路：
根据题意，有以下要点：
- 求子数组的最大和
- 子数组是原数组中的连续元素序列
看到求连续子序列的和，第一时间想到双指针暴力算法，但使用双指针调节子序列区间需要用到两重for循环，时间复杂度为o(n2)，题目中有一个特别大的用例，两层for循环很容易超时。
在本题中贪心算法的“贪心”体现在如何及时更改子数组的左边界上。为了实现最大子列和，需要进行sum += nums[i] 的操作，当sum小于0时，与其加上以前的序列还不如直接重新开始，贪婪地舍弃以往的记录重新开始也是贪心算法的体现。利用这种方法并不会妨碍sum取到最大值，因为这实际上是一种剪枝操作，剪去和为负数的子序列只是剪去了永远不可能成为答案的子序列。我们只需要建立一个变量记录sum取到的最大值即可。
代码示例：
class solution {
public:
int maxsubarray(vector<int>& nums) {
int sum = 0;
// 注意要进行比较取值操作，初始化为最小值以免初值大于正确结果影响正确结果的记录
int res = int_min;
for(int i = 0; i < nums.size(); i++) {
if(sum < 0)
sum = nums[i];
else
sum += nums[i];
res = sum > res ? sum : res;
}
return res;
}
};
（三）摆动序列
376.摆动序列（leetcode）
题目要求：
示例：
提示：
解题思路：
根据题意，可以提炼出以下要点：
（重要！！！）子序列可以从原序列中删除一些元素得到，这说明两点：
- 子序列中的元素在原数组中可以不相邻
- 子序列中的元素的相对位置必须和原数组中保持一致
注意到本题可以通过删除特定节点扩大所求子集的大小，由于题目只求子序列的最大长度，实际上我们并不需要真的进行删除操作，只需要跳过不符合要求的节点，不将它们记入总数中即可（不对它们进行操作，相当于剪除）。为了判断本轮差值是否合规，需要创建一个变量记录上一次有效摆动是上升还是下降，再比较两者的符号
- 如果符号相反说明是有效摆动，将子串长加一（相当一将该节点加入子串）
- 如果相同说明不是有效摆动，不对本节点做任何操作，继续搜索下一个元素
在捋清整体思路以后还需要注意两个细节：
细节一：跳过操作需要考虑哪些情况？不同情况的解决办法是否相通？
跳过操作看似简单，其实需要考虑多种情况：
- case 1 平顶（平底）:[1, 2, 2, 2, 1] 这种情况下，我们不需要记录连续相等元素m的前一个元素x，因为相等的元素会将x与自己的相对大小关系通过自身的相等关系传递到下一个不同值的元素y处（在编程中，我们通过不修改 prevdiff 来实现保留）。当 m > x 且 m > y 时 m 构成高峰，x,y 构成谷底，一共计数3次即可
- case 2 连续上升（下降）:[1, 2, 3, 1] 这种情况看似有所变化实际上和第一种是一样的，递增（递减）的元素会将x与自己的相对大小关系通过不等式的传递性传递到下一个不同值的元素y处（在编程中，我们通过不修改 prevdiff 来实现保留）
- case 3 相等后继续上升（下降）:[1, 2, 2, 3, 1] 这是情况一和情况二的结合，首先按照情况一的方法剪去重复元素，数组变为[1, 2, 3, 1]，然后按照情况二的方法删去连续递增元素3，得到[1, 2, 1]
由此，我们可以看出虽然情况很多，但解决办法是相同的，确保检查到违规情况以后跳过不修改参数即可。
细节二：prevdiff的正负记录了上一轮合规元素比较的结果，那么它的起始状态是什么？
我们希望在初始时不考虑前一个元素与当前元素的差值。初始化为0可以确保在处理第一个元素时，不会意外地将其判断为连续递增或连续递减，导致第一个元素被剪除。
此外，初始化为0和其余部分的处理逻辑相吻合，可以避免为其制定额外的条件逻辑。我们在处理差值时，根据符号的改变来判断是否要增加 maxlength。具体地说，如果差值 diff 为正，且 prevdiff 为负或零，或者如果差值 diff 为负，且 prevdiff 为正或零，那么说明出现了摆动，此时应增加 maxlength。这种差值的符号改变是摆动子序列的关键标志。在这个过程中 prevdiff 初始化为 0 恰好可以保证第一个元素不被剪除。
代码示例：
class solution {
public:
int wigglemaxlength(vector<int>& nums) {
if (nums.size() < 2) {
return nums.size();
}
int maxlength = 1;
int prevdiff = 0; // 用于跟踪前一个元素与当前元素的差值
for (int i = 1; i < nums.size(); i++) {
int diff = nums[i] - nums[i - 1];
if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
maxlength++;
prevdiff = diff;
}
}
return maxlength;
}
};
发表评论