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

算法记录 | Day35 贪心算法

860.柠檬水找零

思路:

只需要维护三种金额的数量,5,10和20。

有如下三种情况:

  • 情况一:账单是5,直接收下。
  • 情况二:账单是10,消耗一个5,增加一个10
  • 情况三:账单是20,优先消耗一个10和一个5,如果不够,再消耗三个5

账单是20的情况,优先消耗一个10和一个5

因为美元10只能给账单20找零,而美元5可以给账单10和账单20找零,美元5更万能!

所以局部最优:遇到账单20,优先消耗美元10,完成本次找零。全局最优:完成全部账单的找零。

class Solution:def lemonadeChange(self, bills: List[int]) -> bool:five = 0 ten = 0 twenty = 0for bill in bills:if bill == 5: five += 1if bill == 10: if five < 0: return Falseten += 1five -= 1if bill == 20:if ten > 0 and five > 0:twenty += 1ten -= 1five -=1elif five >= 3:twenty += 1five -= 3else:return Falsereturn True

406.根据身高重建队列

思路:

1.可以先确定身高维度。将数组按身高从高到低进行排序,身高相同的则按照 k值升序排列。这样排序之后可以确定目前对于第 j 个人来说,前面的 j - 1 个人肯定比他都高。

2.建立一个包含 n 个位置的空队列 queue,按照上边排好的顺序遍历,依次将其插入到第 kj位置上。最后返回新的队列。

406.根据身高重建队列

class Solution:def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:people.sort(key = lambda x: (-x[0],x[1] ))que = []for p in people:que.insert(p[1],p)return que

452. 用最少数量的箭引爆气球

思路:

按开始坐标升序排序需要考虑一种情况:有交集关系的区间中,有的区间结束位置比较早。比如 [0, 6] [1, 2] [4, 5]

,按照开始坐标升序排序的话,如下:

[0 . . . . . 6][1 2][4,5]

第一箭的位置需要进行迭代判断,取区间 [0, 6] [1, 2]中结束位置最小的位置,即arrow_pos = min(points[i][1], arrow_pos),然后再判断接下来的区间是否能够引爆。

而按照结束坐标排序的话,箭的位置一开始就确定了,不需要再改变和判断箭的位置,直接判断区间即可。

按开始位置排序

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:if not points:return Falsepoints.sort(key=lambda x:x[0])arow_pos = points[0][1]count = 1for i in range(len(points)):if arow_pos < points[i][0]:count += 1arow_pos = points[i][1]else:arow_pos = min(arow_pos, points[i][1])return count

按结束位置排序

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:if not points:return Falsepoints.sort(key=lambda x:x[1])arow_pos = points[0][1]count = 1for i in range(len(points)):if arow_pos < points[i][0]:count += 1arow_pos = points[i][1]return count

相关文章:

算法记录 | Day35 贪心算法

860.柠檬水找零 思路&#xff1a; 只需要维护三种金额的数量&#xff0c;5&#xff0c;10和20。 有如下三种情况&#xff1a; 情况一&#xff1a;账单是5&#xff0c;直接收下。情况二&#xff1a;账单是10&#xff0c;消耗一个5&#xff0c;增加一个10情况三&#xff1a;账…...

coinex // 撮合引擎 逻辑流程 (两种数据源 初始化源和前端源)

目录 1 生产者 数据源 1.1. match-server 一启动 初始化数据 自动查询数据库 查询level2要展示的数据 1.2 match-server接收 前端发给Exchange-server的数据 2. 将查询/接受的数据EntrustOrder 转成 Order 解耦 过滤掉不要的属性 3.Order转成 OrderEvent 4. 分配序号发布…...

CentOS7---部署LNMP数据存储到redis

一、部署LNMP及redis 1、部署LNMP&#xff0c;需要将 tengine-2.2.0.tar.gz 拷贝到虚拟机的 /root 目录下 步骤一&#xff1a;安装nginx 源码安装相关软件包 # pcre-devel做正则匹配&#xff0c;zlib-devel做数据压缩 [roottemplate ~]# yum -y install gcc pcre-devel zlib-de…...

Linux中的git命令行

Linux中的git命令行 目录 Linux中的git命令行引入1、Linux下的git工具起源2、gitee的使用.gitignore.git 3、git三板斧3.1 git add3.2 git commit3.3 git push 4、git操作4.1 查看提交日志4.2 查看状态4.3 远端同步4.4 删除文件4.5 修改文件名 引入 当多个开发者同时参与同一个…...

【C++】哈希表:开散列和闭散列

&#x1f4dd; 个人主页 &#xff1a;超人不会飞)&#x1f4d1; 本文收录专栏&#xff1a;《C的修行之路》&#x1f4ad; 如果本文对您有帮助&#xff0c;不妨点赞、收藏、关注支持博主&#xff0c;我们一起进步&#xff0c;共同成长&#xff01; 目录 前言一、基于哈希表的两个…...

C技能树:Hello World

Hello World 输出 "Hello, World!" 字符串&#xff0c;请选出错误答案。 小知识&#xff1a;Hello World究竟从何而来? Hello, World最早是由 Brian Kernighan 创建的。1978年&#xff0c;Brian Kernighan写了一本名叫《C程序设计语言》的编程书&#xff0c;在程…...

TryHackMe-Set(Windows渗透测试 | WinDefender免杀)

Set 您再次发现自己在Windcorp公司的内部网络上。上次你去那里的味道真好&#xff0c;你回来了 了解更多。 但是&#xff0c;这次他们设法保护了域控制器&#xff0c;因此您需要找到另一台服务器&#xff0c;并在第一次扫描时发现“Set”。 Set被用作开发人员的平台&#xf…...

