当前位置： 首页 > news >正文

贪心算法总结篇

news 文章来源：https://blog.csdn.net/weixin_67972246/article/details/132591926 2025/4/30 9:40:39

文章转自代码随想录

贪心算法总结篇

我刚刚开始讲解贪心系列的时候就说了，贪心系列并不打算严格的从简单到困难这么个顺序来讲解。

因为贪心的简单题可能往往过于简单甚至感觉不到贪心，如果我连续几天讲解简单的贪心，估计录友们一定会不耐烦了，会感觉贪心有啥好学的。

但贪心的难题又真的有点难，所以我是简单困难交错着讲的，这样大家就感觉难度适中，而且贪心也没有什么框架和套路，所以对刷题顺序要求没有那么高。

但在贪心系列，我发的题目难度会整体呈现一个阶梯状上升，细心的录友们应该有所体会。

在刚刚讲过的回溯系列中，大家可以发现我是严格按照框架难度顺序循序渐进讲解的，和贪心又不一样，因为回溯法如果题目顺序没选好，刷题效果会非常差！

同样回溯系列也不允许简单困难交替着来，因为前后题目都是有因果关系的，相信跟着刷过回溯系列的录友们都会明白我的良苦用心，哈哈。

每个系列都有每个系列的特点，我都会根据特点有所调整，大家看我每天的推送的题目，都不是随便找一个到就推送的，都是先有整体规划，然后反复斟酌具体题目的结果。

那么在贪心总结篇里，我按难易程度以及题目类型大体归个类。

贪心大总结正式开始：

# 贪心理论基础

在贪心系列开篇词关于贪心算法，你该了解这些！

(opens new window)中，我们就讲解了大家对贪心的普遍疑惑。

  1. 贪心很简单，就是常识？

跟着一起刷题的录友们就会发现，贪心思路往往很巧妙，并不简单。

  1. 贪心有没有固定的套路？

贪心无套路，也没有框架之类的，需要多看多练培养感觉才能想到贪心的思路。

  1. 究竟什么题目是贪心呢？

Carl个人认为：如果找出局部最优并可以推出全局最优，就是贪心，如果局部最优都没找出来，就不是贪心，可能是单纯的模拟。（并不是权威解读，一家之辞哈）

但我们也不用过于强调什么题目是贪心，什么不是贪心，那就太学术了，毕竟学会解题就行了。

  1. 如何知道局部最优推出全局最优，有数学证明么？

在做贪心题的过程中，如果再来一个数据证明，其实没有必要，手动模拟一下，如果找不出反例，就试试贪心。面试中，代码写出来跑过测试用例即可，或者自己能自圆其说理由就行了

就像是 要用一下 1 + 1 = 2，没有必要再证明一下 1 + 1 究竟为什么等于 2。（例子极端了点，但是这个道理）

相信大家读完关于贪心算法，你该了解这些！

(opens new window)，就对贪心有了一个基本的认识了。

# 贪心简单题

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

  • 贪心算法：分发饼干
  • (opens new window)
  • 贪心算法：K次取反后最大化的数组和
  • (opens new window)
  • 贪心算法：柠檬水找零
  • (opens new window)

# 贪心中等题

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

  • 贪心算法：摆动序列
  • (opens new window)
  • 贪心算法：单调递增的数字
  • (opens new window)

# 贪心解决股票问题

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

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

# 两个维度权衡问题

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

  • 贪心算法：分发糖果
  • (opens new window)
  • 贪心算法：根据身高重建队列
  • (opens new window)

在讲解本题的过程中，还强调了编程语言的重要性，模拟插队的时候，使用C++中的list（链表）替代了vector(动态数组)，效率会高很多。

所以在贪心算法：根据身高重建队列（续集）

(opens new window)详细讲解了，为什么用list（链表）更快！

大家也要掌握自己所用的编程语言，理解其内部实现机制，这样才能写出高效的算法！

# 贪心难题

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

# 贪心解决区间问题

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

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

# 其他难题

贪心算法：最大子序和

(opens new window) 其实是动态规划的题目，但贪心性能更优，很多同学也是第一次发现贪心能比动规更优的题目。

贪心算法：加油站

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

最后贪心系列压轴题目贪心算法：我要监控二叉树！

(opens new window)，不仅贪心的思路不好想，而且需要对二叉树的操作特别娴熟，这就是典型的交叉类难题了。

# 贪心每周总结

周总结里会对每周的题目中大家的疑问、相关难点或者笔误之类的进行复盘和总结。

如果大家发现文章哪里有问题，那么在周总结里或者文章评论区一定进行了修正，保证不会因为我的笔误或者理解问题而误导大家，哈哈。

