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

【贪心算法篇】:“贪心”之旅--算法练习题中的智慧与策略(一)

✨感谢您阅读本篇文章,文章内容是个人学习笔记的整理,如果哪里有误的话还请您指正噢✨
✨ 个人主页:余辉zmh–CSDN博客
✨ 文章所属专栏:贪心算法篇–CSDN博客

在这里插入图片描述

文章目录

  • 一.贪心算法
    • 1.什么是贪心算法
    • 2.贪心算法的特点
  • 二.例题
    • 1.柠檬水找零
    • 2.将数组和减半的最小操作次数
    • 3.最大数
    • 4.摆动序列

一.贪心算法

1.什么是贪心算法

贪心算法(Greedy Algorithm)是一种在每一步选择中都采取在当前状态下的最优决策的算法策略。他并不从整体最优上加以考虑,而是做出在当前看来是最好的选择。

1.把解决问题的过程分为若干步骤。

2.解决每一步时都选取当前看起来最优的选择。

3.“希望”得到全局最优解。(注意是“希望”,可不一定就是最优解)

简单形容就是贪婪+鼠目寸光,因此叫做贪心算法。

下面介绍几个典型的示例:

在这里插入图片描述

2.贪心算法的特点

  • 贪心策略的提出
    • 贪心策略的提出是没有标准和模板的,可能每一道题的贪心策略都是不同的,因此在学习贪心算法的时候重点要掌握每一道题的策略,把这道题的策略当成经验。
  • 贪心策略的正确性
    • 前面提到一个词“希望”得到最优解,因为有可能“贪心策略是一个错误的方法,正确的贪心策略,是需要严格的数学证明。

二.例题

1.柠檬水找零

题目

在这里插入图片描述

在这里插入图片描述

算法原理

根据题意可以明白,顾客付钱有三种情况,如果是5美元,那就直接收下;如果是10美元,并且当前手里5美元的数量大于等于1,收下然后找零5美元,如果没有5美元,则返回false;如果是20美元,有两种找零方式,第一种:10+5;第二种:5+5+5;这里就用到了贪心的思想,优先使用第一种方式找零。如果第一次20美元使用第二种找零方式,恰好手里有三张5美元,一张10美元,如果第一次就使用三张5美元,等之后再次遇到10美元,就只剩一张10美元,不能找零。

这里用到的是交换论证法:如果20美元使用第二种找零方式,手里的10美元一直到最后也没有使用,因此10美元可以替换20美元找零时的两张5美元;如果第一次20美元使用第二种找零方式5+5+5,第二次使用第一种方式找零10+5,第二次的10可以和第一次的两张5交换,交换后无影响。

代码实现

bool lemonadeChange(vector<int>& bills){//设置两个变量一个用来表示5元的个数,一用来表示10元的个数int five = 0, ten = 0;for(auto x : bills){//如果给的是5元,直接收下if(x==5){five++;}//如果给的是10元,先判度是否有5元找零,有就找零收下,没有就返回if(x==10){if(five==0){return false;}else{five--;ten++;}}//如果给的是20元,有三种情况if(x==20){//贪心思想,优先考虑10+5找零if(ten&&five){five--;ten--;}//第一种不能找零,再考虑第二种找零方式5+5+5else if(five>=3){five -= 3;}//如果两种情况都不能找零,返回else{return false;}}}return true;
}

2.将数组和减半的最小操作次数

题目

在这里插入图片描述

在这里插入图片描述

算法原理

因此本道题的贪心策略:使用最少的操作次数完成数组和的减半,因此每次选择一个数减半时,都选择最大的那个数减半,这里就是贪心的思想,每次都选择最大的数减半。既然要快速获取数组中的最大数,就可以借助大根堆这个数据结构,每次都选择堆顶的元素减半,减半后从新放回堆中调整,然后循环进行,知道数组和减到一半,返回最小操作数。

代码实现

int halveArray(vector<int>& nums){//建立一个大根堆priority_queue<double> heap;//遍历数组求和并存放到堆中double sum = 0.0;for(int x : nums){heap.push(x);sum += x;}//先获取数组和的一半,每次减去堆顶元素的一半直到减为小于等于0sum /= 2.0;int count=0;while(sum>0){//获取堆顶元素的一半,并删去double t = heap.top() / 2.0;heap.pop();count++;sum -= t;heap.push(t);}return count;
}

3.最大数

题目

在这里插入图片描述

算法原理

根据题意要求,可以自定义排序规则,因为要返回的是组合后最大的数,所以按照自定义的排序规则从大到小的排序;比如现在有两个数,a和b,有两种组合方式ab和ba,如果组合后ab>ba,则a在前,b在后;如果ab=ba,则a=b;如果ab<ba,则b在前,a在后;比如示例一:a=10,b=2,组合后ab=102<ba=210,所以b(2)在前,a(10)在后,根据自定义排序规则将整个数组中的元素都排序后,然后从前往后组合就是要找的最大数。

这里有一个细节点,如何快速的将两个数组合比较?可以先将每一个数都转化成字符串的形式,组合时直接的将两个字符串相加拼接即可,这样就能快速的组合,最后排完序后,还可以直接从前往后将所有字符串拼接,就是要返回的结果。

