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

贪心算法一

news 来源：原创 2025/8/28 20:33:01

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：了解什么是贪心算法，并且掌握贪心算法。

> 毒鸡汤：有些事情，总是不明白，所以我不会坚持。早安!

> 专栏选自：贪心算法_დ旧言~的博客-CSDN博客

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

一、算法讲解

贪心算法的定义：

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

解题的一般步骤是：

建立数学模型来描述问题；
把求解的问题分成若干个子问题；
对每一子问题求解，得到子问题的局部最优解；
把子问题的局部最优解合成原来问题的一个解。

如果大家比较了解动态规划，就会发现它们之间的相似之处。最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。

动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。

二、算法习题

2.1、第一题

题目链接：860. 柠檬水找零 - 力扣（LeetCode）

题目描述：

算法思路：

a. 遇到 5 元钱，直接收下；

b. 遇到 10 元钱，找零 5 元钱之后，收下；

c. 遇到 20 元钱：

先尝试凑 10 + 5 的组合；
如果凑不出来，拼凑 5 + 5 + 5 的组合；

代码呈现：

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five = 0, ten = 0;for (auto x : bills) {if (x == 5)five++;       // 5 元：直接收下else if (x == 10) // 10 元：找零 5 元{if (five == 0)return false;five--;ten++;} else // 20 元：分情况讨论{if (ten && five) // 贪⼼{ten--;five--;} else if (five >= 3) {five -= 3;} elsereturn false;}}return true;}
};

2.2、第二题

题目链接：2208. 将数组和减半的最少操作次数 - 力扣（LeetCode）

题目描述：

算法思路：

每次挑选出「当前」数组中「最⼤」的数，然后「减半」；
直到数组和减少到⾄少⼀半为⽌。

为了「快速」挑选出数组中最⼤的数，我们可以利⽤「堆」这个数据结构。

代码呈现：