所以周总结一定要看！

  • 本周小结！（贪心算法系列一）
  • (opens new window)
  • 本周小结！（贪心算法系列二）
  • (opens new window)
  • 本周小结！（贪心算法系列三）
  • (opens new window)
  • 本周小结！（贪心算法系列四）
  • (opens new window)

# 总结

贪心专题汇聚为一张图：

这个图是 代码随想录知识星球

(opens new window) 成员：海螺人

(opens new window)所画，总结的非常好，分享给大家。

很多没有接触过贪心的同学都会感觉贪心有啥可学的，但只要跟着「代码随想录」坚持下来之后，就会发现，贪心是一种很重要的算法思维而且并不简单，贪心往往妙的出其不意，触不及防！

回想一下我们刚刚开始讲解贪心的时候，大家会发现自己在坚持中进步了很多！

这也是「代码随想录」的初衷，只要一路坚持下来，不仅基础扎实，而且进步也是飞速的。

在这十八道贪心经典题目中，大家可以发现在每一道题目的讲解中，我都是把什么是局部最优，和什么是全局最优说清楚。

这也是我认为判断这是一道贪心题目的依据，如果找不出局部最优，那可能就是一道模拟题。

不知不觉又一个系列结束了

相关文章：

贪心算法总结篇

文章转自代码随想录 贪心算法总结篇 我刚刚开始讲解贪心系列的时候就说了，贪心系列并不打算严格的从简单到困难这么个顺序来讲解。 因为贪心的简单题可能往往过于简单甚至感觉不到贪心，如果我连续几天讲解简单的贪心，估计录友们一定会不耐…...

编程日记 2023/8/31 8:15:07

ICCV 2023 | 港中文MMLab: 多帧光流估计模型VideoFlow，首次实现亚像素级别误差

本文提出了一个多帧光流估计模型 VideoFlow，旨在充分挖掘视频中的时序信息和运动规律，避免当前主流方法只以两帧图片作为输入而面临的信息瓶颈，显著提升了光流估计的性能。 在公开的 Sintel Bechmark 上，VideoFlow 在 Clean 和 Fi…...

编程日记 2023/8/31 8:14:06

【python爬虫】—图片爬取

图片爬取 需求分析Python实现 需求分析 从https://pic.netbian.com/4kfengjing/网站爬取图片，并保存 Python实现 获取待爬取网页 def get_htmls(pageslist(range(2, 5))):"""获取待爬取网页"""pages_list []for page in pages:u…...

编程日记 2023/8/31 8:13:05

自动化运维工具—Ansible

一、Ansible概述1.1 Ansible是什么1.2 Ansible的特性1.3 Ansible的特点1.4 Ansible数据流向 二、Ansible 环境安装部署三、Ansible 命令行模块（1）command 模块（2）shell 模块（3）cron 模块（4&…...

编程日记 2023/8/31 8:12:03

uniapp 安卓平台签名证书(.keystore)生成

安装JRE环境 下载jre安装包：https://www.oracle.com/java/technologies/downloads/#java8安装jre安装包时，记录安装目录(例:C:\Program Files\Java\jdk-20)打开命令行（cmd），将JRE安装路径添加到系统环境变量 d: se…...

编程日记 2023/8/31 8:11:02

缓存中间件Redis常考知识点

缓存中间件Redis常考知识点 1 什么是RDB和AOF2 Redis的过期键的删除策略3 简述Redis事务实现4 Redis 主从复制的核⼼原理5 Redis有哪些数据结构？分别有哪些典型的应⽤场景？6 Redis分布式锁底层是如何实现的？7 Redis主从复制的核⼼原理8 Redis…...

编程日记 2023/8/31 8:10:01

detour编译问题及导入visual studio

Detours是经过微软认证的一个开源Hook库，Detours在GitHub上，网址为 https://github.com/Microsoft/Detours 注意版本不一样的话也是会出问题的，因为我之前是vs2022的所以之前的detours.lib不能使用，必须用对应版本的x64 Native To…...

编程日记 2023/8/31 8:08:59

江西武功山旅游攻略(周末两日游)

一、 往返路线 1: 出发路线 周五晚上上海出发坐火车🚄到江西萍乡(11.5小时,卧铺550左右) 打车到江西武功山景区,120-150元左右,人均30元,1小时10分左右到达 或者 🚗到达萍乡北之后 出站后步行200米到长途汽车站，乘旅游巴士直达武功山游…...

编程日记 2023/8/31 8:07:58

Django静态文件媒体文件文件上传