至于为什么上面的这个自定义排序规则是正确的,可以看下面的证明过程:

在这里插入图片描述

代码实现

string largestNumber(vector<int>& nums){//先将每个数字转换成字符串,存放到字典数组中vector<string> dictionary;for(auto x : nums){dictionary.push_back(to_string(x));}//使用Lambda表达式自定义排序规则sort(dictionary.begin(), dictionary.end(), [&](const string& s1, const string& s2){return s1 + s2 > s2 + s1; });string ret;for(auto s : dictionary){ret += s;}if(ret[0]=='0'){return "0";}return ret;
}

4.摆动序列

题目

在这里插入图片描述

在这里插入图片描述

算法原理

在这里插入图片描述

代码实现

//全局变量表示左侧的峰值
int left = 0;
int wiggleMaxLength(vector<int>& nums){//寻找波峰和波谷int ret = 0;for (int i = 0; i < nums.size(); i++){//如果是最后一个位置,直接+1if(i==nums.size()-1){ret++;break;}//先计算当前位置右侧的峰值int right = nums[i + 1] - nums[i];//如果右侧峰值等于0,跳过if(right==0){continue;}//如果左右两侧峰值相乘小于0,表示当前位置是波峰或者波谷if(left*right<=0){ret++;}//将当前位置的右侧峰值赋值给左侧,表示下一个位置的左侧峰值left = right;}return ret;
}

以上就是关于贪心算法以及一些练习题的讲解,如果哪里有错的话,可以在评论区指正,也欢迎大家一起讨论学习,如果对你的学习有帮助的话,点点赞关注支持一下吧!!!
在这里插入图片描述

相关文章:

【贪心算法篇】:“贪心”之旅--算法练习题中的智慧与策略(一)

✨感谢您阅读本篇文章&#xff0c;文章内容是个人学习笔记的整理&#xff0c;如果哪里有误的话还请您指正噢✨ ✨ 个人主页&#xff1a;余辉zmh–CSDN博客 ✨ 文章所属专栏&#xff1a;贪心算法篇–CSDN博客 文章目录 一.贪心算法1.什么是贪心算法2.贪心算法的特点 二.例题1.柠…...

AJAX XML

AJAX XML 引言 随着互联网技术的不断发展,Web应用对用户交互性和实时性的要求越来越高。AJAX(Asynchronous JavaScript and XML)技术的出现,为Web应用开发提供了强大的支持。AJAX技术允许Web应用在不重新加载整个页面的情况下,与服务器进行异步通信。XML作为数据传输格式…...

踏入编程世界的第一个博客

我&#xff0c;一个双非一本大一新生&#xff0c;普通的不能再普通了&#xff0c;面对宏伟庞大的计算机世界仍显得举手无措&#xff0c;我自以为自身仍有些许骨气&#xff0c;不想普普通通&#xff0c;甚是浑浑噩噩的度过四年大学&#xff0c;经历了高考的打击&#xff0c;双非…...

2025年1月22日(网络编程 udp)

系统信息&#xff1a; ubuntu 16.04LTS Raspberry Pi Zero 2W 系统版本&#xff1a; 2024-10-22-raspios-bullseye-armhf Python 版本&#xff1a;Python 3.9.2 已安装 pip3 支持拍摄 1080p 30 (1092*1080), 720p 60 (1280*720), 60/90 (640*480) 已安装 vim 已安装 git 学习…...

数据结构与算法之栈: LeetCode 641. 设计循环双端队列 (Ts版)

设计循环双端队列 https://leetcode.cn/problems/design-circular-deque/description/ 描述 设计实现双端队列。 实现 MyCircularDeque 类: MyCircularDeque(int k) &#xff1a;构造函数,双端队列最大为 k 。boolean insertFront()&#xff1a;将一个元素添加到双端队列头部…...

从零开始学 HTML:构建网页的基本框架与技巧

系列文章目录 01-从零开始学 HTML&#xff1a;构建网页的基本框架与技巧 文章目录 系列文章目录前言一、HTML 文档的基本框架1.1 <!DOCTYPE html>、<html>、<head>、<body> 标签解析1.1.1 <!DOCTYPE html> 标签1.1.2 <html> 标签1.1.3 &l…...

一些杂记2

1.#define 1.1定义 #define 是一个预处理指令&#xff0c;用于定义宏 宏&#xff0c;是预处理阶段&#xff08;在编译之前&#xff09;由预处理器处理的代码片段 1.2使用 1.2.1 #define 可以定义常量 #define PI 3.14159 1.2.2 #define 可以定义宏函数 #define SQUARE(x) ((…...

C语言 --- 分支

C语言 --- 分支 语句分支语句含义if...else语句单分支if语句语法形式 双分支 if-else 语句语法形式 悬空else含义问题描述 多分支 if-else 语句语法形式 switch...case语句含义语法形式 总结 &#x1f4bb;作者简介&#xff1a;曾与你一样迷茫&#xff0c;现以经验助你入门 C 语…...