信安大佬真的用kali吗?

Kali只是现在网络安全和kali比较火的一个操作系统 下面我为大家讲讲kali系统都有那些优点 Kali介绍Kali Linux是基于Debian的Linux发行版&#xff0c; 设计用于数字取证操作系统。面向专业的渗透测试和安全审计。 集成化&#xff1a;预装超过300个渗透测试工具兼容好&#x…...

禁用表单元素:Layui框架下的实践与技巧

引言 在日常的网页开发过程中&#xff0c;有时我们需要禁用表单元素&#xff0c;以防止用户在某些情况下进行输入或更改。在本文中&#xff0c;我们将介绍如何在Layui框架下使用JavaScript禁用表单元素&#xff0c;例如单选按钮&#xff08;radio&#xff09;、下拉列表&#…...

spring boot 访问HTML

HTML整合spring boot 简介默认文件路径访问自定义文件路径访问 或通过Controller控制器层跳转访问 简介 SpringBoot默认的页面映射路径&#xff08;即模板文件存放的位置&#xff09;为“classpath:/templates/*.html”。静态文件路径为“classpath:/static/”&#xff0c;其中…...

WPF教程(四)--Dispatcher

一、Dispatcher介绍 微软在WPF引入了Dispatcher&#xff0c;那么这个Dispatcher的主要作用是什么呢&#xff1f; 不管是WinForm应用程序还是WPF应用程序&#xff0c;实际上都是一个进程&#xff0c;一个进程可以包含多个线程&#xff0c;其中有一个是主线程&#xff0c;其余的是…...

ijkplayer 编译增加支持更多的音视频格式

ijkplayer是B站开源的一款基于ffmpeg的移动端播放器。但为了减少播放器的体积&#xff0c;很多音视频的格式播放默认都是不支持的&#xff0c;需要自己下载ijkplayer源码进行编译。这里以mac环境下android为例&#xff0c;简述ijkplayer的编译过程&#xff0c;以及为了支持更多…...

TOP命令显示完整命令行信息

TOP 在Linux系统中&#xff0c;可以使用top命令来查看系统的实时性能数据&#xff0c;包括CPU使用率、内存使用率、进程信息等。以下是top命令的常用选项&#xff1a; -d seconds&#xff1a;指定top命令的刷新时间&#xff0c;单位为秒。 -u username&#xff1a;只显示指定…...

Spring6从入门到精通 第一章 带你玩转Spring

这里写目录标题 一 Spring框架产生的原因二 Spring6配置的关键环节 一 Spring框架产生的原因 传统的JavaWeb存在着耦合度较高的问题&#xff0c;而且实现完整的的MVC三层架构&#xff0c;开发成本过大&#xff0c;因此出现了Spring这个轻量级的开发框架&#xff0c;相当于建筑里…...

Apache POI 实现用Java操作Excel完成读写操作

简介 Apache POI是一个用于操作Microsoft Office格式文件&#xff08;包括xls、docx、xlsx、pptx等&#xff09;的Java API库。POI全称为Poor Obfuscation Implementation&#xff0c;是Apache Software Foundation的一个开源项目。它提供了一组Java API&#xff0c;使得Java程…...

改善供应商关系的八种方法

与供应商保持良好关系的重要性有很多原因。最重要的是&#xff0c;它使每个人的日常工作更加愉快。它还可以为你获得更好的交易&#xff0c;有助于协作并增强商誉。 但是&#xff0c;每个供应商都是不同的&#xff0c;建立牢固的关系可能很棘手。本文将解释企业如何建立并操持…...

网络安全-CDN绕过寻找真实IP

网络安全-CDN绕过寻找真实IP CDN就是CDN加速&#xff0c;就是根据你的目标让你访问的更快 CDN CDN&#xff0c;即内容分发网络&#xff0c;主要解决因传输距离和不同运营商节点造成的网络速度性能低下的问题。说得简单点&#xff0c;就是一组在不同运营商之间的对接节点上的…...

牛客网 HJ28 素数伴侣【二分图匹配,匈牙利算法】困难

描述 若两个正整数的和为素数&#xff0c;则这两个正整数称之为“素数伴侣”&#xff0c;如2和5、6和13&#xff0c;它们能应用于通信加密。现在密码学会请你设计一个程序&#xff0c;从已有的 N &#xff08; N 为偶数&#xff09;个正整数中挑选出若干对组成“素数伴侣”&am…...

带你畅玩ChatGPT

ChatGPT出来很久了,最近不少朋友还是不太会使用ChatGPT体验与机器人进行聊天,我正好发现有种非常简单的方式帮助大家体验ChatGPT,且响应速度非常快,写代码能力也不错,现在推荐给大家,希望对大家有所帮助。 目录 一、下载专用浏览器 1.1 下载链接 1.2 安装浏览器 二、…...

ChatGPT探索系列之六:思考ChatGPT的未来发展趋势和挑战

文章目录 前言一、未来发展趋势1. ChatGPT重塑数据分析之道2. ChatGPT颠覆企业运用人工智能和机器学习的途径3. ChatGPT颠覆自动化商业流程4. ChatGPT引领企业决策迈向新纪元 二、ChatGPT掀开未来充满机遇和挑战的新篇章总结 前言 ChatGPT发展到目前&#xff0c;其实网上已经有…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...

从零开始了解数据采集(二十八)——制造业数字孪生

近年来&#xff0c;我国的工业领域正经历一场前所未有的数字化变革&#xff0c;从“双碳目标”到工业互联网平台的推广&#xff0c;国家政策和市场需求共同推动了制造业的升级。在这场变革中&#xff0c;数字孪生技术成为备受关注的关键工具&#xff0c;它不仅让企业“看见”设…...