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

贪心算法【1】

文章目录

    • 860. 柠檬水找零
      • 题目解析
      • 算法原理
      • 代码实现
      • 交换论证法
    • 2208. 将数组和减半的最少操作次数
      • 题目解析
      • 算法原理
      • 代码实现
      • 交换论证法
    • 179. 最大数
      • 题目解析
      • 算法原理
      • 代码实现

860. 柠檬水找零

题目链接:860. 柠檬水找零

题目解析

一杯柠檬水5块钱,每个顾客每次只能买一杯,支付的现金的面额有5块、10块、20块。

我们需要能够正确的找零,而且最开始我们手里没有钱。

如果遇上不能找零的,则返回false;如果从始至终能够正确找零,返回true。

  • bills:顾客支付的钱的面额

算法原理

分情况讨论:

  • 顾客给5块,收下

  • 顾客给10块,手上有5块,给5块,然后收下10块;没有返回false

  • 顾客给20块

    1. 给三张5块
    2. 给一张5块,一张10块

    此时这里就能体现贪心,5块钱可以在10块那里用,也可以在20块这里用,所以要尽可能保留5块钱。

    所以优先选择给一张5块和一张10块。

代码实现

class Solution {
public:bool lemonadeChange(vector<int>& bills){if(bills[0] != 5)   return false;//unordered_map<int, int> hash;int five = 0;int ten = 0;for(auto e : bills){if(e == 5)  five++;else if(e == 10){if(five == 0)   return false;five--;ten++;}else{if(five != 0 && ten != 0){five--;ten--;}else if(five >= 3){five -= 3;}else{return false;}}}return true;}
};

交换论证法

证明策略:交换论证法

假设贪心策略的结果是:a b c d e f;最优解是e b c d a f,需要证明在不破坏最优解最优性质的前提下,能够将最优解调整成贪心解。

这里唯一要考虑的就是顾客给20块钱,该如何找零:

  • 贪心策略,有10块和5块,肯定先将10块给出去
  • 最优解,可能是三个5块,也能是5块、10块各一张
    这里需要考虑不一样的情况,即最优解给的三张5块

此时就要看能不能将这种情况替换成贪心策略一模一样的,这里2种情况:

  • 10块钱后面没用上:此时可以直接将最优解的三张5块,换成一张10块和一张5块(因为这个10块钱不影响后续操作)
  • 10块钱有用上:依旧可以替换两张5块钱,两张5块钱后面也能抵一张10块钱

所以,不管是用或者不用,都能将最优解替换成贪心解。

2208. 将数组和减半的最少操作次数

题目链接:2208. 将数组和减半的最少操作次数

题目解析

给我们一个正整数数组nums,每次操作都能够从数组选一个数字,对其减半(后续还能继续操作这个数)

最后返回,将nums数组和至少减小一半的最小次数。

算法原理

最少操作次数,每次就挑选最大的,这就是我们的贪心策略。

由于要选择每次最大的元素,这需要用堆来辅助。

最大元素,大根堆。

代码实现

class Solution {
public:int halveArray(vector<int>& nums){double sum = 0;priority_queue<double> heap;for(auto e : nums){sum += e;heap.push(e);}double targer = sum / 2.0;int ret = 0;while(sum > targer){double n = heap.top();heap.pop();sum -= n;n /= 2.0;sum += n;ret++;heap.push(n);}return ret;}
};

交换论证法

这次还是一样,如果能将最优解不失最优性质的前提下将最优转换为贪心解,就能证明贪心策略是正确的。

image-20240927163356570

由于是贪心策略,到此处的时候x >= y,这里分2种情况:

  • x在最优解当中没有用过,此时x可以直接替换y,y比x小,x减半,效果更足
  • x在最优解后续操作使用过,此时也能替换,因为都是要使用的,先后顺序并没有关系,不会影响操作次数

此时不管怎样,都能进行替换。

179. 最大数

题目链接:179. 最大数

题目解析

给我们一个非负整数数组,让我们排列组合,找出最大的组合。

返回的是字符串,因为这个数字可能非常大。

算法原理

这个排列组合,差不多像排序:

  • 正常排序(升序):
    它的本质就是确定元素的先后顺序,谁在前谁在后
    规则:

    a > ba前 b后
    a = b都行
    a < bb前 a后
  • 本题也是确定元素的先后顺序,即找出排序规则即可

    ab > baa前 b后
    ab = ba都行
    ab < bab前 a后

    这里的贪心就体现在每次比较都确定最好的排序序列

代码实现

class Solution {
public:string largestNumber(vector<int>& nums){vector<string> str_nums;for(auto e : nums){str_nums.push_back(to_string(e));}sort(str_nums.begin(), str_nums.end(), [](const string &s1, const string &s2){return s1 + s2 > s2 + s1;});string ret;for(auto e : str_nums){ret += e;}if(ret[0] == '0') return "0";return ret;}
};

相关文章:

贪心算法【1】

文章目录 860. 柠檬水找零题目解析算法原理代码实现交换论证法 2208. 将数组和减半的最少操作次数题目解析算法原理代码实现交换论证法 179. 最大数题目解析算法原理代码实现 860. 柠檬水找零 题目链接&#xff1a;860. 柠檬水找零 题目解析 一杯柠檬水5块钱&#xff0c;每个…...

Python PPT合并与拆分 – 详解

目录 使用工具 Python 合并 PPT 合并多个PPT文档 合并每个PPT文档中的特定幻灯片 Python 拆分 PPT 按幻灯片数量拆分 按幻灯片范围拆分 按幻灯片内容拆分 按节 (Section) 拆分 在日常工作或学习中&#xff0c;我们经常需要对PPT文件进行调整&#xff0c;比如将多个PPT…...

JSX:JavaScript的XML

简介 JSX是一种JavaScript的语法扩展&#xff0c;它允许你在JavaScript代码中写类似于HTML的标记。它被React框架广泛使用&#xff0c;以声明式地描述UI组件。JSX最终会被编译成JavaScript对象。 为什么使用JSX&#xff1f; 可读性&#xff1a;JSX使得组件的结构更加清晰&am…...

SAP ABAP-日期格式问题 SAP内部错误,反序列化JSON字符串时发生异常 值 20241215 不是根据 ABAP 的 XML 格式的有效日期

SAP ABAP-日期格式问题 SAP内部错误,反序列化JSON字符串时发生异常 值 20241215 不是根据 ABAP 的 XML 格式的有效日期 在SAP内部用 YYYYMMDD没有问题 外部传入参数...

Golang学习笔记_05——延迟调用

Golang学习笔记_02——函数 Golang学习笔记_03——匿名函数和闭包 Golang学习笔记_04——递归函数 文章目录 延迟调用1. 延迟调用1.1 使用场景1.2 示例 2. panic2.1 使用场景2.2 示例 3. recover3.1 使用场景3.2 示例 源码 延迟调用 在Go语言中&#xff0c;延迟调用&#xff0…...

C++:异常(下)

异常上&#xff1a;C&#xff1a;异常&#xff08;上&#xff09;-CSDN博客 一&#xff1a;异常的重新抛出 大家看下面如果不在里面处理一下的话delete没有运行过。 #include<iostream> #include<string> using namespace std; double division(int a, int b) {if…...

从〇开始深度学习(番外)——下载包

从〇开始深度学习(番外)——下载包 文章目录 从〇开始深度学习(番外)——下载包写在前面正文 写在前面 《从〇开始深度学习&#xff08;番外&#xff09;》系列主要记录一些细碎知识点和技能&#xff0c;与主线并不冲突。如果主线笔记中用得到番外篇的知识或技能&#xff0c;会…...

云原生是什么

云原生是一种构建和运行应用程序的方法&#xff0c;它充分利用了云计算的优势。它不仅仅是指在云上运行应用程序&#xff0c;更重要的是指应用程序的设计、开发、部署和运维方式都充分考虑了云环境的特性&#xff0c;从而能够更好地利用云的弹性、可扩展性和灵活性。 更详细地…...

构建Modbus TCP写多个寄存器指令详解

构建Modbus TCP写多个寄存器指令详解 在Modbus TCP通信中&#xff0c;构建正确的指令对于实现设备间的数据交换至关重要。本文将详细解释如何构建一个Modbus TCP指令&#xff0c;用于向设备地址为1的从站&#xff0c;从地址200&#xff08;0xC8&#xff09;开始&#xff0c;连…...

热更新解决方案3 —— xLua

概述 xLua框架导入和AB包相关准备 xLua导入 其它的导入 C#调用Lua 1.Lua解析器 using System.Collections; using System.Collections.Generic; using UnityEngine; //引用命名空间 using XLua;public class Lesson1_LuaEnv : MonoBehaviour {// Start is called before the fi…...

【Linux】——权限

文章目录 权限的概念创建与删除普通用户普通用户与root用户的切换权限管理权限设置 文件掩码权限的作用粘滞位 权限的概念 在Linux系统中&#xff0c;存在两种主要用户类型&#xff0c;即超级用户root与普通用户。超级用户拥有极高的权限&#xff0c;可以在 Linux 统下执行几乎…...

elasticsearch 使用enrich processor填充数据

文章目录 使用 POST 请求手动插入用户数据1. 创建 Enrich Policy步骤 1.1: 创建 Enrich Policy步骤 1.2: 执行 Enrich Policy 2. 创建 Ingest Pipeline步骤 2.1: 创建 Ingest Pipeline步骤 2.2: 配置 Enrich Processor 参数 3. 使用 Ingest Pipeline步骤 3.1: 使用 Pipeline 进…...

etcd性能调优

性能指标 决定 etcd 性能的关键因素&#xff0c;包括&#xff1a; 延迟 (latency)&#xff1a;延迟是完成操作的时间。吞吐量 (throughput)&#xff1a;吞吐量是在某个时间期间之内完成操作的总数量。当 etcd 接收并发客户端请求时&#xff0c;通常平均延迟随着总体吞吐量增加…...

docker离线安装、linux 安装docker

之前写过一篇docker的离线安装&#xff0c;现在从头再看繁琐了&#xff0c;服务器换了&#xff0c;既然要重搭一遍就要改进一下了。下面步入正题&#xff1a; 1.下载离线软件包 https://download.docker.com/linux/static/stable/x86_64/docker-20.10.6.tgz 2.下载安装工具包…...

信息安全工程师-选择题考点总结

密码理论知识 基础理论 一个密码系统至少由明文、密文、加密算法、解密算法和密钥五个部分组成,而其安全性是由密钥决定的。 按照密钥特征的不同,密码体制分为:对称密码体制和非对称密码体制。 按照对明文加密方式的不同,密码体制分为:流密码和分组密码。 非对称密码体…...

【C++】四季分类题目分析与讨论

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 &#x1f4af;前言&#x1f4af;题目说明&#x1f4af;题目代码实现1.我的做法代码示例解析 2. 老师的类C解法代码示例解析 3. 老师的类C解法代码示例解析 4. 老师新增的基于if的解法代码示例解析 &#x…...

mysqlbinglog如何查看进度呢

要查看 MySQL binlog 的进度&#xff0c;通常是指查看 binlog 文件的当前位置&#xff0c;这对于了解复制进度或者进行恢复操作非常重要。以下是一些常用的方法和 SQL 语句来查看 binlog 进度&#xff1a; 查看当前 binlog 文件和位置&#xff1a; SHOW MASTER STATUS;这个命令…...

CSS系列(11)-- 滤镜与混合模式详解

前端技术探索系列&#xff1a;CSS 滤镜与混合模式详解 &#x1f3a8; 致读者&#xff1a;探索视觉效果的艺术 &#x1f44b; 前端开发者们&#xff0c; 今天我们将深入探讨 CSS 滤镜与混合模式&#xff0c;学习如何创建独特的视觉效果。 滤镜效果详解 &#x1f680; 基础滤…...

Cesium进阶教程——自定义图形、外观、绘图基础、现有着色器移植至Cesium、ShadowMapping、视频GIS、模型压平、卷帘

基础必看 WEBGL基础&#xff08;从渲染管线角度解读&#xff09; 参考路线 http://www.xt3d.online/tutorial/further/article.html 自定义图形 https://blog.csdn.net/m0_55049655/article/details/138908327 https://blog.csdn.net/m0_55049655/article/details/140306837 …...

搭建Tomcat(一)---SocketServerSocket

目录 引入1 引入2--socket 流程 Socket&#xff08;应用程序之间的通讯保障&#xff09; 网卡(计算机之间的通讯保障) 端口 端口号 实例 client端 解析 server端 解析 相关方法 问题1&#xff1a;ServerSocket和Socket有什么关系&#xff1f; ServerSocket Soc…...

Sublime Text 64位:前端及全栈开发利器

本文还有配套的精品资源&#xff0c;点击获取 简介&#xff1a;Sublime Text作为一款高效的文本编辑器&#xff0c;在前端网页开发领域受到广泛青睐&#xff0c;特别是其64位版本在处理大型项目和高内存需求的场景下表现出色。编辑器内置Emmet插件&#xff0c;提供代码高亮、…...

CNCF云原生生态版图-分类指南(一)- 观测和分析

CNCF云原生生态版图-分类指南&#xff08;一&#xff09;- 观测和分析 CNCF云原生生态版图-分类指南一、观测和分析&#xff08;Observability and Analysis&#xff09;&#xff08;一&#xff09;可观测性&#xff08;Observablility&#xff09;1. 是什么&#xff1f;2. 解决…...

Ubuntu本地快速搭建web小游戏网站,公网用户远程访问【内网穿透】

文章目录 前言1. 本地环境服务搭建2. 局域网测试访问3. 内网穿透3.1 ubuntu本地安装cpolar内网穿透3.2 创建隧道3.3 测试公网访问4. 配置固定二级子域名4.1 保留一个二级子域名4.2 配置二级子域名4.3 测试访问公网固定二级子域名前言 网:我们通常说的是互联网;站:可以理解成…...

VMware ubuntu12.04怎么设置静态IP联网

记得刚开始学习嵌入式就是从ubuntu12.04的环境开始学习的C语言&#xff0c;当时没有弄清楚怎么设置静态IP联网&#xff0c;现在写一篇文章。 1.首先&#xff0c;关闭ubuntu的网络&#xff1b; 2.电脑使用的是wifi,将VMware桥接到该网卡上&#xff1b; 3.在虚拟机设置里面选择桥…...

Qt WORD/PDF(一)使用 QtPdfium库实现 PDF 预览

文章目录 一、简介二、下载 QtPdfium三、加载 QtPdfium 动态库四、Demo 使用 关于QT Widget 其它文章请点击这里: QT Widget 姊妹篇: Qt WORD/PDF&#xff08;一&#xff09;使用 QtPdfium库实现 PDF 操作 Qt WORD/PDF&#xff08;二&#xff09;使用 QtPdfium库实现…...

UE5 C++ Subsystem 和 多线程

一.Subsystem先做一个简单的介绍&#xff0c;其实可以去看大钊的文章有一篇专门讲这个的。 GamePlay框架基础上的一个增强功能&#xff0c;属于GamePlay架构的范围。Subsystems是一套可以定义自动实例化和释放的类的框架。这个框架允许你从5类里选择一个来定义子类(只能在C定义…...

23.DDD与微服务

学习视频来源&#xff1a;DDD独家秘籍视频合集 https://space.bilibili.com/24690212/channel/collectiondetail?sid1940048&ctype0 文章目录 DDD与微服务的关系1. DDD可以用微服务实现&#xff0c;也可以不用微服务实现2. DDD是微服务拆分的必须参考项之一3. 微服务架构…...

vue3+ant design vue实现日期选择器不展示清除按钮

1、代码&#xff1a;只需设置:allowClear"false"即可 <a-date-pickerv-model:value"value1":disabledDate"disabledDate"change"queryRate":allowClear"false" />const disabledDate (current: Dayjs) > {// 获取…...

Amazon Bedrock与AWS服务的无缝集成,如何打造智能化应用

在AI和大数据飞速发展的今天&#xff0c;Amazon Bedrock作为AWS的一项新兴服务&#xff0c;正逐渐成为开发者和企业拥抱生成式AI的核心工具。那么&#xff0c;Amazon Bedrock与AWS其他服务结合&#xff0c;究竟能够带来哪些强大的应用场景呢&#xff1f;今天九河云就来和大家探…...

Rust之抽空学习系列(四)—— 编程通用概念(下)

Rust之抽空学习系列&#xff08;四&#xff09;—— 编程通用概念&#xff08;下&#xff09; 1、函数 函数用来对功能逻辑进行封装&#xff0c;能够增强复用、提高代码的可读 以下是函数的主要组成部分&#xff1a; 名称参数返回类型函数体 1.1、函数名称 在Rust中&…...

【Apache paimon】-- 集成 hive3.1.3 异常

目录 1、场景再现 Step1:在 hive cli beeline 执行创建 hive paimon 表 Step2:使用 insert into 写入数据 Step3:抛出异常 2、原因分析 Step1:在 yarn resource manager 作业界面查询 hive sql mr job 的 yarn log Step2:搜索job 使用的 zstd jar 版本 Step3:定…...

SpringCloud微服务实战系列:01让SpringCloud项目在你机器上运行起来

目录 项目选型 项目安装-本地运行起来 软件安装&#xff1a; 项目启动&#xff1a; 总结&答疑 项目选型 软件开发&#xff0c;基本上都不会从0开始&#xff0c;一般都是在其他项目或者组件的基础上进行整合优化迭代&#xff0c;站在巨人肩膀上才能看得更远&#xff0c…...

分布式锁【Redis场景分布式锁篇】

文章目录 1.Redis分布式锁2.分布式锁其它方案1.主动轮询型1.MySQL分布式锁2.Redis分布式锁 2.监听回调型1.Etcd2.Zookeeper 总结 1.Redis分布式锁 锁通常用来控制共享资源&#xff0c;比如一个进程内有多个线程竞争一个数据的使用权限&#xff0c;解决方式之一就是加锁。分布式…...

BGP协议

BGP&#xff08;Border Gateway Protocol&#xff0c;边界网关协议&#xff09;是一种用于在不同网络之间传输可达性信息的路由协议。它是互联网上使用的主要协议之一&#xff0c;用于连接不同的自治系统&#xff08;AS&#xff09;&#xff0c;即由单个实体控。边界网关协议_百…...

iframe webview打开外链内嵌video标签导致视频无法全屏展示

iframe webview打开外链内嵌video标签导致视频无法全屏展示 解决方法iframe 添加属性webview 添加属性 解决方法 iframe 添加属性 <iframe style"width: 100%;height: 100vh;" src"http://xxx.xxx........" allowfullscreen"true" w…...

学习日志024--opencv中处理轮廓的函数

目录 前言​​​​​​​ 一、 梯度处理的sobel算子函数 功能 参数 返回值 代码演示 二、梯度处理拉普拉斯算子 功能 参数 返回值 代码演示 三、Canny算子 功能 参数 返回值 代码演示 四、findContours函数与drawContours函数 功能 参数 返回值 代码演示 …...

【从零开始入门unity游戏开发之——C#篇05】转义字符、@处理多行文本或者不使用转义字符、随机数

文章目录 一、转义字符1、什么是转义字符&#xff1f;2、常见的转义字符3、总结 二、使用处理多行文本或者不使用转义字符1、多行字符串2、不使用转义字符 三、随机数1、Random.Next()生成随机整数示例&#xff1a;生成一个随机整数生成指定范围内的随机整数 2、Random.NextSin…...

PHP获取指定日期的下周日至下周六的日期(下周几的日期)

PHP获取指定日期的下周日至下周六的日期&#xff08;下周几的日期&#xff09; 在PHP中&#xff0c;可以使用strtotime()函数来获取指定日期的下周日至下周六的日期。 // 周天 sunday // 周一 monday // 周二 tuesday // 周三 wednesday // 周四 thursday // 周五 friday // …...

超越飞书钉钉:探索高效内部知识库平替方案与应用

在团队协作日益频繁的今天&#xff0c;飞书与钉钉作为两大主流的企业沟通与协作平台&#xff0c;广受企业青睐。然而&#xff0c;随着企业规模的扩大和知识的累积&#xff0c;单纯的沟通与协作已难以满足企业对知识管理与传承的需求。因此&#xff0c;寻找一款能够高效整合内部…...

3D相框案例讲解(详细)

前言 通过现阶段的学习&#xff0c;我们已经掌握了HTML&#xff0c;CSS和JS部分的相关知识点&#xff0c;现在让我们通过一篇案例&#xff0c;来巩固我们近期所学的知识点。 详细视频讲解戳这里 任务一 了解目标案例样式 1.1了解案例 3D相框 1.2 分析案例 首先我们看到一个…...

一、基于langchain使用Qwen搭建金融RAG问答机器人--技术准备

一,LangChain框架介绍 LangChain 框架是一个开源工具&#xff0c;通过为各种 LLM 提供通用接口来简化应用程序的开发流程&#xff0c;帮助开发者自由构建 LLM应用。 LangChain封装了很多组件&#xff0c;通过这些组件的组合可以构建多种类型的RAG应用。开发者可以直接将私有数…...

2024年全球安全光幕装置行业总体规模、主要企业国内外市场占有率及排名

根据研究团队调研统计&#xff0c;2023年全球安全光幕装置市场销售额达到了46亿元&#xff0c;预计2030年将达到70亿元&#xff0c;年复合增长率&#xff08;CAGR&#xff09;为6.4%&#xff08;2024-2030&#xff09;。中国市场在过去几年变化较快&#xff0c;2023年市场规模为…...

uniapp跨端适配—条件编译

在uniapp中&#xff0c;跨端适配是通过条件编译实现的。条件编译允许开发者根据不同的平台&#xff08;如iOS、Android、微信小程序、百度小程序等&#xff09;编写不同的代码。这样可以确保每个平台上的应用都能得到最优的性能和用户体验。 以下是uniapp中条件编译的基本语法…...

HTML、CSS表格的斜表头样式设置title 画对角线

我里面有用到layui框架的影响&#xff0c;实际根据你自己的框架来小调下就可以 效果如下 上代码 <!DOCTYPE html> <html lang"zh"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-wi…...

自动驾驶控制与规划——Project 2: 车辆横向控制

目录 零、任务介绍一、环境配置二、算法三、代码实现四、效果展示 零、任务介绍 补全src/ros-bridge/carla_shenlan_projects/carla_shenlan_stanley_pid_controller/src/stanley_controller.cpp中的TODO部分。 一、环境配置 上一次作业中没有配置docker使用gpu&#xff0c;…...

Docker的初识

目录 1. 容器技术发展史1.1 Jail 时代1.2 云时代1.3 云原生时代1.3.1 Google & Docker 竞争1.3.2 k8s 成为云原生事实标准 2. 虚拟化和容器化的概念2.1 什么是虚拟化、容器化2.2 为什么要虚拟化、容器化&#xff1f;2.3 虚拟化实现方式2.3.1 应用程序执行环境分层2.3.2 虚拟…...

R-Studio Technician,无网络负担地进行远程数据分析和数据恢复任务

对于数据恢复技术人员和技术支持团队来说&#xff0c;时间就是金钱。这不仅包括您在客户机器上花费的时间 - 还包括您往返公司办公室的时间&#xff0c;这可能会带来巨大的不便&#xff0c;特别是如果客户位于其他省市。电话支持通常不适用于需要数小时才能完成的复杂任务&…...

Couchbase的OLAP支持情况

Couchbase 是一个高性能的 NoSQL 数据库&#xff0c;主要用于在线事务处理&#xff08;OLTP&#xff09;场景&#xff0c;但它也提供了一些功能来支持在线分析处理&#xff08;OLAP&#xff09;需求。以下是 Couchbase 对 OLAP 支持的几个方面&#xff1a; 1. N1QL 查询语言 …...

路径规划之启发式算法之十六:和声搜索算法(Harmony Search, HS)

和声搜索算法(Harmony Search, HS)是一种新兴的启发式全局搜索算法,是一种模拟音乐家即兴演奏过程的群体智能优化算法。这种算法由Zong Woo Geem等人在2001年提出,灵感来源于音乐家在寻找和声时的创造性思维过程。HS算法通过模拟音乐家演奏音乐时的选择过程来寻找问题的最优…...

服务器---centos上安装docker并使用docker配置jenkins

要在 Docker 中安装 Jenkins 并进行管理,可以按照以下步骤操作: 1. 安装 Docker 首先,确保你的系统已经安装了 Docker。如果尚未安装,可以使用以下命令进行安装: 在 CentOS 上安装 Docker sudo yum install -y yum-utils sudo yum-config-manager --add-repo https://…...