文章目录 一、静态文件和媒体文件1.在django中使用静态文件实践2.在django中使用媒体文件 二、文件上传单文件上传实践多文件上传 一、静态文件和媒体文件 媒体文件: 用户上传的文件，叫做media 静态文件:存放在服务器的css,js,image,font等 叫做static1.在django中…...

编程日记 2023/8/31 8:06:57

mysql 分库分表实现思路

MySQL的分库分表是一种常用的数据库拆分方案，它可以提高数据库的性能和扩展性。下面是一般的实现步骤： 数据库设计：首先，需要对数据库进行良好的设计。确定要分库分表的实体和关系，并根据业务需求进行合理的拆分。 数…...

编程日记 2023/8/31 8:05:55

Android深思如何防止快速点击

前言 其实快速点击是个很好解决的问题，但是如何优雅的去解决确是一个难题，本文主要是记录一些本人通过解决快速点击的过程中脑海里浮现的一些对这个问题的深思。 作者：流浪汉kylin 链接：https://juejin.cn/post/7197337416096055…...

编程日记 2023/8/31 8:04:54

PHP自己的框架cookie()使用（完善篇七）

1、PHP自己的框架cookie() 2、cookie类&#xff08;CookieBase.php&#xff09; <?php class CookieBase {/*** 设置cookie*/public static function set($name, $value, $expire 3600, $path , $domain , $secure false, $httponly false) {setcookie($name, $valu…...

编程日记 2023/8/31 8:03:53

Spring Boot Dubbo Zookeeper（含ZK安装脚本）

文章目录 Spring Boot Dubbo Zookeeper&#xff08;含ZK安装脚本&#xff09;简介DubboCommonProviderConsumer Zookeeper Spring Boot Dubbo Zookeeper&#xff08;含ZK安装脚本&#xff09; 简介 Dubbo Common 公共依赖 <!-- Spring Boot Starter --> <dependen…...

编程日记 2023/8/31 8:02:51

BigDecimal百科全书

一、BigDecimal简述 Java在java.math包中提供的API类BigDecimal&#xff0c;用来对超过16位有效位的数进行精确的运算。双精度浮点型变量double可以处理16位有效数&#xff0c;但在实际应用中&#xff0c;可能需要对更大或者更小的数进行运算和处理。 一般情况下&#xff0c;…...

编程日记 2023/8/31 8:01:50

【30天熟悉Go语言】11 数组的全方位使用与解析

作者&#xff1a;秃秃爱健身&#xff0c;多平台博客专家&#xff0c;某大厂后端开发&#xff0c;个人IP起于源码分析文章 &#x1f60b;。 源码系列专栏&#xff1a;Spring MVC源码系列、Spring Boot源码系列、SpringCloud源码系列&#xff08;含&#xff1a;Ribbon、Feign&…...

编程日记 2023/8/31 8:00:49

静态路由(详细理解+实例精讲)

系列文章目录 华为数通学习&#xff08;6&#xff09; 前言 一&#xff0c;静态路由 二&#xff0c;静态路由配置 三&#xff0c;缺省路由 四&#xff0c;缺省路由应用场景 总结 前言 随着华为公司的不断发展&#xff0c;数据通信这门技术也越来越重要&#xff0c;很多人…...

编程日记 2023/8/31 7:59:47

leetcode做题笔记118. 杨辉三角

给定一个非负整数 numRows&#xff0c;生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中&#xff0c;每个数是它左上方和右上方的数的和。 思路一&#xff1a;动态规划 int** generate(int numRows, int* returnSize, int** returnColumnSizes){int **returnnum(int **)…...

编程日记 2023/8/31 7:58:46

stm32之24.RTC闹钟usart端口修改配置

&#xff08;需要修改&#xff09; 源码 while(1){//rtc唤醒事件if(g_rtc_wakeup_event){//获取日期RTC_GetDate(RTC_Format_BCD,&RTC_DateStructure);printf("20%02x/%02x/%02xWeek:%x\r\n",RTC_DateStructure.RTC_Year,RTC_DateStructure.RTC_Month,RTC_Date…...

编程日记 2023/8/31 7:57:43

Spring Security无法调用接口错误解决

之前在写程序的时候&#xff0c;发现有个接口使用postmapping发送请求一直无法进行调用 PostMapping("/user/login")public ResponseResult login(User user){//登录&#xff0c;这里登录的时候需要传入用户名和密码System.out.println("user "user.toSt…...

编程日记 2023/8/31 7:56:41

运维Shell脚本小试牛刀(二)