class Solution {
public:int halveArray(vector<int>& nums) {priority_queue<double> heap; // 创建⼀个⼤根堆double sum = 0.0;for (int x : nums) // 把元素都丢进堆中，并求出累加和{heap.push(x);sum += x;}sum /= 2.0; // 先算出⽬标和int count = 0;while (sum > 0) // 依次取出堆顶元素减半，直到减到之前的⼀半以下{double t = heap.top() / 2.0;heap.pop();sum -= t;count++;heap.push(t);}return count;}
};

2.3、第三题

题目链接：179. 最大数 - 力扣（LeetCode）

题目描述：

算法思路：

可以先优化：

将所有的数字当成字符串处理，那么两个数字之间的拼接操作以及⽐较操作就会很⽅便。

贪⼼策略：

按照题⽬的要求，重新定义⼀个新的排序规则，然后排序即可。

排序规则：

「A 拼接 B」⼤于「B 拼接 A」，那么 A 在前，B 在后；
「A 拼接 B」等于「B 拼接 A」，那么 A B 的顺序⽆所谓；
「A 拼接 B」⼩于「B 拼接 A」，那么 B 在前，A 在后

代码呈现：

class Solution {
public:string largestNumber(vector<int>& nums) {// 优化：把所有的数转化成字符串vector<string> strs;for (int x : nums)strs.push_back(to_string(x));// 排序sort(strs.begin(), strs.end(), [](const string& s1, const string& s2) {return s1 + s2 > s2 + s1;});// 提取结果string ret;for (auto& s : strs)ret += s;if (ret[0] == '0')return "0";return ret;}
};

2.4、第四题

题目链接：376. 摆动序列 - 力扣（LeetCode）

题目描述：

算法思路：

对于某⼀个位置来说：

如果接下来呈现上升趋势的话，我们让其上升到波峰的位置；
如果接下来呈现下降趋势的话，我们让其下降到波⾕的位置。
因此，如果把整个数组放在「折线图」中，我们统计出所有的波峰以及波⾕的个数即可

代码呈现：

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int n = nums.size();if (n < 2)return n;int ret = 0, left = 0;for (int i = 0; i < n - 1; i++) {int right = nums[i + 1] - nums[i]; // 计算接下来的趋势if (right == 0)continue; // 如果⽔平，直接跳过if (right * left <= 0)ret++; // 累加波峰或者波⾕left = right;}return ret + 1;}
};

2.5、第五题

题目链接：300. 最长递增子序列 - 力扣（LeetCode）

题目描述：

算法思路：

我们在考虑最⻓递增⼦序列的⻓度的时候，其实并不关⼼这个序列⻓什么样⼦，我们只是关⼼最后⼀个元素是谁。这样新来⼀个元素之后，我们就可以判断是否可以拼接到它的后⾯。
因此，我们可以创建⼀个数组，统计⻓度为 x 的递增⼦序列中，最后⼀个元素是谁。为了尽可能让这个序列更⻓，我们仅需统计⻓度为 x 的所有递增序列中最后⼀个元素的「最⼩值」。
统计的过程中发现，数组中的数呈现「递增」趋势，因此可以使⽤「⼆分」来查找插⼊位置。

代码呈现：

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> ret;ret.push_back(nums[0]);for (int i = 1; i < n; i++) {if (nums[i] > ret.back()) // 如果能接在最后⼀个元素后⾯，直接放{ret.push_back(nums[i]);} else {// ⼆分插⼊位置int left = 0, right = ret.size() - 1;while (left < right) {int mid = (left + right) >> 1;if (ret[mid] < nums[i])left = mid + 1;elseright = mid;}ret[left] = nums[i]; // 放在 left 位置上}}return ret.size();}
};

2.6、第六题

题目链接：334. 递增的三元子序列 - 力扣（LeetCode）

题目描述：

算法思路：

不⽤⼀个数组存数据，仅需两个变量即可。也不⽤⼆分插⼊位置，仅需两次⽐较就可以找到插⼊位
置。

代码呈现：

class Solution {
public : bool increasingTriplet(vector<int>& nums) 
{int a = nums[0], b = INT_MAX;for (int i = 1; i < nums.size(); i++) {if (nums[i] > b)return true;else if (nums[i] > a)b = nums[i];elsea = nums[i];}return false;}
};

三、结束语

今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。

贪心算法一

> 作者：დ旧言~ > 座右铭：松树千年终是朽，槿花一日自为荣。 > 目标：了解什么是贪心算法，并且掌握贪心算法。 > 毒鸡汤：有些事情，总是不明白，所以我不会坚持。早安! >…...

编程日记 2025/8/28 20:33:01

Java进阶：Dubbo

分布式RPC框架Apache Dubbo 1. 软件架构的演进过程软件架构的发展经历了由单体架构、垂直架构、SOA架构到微服务架构的演进过程，下面我们分别了解一下这几个架构。 1.1 单体架构架构说明： 全部功能集中在一个项目内（All in one&#xf…...

编程日记 2025/8/28 20:32:46

【Day9】make/makeFile如何让项目构建自动化起飞

【Day9】make/makeFile如何让项目构建自动化起飞使用make命令编写makefile文件依赖管理增量构建makefile注释：#makefile其他语法 make/makefile递归式工作过程在Linux中，项目自动化构建是指使用一系列工具和脚本来自动执行软件项目的编译、测试、打包和…...

编程日记 2025/8/28 20:27:33

SCI1区TOP：自适应学习粒子群算法SLPSO，深度解析+性能实测

目录 1.摘要2.改进策略3.自适应学习粒子群算法4.结果展示5.参考文献6.获取代码 1.摘要粒子群算法（PSO）是一种基于种群的随机搜索方法，广泛应用于科学和工程领域的连续空间优化问题，并已证明其高效性和有效性。许多实际问题的往往…...

编程日记 2025/8/28 20:29:07

迷你世界脚本显示板管理接口：DisPlayBoard

显示板管理接口：DisPlayBoard 迷你世界更新时间: 2023-04-26 10:21:14 具体函数名及描述如下: 序号函数名函数描述 1 showBoard(...) 对玩家显示显示板 2 hideBoard(...) 对玩家隐藏显示板 3 setBoardPicture 对玩家设置显示板的图片…...

编程日记 2025/8/28 20:27:34

如何使用 LLM 生成的术语自动在搜索应用程序上构建 autocomplete 功能

作者：来自 Elastic Michael Supangkat 了解如何在 Elastic Cloud 中，通过使用 LLM 生成的词汇，为搜索应用增强自动补全功能，实现更智能、更动态的搜索建议。自动补全是搜索应用中的一项关键功能，它通过在用户输入时实…...

编程日记 2025/8/28 20:31:12

电路基础：【1】PN结二极管制作电桥点亮LED灯

第一章：PN结二极管制作电桥点亮LED灯文章目录第一章：PN结二极管制作电桥点亮LED灯前言一、电路原理二、电路图与元器件1.电路图做实验总结前言在本章中，我们将探讨如何通过PN结二极管制作电桥电路，并利用该电路点亮LED灯。L…...

编程日记 2025/8/24 7:52:47

蓝桥与力扣刷题（蓝桥门牌制作）

题目：小蓝要为一条街的住户制作门牌号。这条街一共有 2020 位住户，门牌号从 1 到 2020编号。小蓝制作门牌的方法是先制作 0 到 9 这几个数字字符，最后根据需要将字符粘贴到门牌上，例如门牌 1017 需要依次粘贴字符 1、0、1、7&…...

编程日记 2025/8/28 20:26:50

unity console日志双击响应事件扩展

1 对于项目中一些比较长的日志，比如前后端交互协议具体数据等，这些日志内容可能会比较长，在unity控制面板上查看不是十分方便，我们可以对双击事件进行扩展，将日志保存到一个文本中，然后用系统默认的文本查看…...

编程日记 2025/8/28 20:26:25

基于Django创建一个WEB后端框架（DjangoRestFramework+MySQL)流程

一、Django项目初始化 1.创建Django项目 Django-admin startproject 项目名 2.安装 djangorestframework pip install djangorestframework 解释: Django REST Framework (DRF) 是基于 Django 框架的一个强大的 Web API 框架，提供了多种工具和库来构建 RESTf…...

编程日记 2025/8/28 20:26:27

unittest框架核心知识的系统复习及与pytest的对比

1. unittest 介绍是什么：Python 标准库自带的单元测试框架，遵循 xUnit 架构（类似Java的JUnit）。核心概念： TestCase：测试用例的基类，所有测试类需继承它。 TestSuite：测试套件&a…...

编程日记 2025/8/23 7:24:47

嵌入式硬件设计SPI时需要注意什么？

嵌入式硬件设计SPI时需要注意什么？ 1. 硬件设计注意事项关键点注意事项1. 信号完整性- 缩短SCK、MOSI、MISO的走线长度，避免反射干扰。- 使用屏蔽线或差分信号（高速场景）。- 阻抗匹配（特别是高频信号，如50Ω端接）。2. 电源与地线- 电源去耦：每个SPI芯片的VCC附近放置0…...

编程日记 2025/8/21 8:54:37

vscode远程ssh链接服务器

前提：安装并配置好 ssh 服务,并且远程主机和本地主机在同一个局域网。降级到1.85.2版本并禁用自动更新，因为最新的vscode不支持remote SSH。【VS Code】VS Code不再支持remote SSH 1.在vscode 扩展中搜索Remote - SSH,下载安装扩展 2.点击远程资源管理…...

编程日记 2025/8/20 12:35:59

97k倍区间

97k倍区间 ⭐️难度：中等 🌟考点：暴力，2017省赛 📖 📚 import java.util.Scanner;public class Main {static int N 100010;public static void main(String[] args) {Scanner sc new Scanner(System.…...

编程日记 2025/8/24 22:25:21

绝美焦糖暖色调复古风景画面Lr调色教程，手机滤镜PS+Lightroom预设下载！

调色教程通过 Lr 软件丰富的工具和功能，对风景照片在色彩、影调等方面进行调整。例如利用基本参数调整选项，精准控制照片亮度、对比度、色温、色调等基础要素；运用 HSL 面板可对不同色彩的色相、饱和度以及明亮度进行单独调节；利…...

编程日记 2025/8/25 17:14:08

双王炸爆单，问界M8、M9怎么选？

文 | AUTO芯球作者 | 雷慢问界M8一小时小订7500台， 新问界M9一小时订单3800台。余承东这次直接把一对王炸打了出来， 来看这对大小王， 问界M8预售价36.8万到45.8万， 问界M9预售价47.8万到57.8万， 这两款车&…...

编程日记 2025/8/25 20:09:42

【自学笔记】OpenStack基础知识点总览-持续更新

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录 OpenStack基础知识点总览一、OpenStack概述1.1 OpenStack起源1.2 OpenStack的目标与优势1.3 OpenStack的常见核心项目二、OpenStack的节点类型2.1 控制节点2.2 网络…...

编程日记 2025/8/28 0:57:09

同步 Fork 仓库的命令

同步 Fork 仓库的命令要将您 fork 的仓库的 main 分支与原始仓库（fork 源）同步，您可以使用以下命令： 首先，确保您已经添加了原始仓库作为远程仓库（如果尚未添加）： git remote add…...

编程日记 2025/8/24 4:47:58

2025-03-04 学习记录--C/C++-C语言判断是否是素数

合抱之木，生于毫末；九层之台，起于累土；千里之行，始于足下。💪🏻 C语言判断是否是素数一、代码 ⭐️ #include <stdio.h> #include <stdbool.h> // 使用 bool 类型// 判断是否是…...

编程日记 2025/8/26 23:49:22

1、CI/CD 平台安装部署（Gitlab+Jenkins）

CI/CD 平台安装部署安装部署Gitlab安装Gitlab添加组、创建用户、创建项目 Jenkins 安装Maven 安装和配置Tomcat 安装和配置Jenkins 构建 Maven 项目自由风格项目构建什么是CI/CD？ 通俗来说就是启动一个服务，能够监听代码变化，然后自动执行构…...

编程日记 2025/8/18 6:13:37

数据集路径出错.yaml‘ images not found , missing path

方法一：删除settings.yaml 方法二：dataset_name.yaml改用绝对路径，如最后一张图错误分析： dataset_name.yaml中的path的路径仅支持绝对路径，写相对路径就会搜索不到，使用settings.json中的路径&#xff0…...

编程日记 2025/8/27 22:25:06

零基础学习Python 之类（Class）和实例（Instance）_我的学习Python记录12

零基础学习Python 之类（Class）和实例（Instance）_我的学习Python记录12 目录什么是类和实例？类的作用如何定义类？如何创建实例？类的属性和方法属性方法实际案例案例 1：学生信息…...

编程日记 2025/8/28 12:06:57

Map＜String,Object＞转换为XML报文的方法

1. 使用 JAXB (Java Architecture for XML Binding) JAXB 是 Java 标准库的一部分，支持将 Java 对象与 XML 相互转换。虽然 JAXB 主要用于将 Java 对象转换为 XML，但可以通过一些技巧将 Map<String, Object> 转换为 XML。示例代码 import java…...

编程日记 2025/8/25 3:05:42

Linux：如何安装虚拟机

Linux：如何安装虚拟机第一步首先打开阿里巴巴开源镜像网站然后点击相应要下载链接选择自己需要的这个是完整版这个是联网进行安装系统这个是基础版只有命令行界面这里我选择下载基础版下载好打开vmwareworkstation 开始安装...

编程日记 2025/8/23 12:34:24

HTML 编辑器推荐与 VS Code 使用教程

在进行 HTML 编程时，选择一款合适的 HTML 编辑器能极大地提高开发效率。以下为大家推荐几款常用且功能强大的 HTML 编辑器，同时详细介绍如何使用 VS Code 创建和预览 HTML 文件。一、HTML 编辑器推荐 VS Code：由微软开发，是一款…...

编程日记 2025/8/24 8:39:31

Python的Pandas和matplotlib库：让数据可视化贼简单

在数据爆炸的时代，数据可视化已成为数据分析的关键环节。Python 作为强大的编程语言，拥有众多用于数据可视化的库，而 pandas 库在其中扮演着重要角色。它不仅能高效处理和分析数据，还具备强大的数据可视化功能，让我们轻…...

编程日记 2025/8/27 8:45:27

私有云基础架构与运维（二）

二.私有云基础架构【项目概述】经过云计算基础知识及核心技术的学习后，希望进一步了解 IT 基础架构的演变过程，通过学习传统架构、集群架构以及私有云基础架构的相关知识，认识企业从传统 IT 基础架构到私有云基础架构转型的必要性。…...

编程日记 2025/8/25 18:28:44

Java Maven 项目问题：org.dom4j:dom4j:pom:2.1.3 failed to transfer from...

问题与处理策略问题描述 IDEA 中打开一个 Java 项目，使用 Maven 构建时，报如下错误 org.dom4j:dom4j:pom:2.1.3 failed to transfer from https://repo.maven.apache.org/maven2 during a previous attempt. This failure was cached in the local r…...

编程日记 2025/8/23 4:41:11

DeepSeek group-limited expert routing和负载均衡

Ref https://github.com/deepseek-ai/DeepSeek-V3/blob/main/inference/model.py GitHub - deepseek-ai/EPLB: Expert Parallelism Load Balancer DeepSeek-V3 Technical Report DeepSeek的路由方法 class Gate(nn.Module):def __init__(self, args: ModelArgs):super().__…...

编程日记 2025/8/25 21:38:46

一、算法讲解

二、算法习题

2.1、第一题

2.2、第二题

2.3、第三题

2.4、第四题

2.5、第五题

2.6、第六题

三、结束语

相关文章：