【Numpy核心编程攻略:Python数据处理、分析详解与科学计算】2.10 ndarray内存模型:从指针到缓存优化

2.10 ndarray内存模型&#xff1a;从指针到缓存优化 目录 #mermaid-svg-p0zxLYqAnn59O2Xe {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-p0zxLYqAnn59O2Xe .error-icon{fill:#552222;}#mermaid-svg-p0zxLYqAnn59O…...

【Numpy核心编程攻略:Python数据处理、分析详解与科学计算】2.6 广播机制核心算法:维度扩展的数学建模

2.6 广播机制核心算法&#xff1a;维度扩展的数学建模 目录/提纲 #mermaid-svg-IfELXmhcsdH1tW69 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-IfELXmhcsdH1tW69 .error-icon{fill:#552222;}#mermaid-svg-IfELXm…...

K8S极简教程(4小时快速学会)

1. K8S 概览 1.1 K8S 是什么 K8S官网文档&#xff1a;https://kubernetes.io/zh/docs/home/ 1.2 K8S核心特性 服务发现与负载均衡&#xff1a;无需修改你的应用程序即可使用陌生的服务发现机制。存储编排&#xff1a;自动挂载所选存储系统&#xff0c;包括本地存储。Secret和…...

系统URL整合系列视频二(界面原型)

视频 系统URL整合系列视频二&#xff08;界面原型&#xff09; 视频介绍 &#xff08;全国&#xff09;大型分布式系统Web资源URL整合需求界面原型讲解。当今社会各行各业对软件系统的web资源访问权限控制越来越严格&#xff0c;控制粒度也越来越细。安全级别提高的同时也增加…...

虚幻浏览器插件 UE与JS通信

温馨提示&#xff1a;本节内容需要结合插件Content下的2_Communication和Resources下的sample.html 一起阅读。 1. UE调用JS 1.1 JS脚本实现 该部分共两步: 导入jstote.js脚本实现响应函数并保存到 ue.interface 中 jsfunc 通过json对象传递参数&#xff0c;仅支持函数名小…...

OpenAI深夜反击:o3-mini免费上线,能否撼动DeepSeek的地位?

还在为寻找合适的 AI 模型而烦恼吗&#xff1f;chatTools 平台为您精选 o1、GPT4o、Claude、Gemini 等顶尖 AI 模型&#xff0c;满足您不同的 AI 应用需求。立即体验强大的 AI 能力&#xff01; 深夜反击&#xff0c;OpenAI祭出o3-mini 在DeepSeek异军突起&#xff0c;搅动AI行…...

Golang 应用的 Docker 部署方式介绍及使用详解

本文将介绍如何使用 Docker 部署一个基于 Go 语言的后台服务应用 godco&#xff0c;并介绍如何配置 MongoDB 数据库容器的连接&#xff0c;确保应用能够成功启动并连接到容器方式部署的mongoDB数据库。 前提条件 1.已安装 Docker/Podman 2.已安装 MongoDB 数据库容器&#xff…...

deep seek R1本地化部署及openAI API调用

先说几句题外话。 最近deep seek火遍全球&#xff0c;所以春节假期期间趁着官网优惠充值了deep seek的API&#xff0c;用openAI的接口方式尝试了下对deep seek的调用&#xff0c;并且做了个简单测试&#xff0c;测试内容确实非常简单&#xff1a;通过prompt提示词让大模型对用…...

力扣第435场周赛讲解

文章目录 题目总览题目详解3442.奇偶频次间的最大差值I3443.K次修改后的最大曼哈顿距离3444. 使数组包含目标值倍数的最少增量3445.奇偶频次间的最大差值 题目总览 奇偶频次间的最大差值I K次修改后的最大曼哈顿距离 使数组包含目标值倍数的最少增量 奇偶频次间的最大差值II …...

初入机器学习

写在前面 本专栏专门撰写深度学习相关的内容&#xff0c;防止自己遗忘&#xff0c;也为大家提供一些个人的思考 一切仅供参考 概念辨析 深度学习&#xff1a; 本质是建模&#xff0c;将训练得到的模型作为系统的一部分使用侧重于发现样本集中隐含的规律难点是认识并了解模型&…...

Signature

Signature 题目是&#xff1a; import ecdsaimport random​def ecdsa_test(dA,k):​sk ecdsa.SigningKey.from_secret_exponent(secexpdA,curveecdsa.SECP256k1)sig1 sk.sign(databHi., kk).hex()sig2 sk.sign(databhello., kk).hex()#不同的kr1 int(sig1[:64], 16)s1 i…...

93,【1】buuctf web [网鼎杯 2020 朱雀组]phpweb

进入靶场 页面一直在刷新 在 PHP 中&#xff0c;date() 函数是一个非常常用的处理日期和时间的函数&#xff0c;所以应该用到了 再看看警告的那句话 Warning: date(): It is not safe to rely on the systems timezone settings. You are *required* to use the date.timez…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

mac:大模型系列测试

0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何&#xff0c;是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试&#xff0c;是可以跑通文章里面的代码。训练速度也是很快的。 注意…...