运维Shell脚本小试牛刀(一) 运维Shell脚本小试牛刀(二) 运维Shell脚本小试牛刀(三)::$(cd $(dirname $0)&#xff1b; pwd)命令详解 一: if---else.....fi 条件判断演示 [rootwww shelldic]# cat checkpass.sh #!/bin/bash - # # # # FILE: ch…...

编程日记 2023/8/31 7:55:40

飞天使-python的模块与包与装饰器

文章目录 模块与包标准模块第三方模块自定义模块 高级语法切片迭代器/生成器高级模式&#xff08;闭包&#xff09;高级模式&#xff08;装饰器&#xff09; 参考视频 模块与包 标准模块 import os print(os.getcwd())import sys print(sys.argv) print(sys.platform) print(…...

编程日记 2023/8/31 7:54:39

linux shell脚本利用 kill -0 检查进程是否存在

1.kill -0介绍 kill -0 pid用来检查进程是否存在&#xff0c;kill -0 pid解释(来自man kill)&#xff1a;“If sig is 0, then no signal is sent, but error checking is still performed.”不发送任何信号&#xff0c;但是系统会进行错误检查。 kill -0 pid ->若存在&am…...

编程日记 2023/8/31 7:53:38

抖音视频删了怎么在电脑上找回来

【昨天整理电脑文件时&#xff0c;不小心将剪辑好的抖音作品误删了&#xff0c;但是回收站中找不回来了&#xff0c;这些视频是我花了很多心血制作的&#xff0c;如果没了真的十分可惜&#xff01;希望大家能帮帮我&#xff0c;告诉我应该如何恢复这些文件。】 现在人们都喜欢…...

编程日记 2023/8/31 7:52:37

方面级别情感分析之四元组预测

情感四元组预测现有方法 阅读本文之前我们默认你对情感分析有基本的认识。 如果没有请阅读文章(https://tech.tcl.com/post/646efb5b4ba0e7a6a2da6476) 情感分析四元组预测涉及四个情感元素: 方面术语a&#xff0c;意见术语(也叫观点术语)o&#xff0c; 方面类别ac&#xff0c…...

编程日记 2023/8/31 7:51:36

算法 稀疏数组 数组优化 数组压缩 二维数组转稀疏数组 算法合集（二）

1. 五子棋游戏&#xff0c;玩家对战一半停战休息&#xff0c;此时需要存储当前对战双方棋子信息 a. 采用二维数组存储&#xff1a; 0为空&#xff0c; 1代表黑棋 2代表蓝色棋子 b. 棋盘为11行&#xff0c;11列 > int [][] chessArray new int [11][11]; c. 出现的问题&am…...

编程日记 2023/8/31 7:50:34

交换机端口安全实验

文章目录 一、实验的背景与目的二、实验拓扑三、实验需求四、实验解法1. PC配置IP地址部分2. 在SW1上开启802.1X身份验证3. 创建一个用户身份验证的用户。用户名为wangdaye&#xff0c;密码为1234564.创建一个端口隔离组&#xff0c;实现三台PC无法互相访问 摘要&#xff1a; 本…...

编程日记 2023/8/31 7:49:32

c# 本地化中英文切换

区域 线程默认区域为当前计算机所选区域 设置当前区域&#xff1a; Thread.CurrentThread.CurrentCulture new CultureInfo(“zh-cn”); 获取当前区域&#xff1a; Console.WriteLine(Thread.CurrentThread.CurrentCulture.ToString()); 区域名称&#xff1a; “zh-cn” 中文…...

编程日记 2023/8/31 7:48:31

rabbitmq的优先级队列

在我们系统中有一个 订单催付 的场景&#xff0c;我们的客户在天猫下的订单 , 淘宝会及时将订单推送给我们&#xff0c;如果在用户设定的时间内未付款那么就会给用户推送一条短信提醒&#xff0c;很简单的一个功能对吧&#xff0c;但是&#xff0c;tianmao商家对我们来说&#…...

编程日记 2023/8/31 7:47:30

SpringBoot的Cacheable缓存注解

当我们的应用程序需要频繁地读取和写入数据时&#xff0c;为了提高应用程序的性能&#xff0c;我们通常会使用缓存技术。Spring Boot 提供了一种简单而强大的缓存框架&#xff0c;它可以轻松地将数据缓存到 Redis 中。 在 Spring Boot 中可以在方法上简单的加上注解实现缓存。…...

编程日记 2023/8/31 7:46:29

uniapp的 picker 日期时间选择器

效果图&#xff1a; dateTimePicker.js function withData(param){return param < 10 ? 0 param : param; } function getLoopArray(start,end){var start start || 0;var end end || 1;var array [];for (var i start; i < end; i) {array.push(withData(i))…...

编程日记 2023/8/31 7:45:28