贪心算法总结篇

川长思鸟来 2023-10-16 15:43 13阅读 0赞

#### 贪心算法总结篇 ####

*  简单题
 *  中等题
 *   *  贪心解决股票问题
     *  两个维度权衡问题
 *  难题
 *   *  贪心解决区间问题
     *  其他难题
 *  总结

## 简单题 ##

以下三道题目就是简单题，大家会发现贪心感觉就是常识。是的，如下三道题目，就是靠常识，但我都具体分析了局部最优是什么，全局最优是什么，贪心也要贪的有理有据！

*  贪心算法：分发饼干
 *  贪心算法：K次取反后最大化的数组和
 *  贪心算法：柠檬水找零

## 中等题 ##

贪心中等题，靠常识可能就有点想不出来了。开始初现贪心算法的难度与巧妙之处。

*  贪心算法：摆动序列
 *  贪心算法：单调递增的数字

### 贪心解决股票问题 ###

大家都知道股票系列问题是动规的专长，其实用贪心也可以解决，而且还不止就这两道题目，但这两道比较典型，我就拿来单独说一说:

*  贪心算法：买卖股票的最佳时机II
 *  贪心算法：买卖股票的最佳时机含手续费 本题使用贪心算法比较绕，建议后面学习动态规划章节的时候，理解动规就好

### 两个维度权衡问题 ###

在出现两个维度相互影响的情况时，两边一起考虑一定会顾此失彼，要先确定一个维度，再确定另一个一个维度。

*  贪心算法：分发糖果
 *  贪心算法：根据身高重建队列

## 难题 ##

这里的题目如果没有接触过，其实是很难想到的，甚至接触过，也一时想不出来，所以题目不要做一遍，要多练！

### 贪心解决区间问题 ###

关于区间问题，大家应该印象深刻，有一周我们专门讲解的区间问题，各种覆盖各种去重。

*  贪心算法：跳跃游戏
 *  贪心算法：跳跃游戏II
 *  贪心算法：用最少数量的箭引爆气球
 *  贪心算法：无重叠区间
 *  贪心算法：划分字母区间
 *  贪心算法：合并区间

### 其他难题 ###

**贪心算法：最大子序和**其实是动态规划的题目，但贪心性能更优，很多同学也是第一次发现贪心能比动规更优的题目。

**贪心算法：加油站**可能以为是一道模拟题，但就算模拟其实也不简单，需要把while用的很娴熟。但其实是可以使用贪心给时间复杂度降低一个数量级。

最后贪心系列压轴题目\*\*贪心算法：我要监控二叉树！\*\*不仅贪心的思路不好想，而且需要对二叉树的操作特别娴熟，这就是典型的交叉类难题了。

## 总结 ##

![在这里插入图片描述][4cf18b1733ad4a48be26640b59b45643.png]  
**参考资料**：[代码随想录-贪心算法总结篇][-]

[4cf18b1733ad4a48be26640b59b45643.png]: https://img-blog.csdnimg.cn/4cf18b1733ad4a48be26640b59b45643.png
[-]: https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E7%AF%87.html#%E8%B4%AA%E5%BF%83%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80

发表评论取消回复

表情：

评论列表（有 0 条评论，13人围观）

还没有评论，来说两句吧...

相关阅读

相关算法-贪心算法

1、分糖果问题 public int candy (int[] arr) { int n = arr.length;

柔光的暖阳◎/ 2024年03月24日 21:14/ 0 赞/ 78 阅读

相关贪心算法——知识点总结

贪心算法一、基本概念：所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的

ゝ一世哀愁。/ 2023年10月17日 13:26/ 0 赞/ 13 阅读

相关贪心算法总结篇

贪心算法总结篇简单题中等题贪心解决股票问题两个维度权衡问题难题贪心解决区间问题其他难题

川长思鸟来/ 2023年10月16日 15:43/ 0 赞/ 14 阅读

相关贪心类算法总结

例题：输入描述：有多组测试数据。第一行输入两个非负整数x 和n。接下来n 行，每行输入两个整数，分别为mi 和wi。所有数据都不大于1000。

骑猪看日落/ 2023年07月24日 02:38/ 0 赞/ 11 阅读

相关总结贪心算法_本周小结！（贪心算法系列二）

> ❝ > > 通知：一些录友表示经常看不到每天的文章，现在公众号已经不按照发送时间推荐了，而是根据一些规则乱序推送，所以可能关注了「代码随想录」也一直看不到文章，建议把「代

水深无声/ 2023年01月06日 01:39/ 0 赞/ 117 阅读

相关面试算法大全-贪心算法总结

11、贪心 11.1 贪心算法总结贪心算法是指在每个阶段做选择的时候都做出当前阶段（或状态）最好的选择，并且期望这样做到的结果是全局最优解（但未必是全局最优

喜欢ヅ旅行/ 2022年10月17日 13:51/ 0 赞/ 194 阅读

相关贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。举一个简单的贪心法例子，平时

本是古典何须时尚/ 2022年06月06日 03:11/ 0 赞/ 303 阅读

相关贪心算法总结

希望为读者了解贪心起到帮助，在(二)中典型的贪心问题务必自己百度学习！（一）贪心算法特点：（1）设计要素： 1）.贪心法适用于组合优化问题 2）.求解

缺乏、安全感/ 2022年02月27日 15:54/ 0 赞/ 255 阅读

相关贪心算法

1.钞票支付问题，1元，2元，5元，10元，20元，50元，100元钞票无穷张，使用这些钞票怎么支付，最少需要多少张。思路：尽可能使用面额较大的金额数目。反证法：若不成立，

深碍√TFBOYSˉ_/ 2022年02月22日 08:49/ 0 赞/ 309 阅读

相关贪心算法

贪心算法概念设计贪心算法的步骤案例剪绳子问题描述解决思路代码实

我就是我/ 2021年11月04日 13:48/ 0 赞/ 457 阅读