南宁网站建设技术支持,白蛇传奇网页版游戏,河北建设信息平台网站,网站不收录贪心算法理论基础 关于贪心算法#xff0c;你该了解这些#xff01;
题目分类大纲如下#xff1a; # 什么是贪心
贪心的本质是选择每一阶段的局部最优#xff0c;从而达到全局最优。
这么说有点抽象#xff0c;来举一个例子#xff1a;
例如#xff0c;有一堆钞票你该了解这些
题目分类大纲如下 # 什么是贪心
贪心的本质是选择每一阶段的局部最优从而达到全局最优。
这么说有点抽象来举一个例子
例如有一堆钞票你可以拿走十张如果想达到最大的金额你要怎么拿
指定每次拿最大的最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优最后拿走最大数额的钱就是推出全局最优。
再举一个例子如果是 有一堆盒子你有一个背包体积为n如何把背包尽可能装满如果还每次选最大的盒子就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。
# 贪心的套路什么时候用贪心
很多同学做贪心的题目的时候想不出来是贪心想知道有没有什么套路可以一看就看出来是贪心。
说实话贪心算法并没有固定的套路。
所以唯一的难点就是如何通过局部最优推出整体最优。
那么如何能看出局部最优是否能推出整体最优呢有没有什么固定策略或者套路呢
不好意思也没有 靠自己手动模拟如果模拟可行就可以试一试贪心策略如果不可行可能需要动态规划。
有同学问了如何验证可不可以用贪心算法呢
最好用的策略就是举反例如果想不到反例那么就试一试贪心吧。
可有有同学认为手动模拟举例子得出的结论不靠谱想要严格的数学证明。
一般数学证明有如下两种方法
数学归纳法反证法
看教课书上讲解贪心可以是一堆公式估计大家连看都不想看所以数学证明就不在我要讲解的范围内了大家感兴趣可以自行查找资料。
面试中基本不会让面试者现场证明贪心的合理性代码写出来跑过测试用例即可或者自己能自圆其说理由就行了。
举一个不太恰当的例子我要用一下11 2但我要先证明11 为什么等于2。严谨是严谨了但没必要。
虽然这个例子很极端但可以表达这么个意思刷题或者面试的时候手动模拟一下感觉可以局部最优推出整体最优而且想不到反例那么就试一试贪心。
例如刚刚举的拿钞票的例子就是模拟一下每次拿做大的最后就能拿到最多的钱这还要数学证明的话其实就不在算法面试的范围内了可以看看专业的数学书籍
所以这也是为什么很多同学通过accept了贪心的题目但都不知道自己用了贪心算法因为贪心有时候就是常识性的推导所以会认为本应该就这么做
那么刷题的时候什么时候真的需要数学推导呢
例如这道题目链表环找到了那入口呢
(opens new window)这道题不用数学推导一下就找不出环的起始位置想试一下就不知道怎么试这种题目确实需要数学简单推导一下。
# 贪心一般解题步骤
贪心算法一般分为如下四步
将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解
这个四步其实过于理论化了我们平时在做贪心类的题目 很难去按照这四步去思考真是有点“鸡肋”。
做题的时候只要想清楚 局部最优 是什么如果推导出全局最优其实就够了。
# 总结
本篇给出了什么是贪心以及大家关心的贪心算法固定套路。
不好意思了贪心没有套路说白了就是常识性推导加上举反例。
最后给出贪心的一般解题步骤大家可以发现这个解题步骤也是比较抽象的不像是二叉树回溯算法给出了那么具体的解题套路和模板。 一、力扣第455题分发饼干
题目:
假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。
对每个孩子 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 g.length 3 * 1040 s.length 3 * 1041 g[i], s[j] 231 - 1
思路
为了满足更多的小孩就不要造成饼干尺寸的浪费。
大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子那么就应该优先满足胃口大的。
这里的局部最优就是大饼干喂给胃口大的充分利用饼干尺寸喂饱一个全局最优就是喂饱尽可能多的小孩。
可以尝试使用贪心策略先将饼干数组和小孩数组排序。
然后从后向前遍历小孩数组用大饼干优先满足胃口大的并统计满足小孩数量。
如图 这个例子可以看出饼干 9 只有喂给胃口为 7 的小孩这样才是整体最优解并想不出反例那么就可以撸代码了。
C代码整体如下
// 版本一
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int index s.size() - 1; // 饼干数组的下标int result 0;for (int i g.size() - 1; i 0; i--) { // 遍历胃口if (index 0 s[index] g[i]) { // 遍历饼干result;index--;}}return result;}
};时间复杂度O(nlogn)空间复杂度O(1)
从代码中可以看出我用了一个 index 来控制饼干数组的遍历遍历饼干并没有再起一个 for 循环而是采用自减的方式这也是常用的技巧。
有的同学看到要遍历两个数组就想到用两个 for 循环那样逻辑其实就复杂了。
# 注意事项
注意版本一的代码中可以看出来是先遍历的胃口在遍历的饼干那么可不可以 先遍历 饼干在遍历胃口呢
其实是不可以的。
外面的 for 是里的下标 i 是固定移动的而 if 里面的下标 index 是符合条件才移动的。
如果 for 控制的是饼干 if 控制胃口就是出现如下情况 if 里的 index 指向 胃口 10 for 里的 i 指向饼干 9因为 饼干 9 满足不了 胃口 10所以 i 持续向前移动而 index 走不到s[index] g[i] 的逻辑所以 index 不会移动那么当 i 持续向前移动最后所有的饼干都匹配不上。
所以 一定要 for 控制 胃口里面的 if 控制饼干。
# 其他思路
也可以换一个思路小饼干先喂饱小胃口
代码如下
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int index 0;for(int i 0; i s.size(); i) { // 饼干if(index g.size() g[index] s[i]){ // 胃口index;}}return index;}
};时间复杂度O(nlogn)空间复杂度O(1)
细心的录友可以发现这种写法两个循环的顺序改变了先遍历的饼干在遍历的胃口这是因为遍历顺序变了我们是从小到大遍历。
理由在上面 “注意事项”中 已经讲过。
# 总结
这道题是贪心很好的一道入门题目思路还是比较容易想到的。
文中详细介绍了思考的过程想清楚局部最优想清楚全局最优感觉局部最优是可以推出全局最优并想不出反例那么就试一试贪心。 二、力扣第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 10000 nums[i] 1000 进阶你能否用 O(n) 时间复杂度完成此题?
思路
# 思路 1贪心解法
本题要求通过从原始序列中删除一些也可以不删除元素来获得子序列剩下的元素保持其原始顺序。
相信这么一说吓退不少同学这要求最大摆动序列又可以修改数组这得如何修改呢
来分析一下要求删除元素使其达到最大摆动序列应该删除什么元素呢
用示例二来举例如图所示 局部最优删除单调坡度上的节点不包括单调坡度两端的节点那么这个坡度就可以有两个局部峰值。
整体最优整个序列有最多的局部峰值从而达到最长摆动序列。
局部最优推出全局最优并举不出反例那么试试贪心
为方便表述以下说的峰值都是指局部峰值
实际操作上其实连删除的操作都不用做因为题目要求的是最长摆动子序列的长度所以只需要统计数组的峰值数量就可以了相当于是删除单一坡度上的节点然后统计长度
这就是贪心所贪的地方让峰值尽可能的保持峰值然后删除单一坡度上的节点
在计算是否有峰值的时候大家知道遍历的下标 i 计算 prediffnums[i] - nums[i-1] 和 curdiffnums[i1] - nums[i]如果prediff 0 curdiff 0 或者 prediff 0 curdiff 0 此时就有波动就需要统计。
这是我们思考本题的一个大题思路但本题要考虑三种情况
情况一上下坡中有平坡情况二数组首尾两端情况三单调坡中有平坡
# 情况一上下坡中有平坡
例如 [1,2,2,2,1]这样的数组如图 它的摇摆序列长度是多少呢 其实是长度是 3也就是我们在删除的时候 要不删除左面的三个 2要不就删除右边的三个 2。
如图可以统一规则删除左边的三个 2 在图中当 i 指向第一个 2 的时候prediff 0 curdiff 0 当 i 指向最后一个 2 的时候 prediff 0 curdiff 0。
如果我们采用删左面三个 2 的规则那么 当 prediff 0 curdiff 0 也要记录一个峰值因为他是把之前相同的元素都删掉留下的峰值。
所以我们记录峰值的条件应该是 (preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)为什么这里允许 prediff 0 就是为了 上面我说的这种情况。
# 情况二数组首尾两端
所以本题统计峰值的时候数组最左面和最右面如何统计呢
题目中说了如果只有两个不同的元素那摆动序列也是 2。
例如序列[2,5]如果靠统计差值来计算峰值个数就需要考虑数组最左面和最右面的特殊情况。
因为我们在计算 prediffnums[i] - nums[i-1] 和 curdiffnums[i1] - nums[i]的时候至少需要三个数字才能计算而数组只有两个数字。
这里我们可以写死就是 如果只有两个元素且元素不同那么结果为 2。
不写死的话如何和我们的判断规则结合在一起呢
可以假设数组最前面还有一个数字那这个数字应该是什么呢
之前我们在 讨论 情况一相同数字连续 的时候 prediff 0 curdiff 0 或者 0 也记为波谷。
那么为了规则统一针对序列[2,5]可以假设为[2,2,5]这样它就有坡度了即 preDiff 0如图 针对以上情形result 初始为 1默认最右面有一个峰值此时 curDiff 0 preDiff 0那么 result计算了左面的峰值最后得到的 result 就是 2峰值个数为 2 即摆动序列长度为 2
经过以上分析后我们可以写出如下代码
// 版本一
class Solution {
public:int wiggleMaxLength(vectorint nums) {if (nums.size() 1) return nums.size();int curDiff 0; // 当前一对差值int preDiff 0; // 前一对差值int result 1; // 记录峰值个数序列默认序列最右边有一个峰值for (int i 0; i nums.size() - 1; i) {curDiff nums[i 1] - nums[i];// 出现峰值if ((preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)) {result;}preDiff curDiff;}return result;}
};时间复杂度O(n)空间复杂度O(1)
此时大家是不是发现 以上代码提交也不能通过本题
所以此时我们要讨论情况三
# 情况三单调坡度有平坡
在版本一中我们忽略了一种情况即 如果在一个单调坡度上有平坡例如[1,2,2,2,3,4]如图 图中我们可以看出版本一的代码在三个地方记录峰值但其实结果因为是 2因为 单调中的平坡 不能算峰值即摆动。
之所以版本一会出问题是因为我们实时更新了 prediff。
那么我们应该什么时候更新 prediff 呢
我们只需要在 这个坡度 摆动变化的时候更新 prediff 就行这样 prediff 在 单调区间有平坡的时候 就不会发生变化造成我们的误判。
所以本题的最终代码为 // 版本二
class Solution {
public:int wiggleMaxLength(vectorint nums) {if (nums.size() 1) return nums.size();int curDiff 0; // 当前一对差值int preDiff 0; // 前一对差值int result 1; // 记录峰值个数序列默认序列最右边有一个峰值for (int i 0; i nums.size() - 1; i) {curDiff nums[i 1] - nums[i];// 出现峰值if ((preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)) {result;preDiff curDiff; // 注意这里只在摆动变化的时候更新prediff}}return result;}
};其实本题看起来好像简单但需要考虑的情况还是很复杂的而且很难一次性想到位。
本题异常情况的本质就是要考虑平坡 平坡分两种一个是 上下中间有平坡一个是单调有平坡如图 # 思路 2动态规划
考虑用动态规划的思想来解决这个问题。
很容易可以发现对于我们当前考虑的这个数要么是作为山峰即 nums[i] nums[i-1]要么是作为山谷即 nums[i] nums[i - 1]。
设 dp 状态dp[i][0]表示考虑前 i 个数第 i 个数作为山峰的摆动子序列的最长长度设 dp 状态dp[i][1]表示考虑前 i 个数第 i 个数作为山谷的摆动子序列的最长长度
则转移方程为
dp[i][0] max(dp[i][0], dp[j][1] 1)其中0 j i且nums[j] nums[i]表示将 nums[i]接到前面某个山谷后面作为山峰。dp[i][1] max(dp[i][1], dp[j][0] 1)其中0 j i且nums[j] nums[i]表示将 nums[i]接到前面某个山峰后面作为山谷。
初始状态
由于一个数可以接到前面的某个数后面也可以以自身为子序列的起点所以初始状态为dp[0][0] dp[0][1] 1。
C代码如下
class Solution {
public:int dp[1005][2];int wiggleMaxLength(vectorint nums) {memset(dp, 0, sizeof dp);dp[0][0] dp[0][1] 1;for (int i 1; i nums.size(); i) {dp[i][0] dp[i][1] 1;for (int j 0; j i; j) {if (nums[j] nums[i]) dp[i][1] max(dp[i][1], dp[j][0] 1);}for (int j 0; j i; j) {if (nums[j] nums[i]) dp[i][0] max(dp[i][0], dp[j][1] 1);}}return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);}
};时间复杂度O(n^2)空间复杂度O(n)
进阶
可以用两棵线段树来维护区间的最大值
每次更新dp[i][0]则在tree1的nums[i]位置值更新为dp[i][0]每次更新dp[i][1]则在tree2的nums[i]位置值更新为dp[i][1]则 dp 转移方程中就没有必要 j 从 0 遍历到 i-1可以直接在线段树中查询指定区间的值即可。
时间复杂度O(nlog n)
空间复杂度O(n)
三、力扣第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 [5,4,-1,7,8]
输出23提示
1 nums.length 105-104 nums[i] 104 进阶如果你已经实现复杂度为 O(n) 的解法尝试使用更为精妙的 分治法 求解。
暴力解法
暴力解法的思路第一层 for 就是设置起始位置第二层 for 循环遍历数组寻找最大值
class Solution {
public:int maxSubArray(vectorint 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;}
};时间复杂度O(n^2)空间复杂度O(1)
以上暴力的解法 C勉强可以过其他语言就不确定了。
# 贪心解法
贪心贪的是哪里呢
如果 -2 1 在一起计算起点的时候一定是从 1 开始计算因为负数只会拉低总和这就是贪心贪的地方
局部最优当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和”因为负数加上下一个元素 “连续和”只会越来越小。
全局最优选取最大“连续和”
局部最优的情况下并记录最大的“连续和”可以推出全局最优。
从代码角度上来讲遍历 nums从头开始用 count 累积如果 count 一旦加上 nums[i]变为负数那么就应该从 nums[i1]开始从 0 累积 count 了因为已经变为负数的 count只会拖累总和。
这相当于是暴力解法中的不断调整最大子序和区间的起始位置。
那有同学问了区间终止位置不用调整么 如何才能得到最大“连续和”呢
区间的终止位置其实就是如果 count 取到最大值了及时记录下来了。例如如下代码
if (count result) result count;这样相当于是用 result 记录最大子序和区间和变相的算是调整了终止位置。
如动画所示 红色的起始位置就是贪心每次取 count 为正数的时候开始一个区间的统计。
那么不难写出如下 C代码关键地方已经注释
class Solution {
public:int maxSubArray(vectorint nums) {int result INT32_MIN;int count 0;for (int i 0; i nums.size(); i) {count nums[i];if (count result) { // 取区间累计的最大值相当于不断确定最大子序终止位置result count;}if (count 0) count 0; // 相当于重置最大子序起始位置因为遇到负数一定是拉低总和}return result;}
};时间复杂度O(n)空间复杂度O(1)
当然题目没有说如果数组为空应该返回什么所以数组为空的话返回啥都可以了。
# 常见误区
误区一
不少同学认为 如果输入用例都是-1或者 都是负数这个贪心算法跑出来的结果是 0 这是又一次证明脑洞模拟不靠谱的经典案例建议大家把代码运行一下试一试就知道了也会理解 为什么 result 要初始化为最小负数了。
误区二
大家在使用贪心算法求解本题经常陷入的误区就是分不清是遇到 负数就选择起始位置还是连续和为负选择起始位置。
在动画演示用大家可以发现 4遇到 -1 的时候我们依然累加了为什么呢
因为和为 3只要连续和还是正数就会 对后面的元素 起到增大总和的作用。 所以只要连续和为正数我们就保留。
这里也会有录友疑惑那 4 -1 之后 不就变小了吗 会不会错过 4 成为最大连续和的可能性
其实并不会因为还有一个变量 result 一直在更新 最大的连续和只要有更大的连续和出现result 就更新了那么 result 已经把 4 更新了后面 连续和变成 3也不会对最后结果有影响。
# 动态规划
当然本题还可以用动态规划来做在代码随想录动态规划章节我会详细介绍如果大家想在想看可以直接跳转动态规划版本详解
(opens new window)
那么先给出我的 dp 代码如下有时间的录友可以提前做一做
class Solution {
public:int maxSubArray(vectorint nums) {if (nums.size() 0) return 0;vectorint dp(nums.size(), 0); // dp[i]表示包括i之前的最大连续子序列和dp[0] nums[0];int result dp[0];for (int i 1; i nums.size(); i) {dp[i] max(dp[i - 1] nums[i], nums[i]); // 状态转移公式if (dp[i] result) result dp[i]; // result 保存dp[i]的最大值}return result;}
};时间复杂度O(n)空间复杂度O(n)
# 总结
本题的贪心思路其实并不好想这也进一步验证了别看贪心理论很直白有时候看似是常识但贪心的题目一点都不简单
后续将介绍的贪心题目都挺难的所以贪心很有意思别小看贪心
day31补
