代码随想录|Day29|贪心04|860.柠檬水找零、406.根据身高重建队列、452.用最少数量的箭引爆气球

860.柠檬水找零

我们维护三种金额的数量:five,ten,twenty

有如下三种情况:

  • 账单是5:five + 1,无需找零
  • 账单是10:ten + 1,找零一张5元(five - 1)
  • 账单是20:twenty + 1,找零一张10元一张5元(ten - 1, five -1),或找零三张5元(five -3)

前两种情况都是固定策略,第三种情况存在两种策略。

如果账单是20,应该优先消耗一个10元一个5元,而不是三个5元。为什么?

因为10元只能用来给20元账单找零,而5元既可以给20元或10元账单找零。

5元更万能,因此使用贪心策略,优先消耗10元,可以给更多的账单找零。

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five, ten, twenty = 0, 0, 0
        
        for bill in bills:
            # 5元账单
            if bill == 5:
                five += 1
            # 10元账单
            elif bill == 10:
                ten += 1
                if five > 0:
                    five -= 1
                else:
                    return False
            # 20元账单
            elif bill == 20:
                twenty += 1
                # 优先使用10元找零
                if ten > 0 and five > 0:
                    ten -= 1
                    five -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False
        return True

406.根据身高重建队列

如果同时考虑两个属性 hk,那么很容易顾此失彼。

我们首先考虑身高属性 h,由于 k 描述的是前面有 k 个身高大于或等于 h 的人,因此更高的应该排在前面,我们按照身高 h 降序排序数组。对于身高相同的人,按照 k 升序排序。

接着考虑属性 k,我们将 k 当作索引,重新安排排序后的数组即可得到结果。举个例子,[5, 1],意味着此人之前有 1个 身高 不矮于5 的人,由于先前已经按照身高排序,因此此人应该被安插在 第二个 位置。

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # 排序
        # -x[0]:按照身高h降序排序
        # x[1]:如果身高h相同,按照人数k降序排列
        people.sort(key = lambda x: (-x[0], x[1]))
        res = []
        # 重建
        for p in people:
            # 以 k 为索引重建队列
            res.insert(p[1], p)
        return res

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

思路:按照左边界对数组进行排序,通过判断当前气球的左边界 是否大于 上一个气球的右边界来判断是否重叠。需要注意的是,存在2个甚至更多气球重叠的情况,因此每次发现重叠气球的情况时,我们需要寻找一个最优的射击位置:重叠气球中最小的右边界。

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        # 按左边界排序
        points.sort(key = lambda x: x[0])

        result = 1

        for i in range(1, len(points)):
            if points[i][0] > points[i-1][1]:
                result += 1
            # 寻找最优射击位置
            else:
                points[i][1] = min(points[i-1][1], points[i][1])
        return result

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/505384.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Eclipse EMF教程(上)

What every Eclipse developer should know about EMF 翻译自:https://eclipsesource.com/blogs/tutorials/emf-tutorial/ 本教程是对EMF的介绍,解释了EMF的基础知识。我们首先向您展示如何基于EMF构建一个非常简单的以数据为中心的应用程序&#xff0c…

MES_ENT_STD

生产执行系统(企业标准版)MES_ENT_STD ERP_ENT_STD_59438.ieqq.ent-CSDN博客 OAMS_ENT_STD-CSDN博客

分类预测 | MATLAB实现BO-CNN-LSTM贝叶斯优化卷积长短期记忆网络多输入分类预测

分类预测 | MATLAB实现BO-CNN-LSTM贝叶斯优化卷积长短期记忆网络多输入分类预测 目录 分类预测 | MATLAB实现BO-CNN-LSTM贝叶斯优化卷积长短期记忆网络多输入分类预测效果一览基本介绍模型搭建程序设计参考资料 效果一览 基本介绍 MATLAB实现BO-CNN-LSTM贝叶斯优化卷积长短期记…

主干网络篇 | 利用RT-DETR模型主干HGNet去替换YOLOv8的主干

前言:Hello大家好,我是小哥谈。众所周知,实时目标检测(Real-Time Object Detection)一直被YOLO系列检测器统治着,YOLO版本更是炒到了v9,前段时间百度飞桨的PaddleDetection团队发布了一个名为RT-DETR的检测器,宣告其推翻了YOLO对实时检测领域统治。论文标题很直接:《D…

WPF上使用MaterialDesign框架---下载与配置

一、介绍: Material Design语言的一些重要功能包括 系统字体Roboto的升级版本 ,同时颜色更鲜艳,动画效果更突出。杜拉特还简要谈到了新框架的一些变化。谷歌的想法是让谷歌平台上的开发者掌握这个新框架,从而让所有应用就有统一的…

Python 常用内置库 time库、random库、turtle库

文章目录 一、time库二、random库三、turtle库1. 绘制正方形2. 使用海龟对象绘制六边形3. 绘制多个起点相同大小不同起点的五角星4. 绘制多个图形和添加文字 提示:以下是本篇文章正文内容,下面案例可供参考 一、time库 time是最基础的时间处理库&#…

CAJViewer7.3 下载地址及安装教程

CAJViewer是中国学术期刊(CAJ)全文数据库的专用阅读软件。CAJViewer是中国知识资源总库(CNKI)开发的一款软件,旨在方便用户在线阅读和下载CAJ数据库中的学术论文、期刊和会议论文等文献资源。 CAJViewer具有直观的界面…

Kubernetes之Projected Volume

目录 四种Projected Volume Secret 使用方法 应用场景 示例 ConfigMap 使用方法 应用场景 示例 Downward API 使用方法 应用场景 示例 ServiceAccountToken 使用方法 应用场景 示例 在 Kubernetes 中,有几类特殊的 Volume,它们存在的意义不是为了存放容器里的…

深入探索位图技术:原理及应用

文章目录 一、引言二、位图(Bitset)基础知识1、位图的概念2、位图的表示3、位图操作 三、位图的应用场景1、数据查找与存储2、数据去重与排序 四、位图的实现 一、引言 位图,以其高效、简洁的特性在数据处理、存储和检索等多个领域发挥着举足…

抽象类和接口的简单认识

目录 一、抽象类 1.什么是抽象类 2.抽象类的注意事项 3.抽象类与普通类的对比 二、接口 1.接口的简单使用 2.接口的特性 3.接口的使用案例 4.接口和抽象类的异同 一、抽象类 所谓抽象类,就是更加抽象的类,也就是说,这个类不能具体描…

文献学习-23-MRM:用于遗传学医学图像预训练的掩码关系建模

MRM: Masked Relation Modeling for Medical Image Pre-Training with Genetics Authors: Qiushi Yang, Wuyang Li, Baopu Li, Yixuan Yuan Source: ICCV 2023 Abstract: 关于自动多模态医疗诊断的 ODERN 深度学习技术依赖于大量的专家注释,这既耗时又令人望而却…

【KingSCADA】播放语音

1.函数介绍 PlaySound(string strWaveFileName, int nMode);下面是官方帮助文档中的解释: 2.生成语音文件 3.使用脚本播放音频文件 将音频文件存放在工程目录下面,我存放在了…\Resources\文件夹下: 我简单的写了一个定时1分钟播放一次语…

【MATLAB源码-第23期】基于matlab的短时傅里叶STFT信号变换仿真,得到信号的时频曲线图。

操作环境: MATLAB 2022a 1、算法描述 短时傅里叶变换(Short-Time Fourier Transform,STFT)是傅里叶变换的一种扩展,用于分析信号在时域和频域上的变化。描述如下: 1. **时域与频域分析**: …

使用 Seq2Seq 模型进行文本摘要

目录 引言 1 导入数据集 2 清洗数据集 3 确定允许的最大序列长度 4 选择合理的文本和摘要 5 对文本进行标记 6 删除空文本和摘要 7 构建模型 7.1 编码器 7.2 解码器 8 训练模型 9 测试模型 10 注意 11 整体代码 引言 文本摘要是指在捕捉其本质的同时缩短长文本的…

windows平台虚拟机安装

windows平台虚拟机安装 1. 安装VMwareWorkstationPro 1.1 软件下载 官网下载 官网 百度网盘下载 版本 VMwareWorkstationPro16 链接:https://pan.baidu.com/s/1LidMxoM9e4a4CANixyRoyg?pwd1157 提取码:1157 1.2 软件安装 软件安装注意事项 软件…

Mamba和状态空间模型(SSM)的视觉指南:替代 Transformers 的语言建模方法

原文地址: A Visual Guide to Mamba and State Space Models 2024 年 2 月 19 日 论文地址:https://arxiv.org/pdf/2312.00752.pdf 这篇论文介绍了一种新型的线性时间序列模型Mamba,它通过选择性状态空间(Selective State Space…

详解CAS(Compare and swap)

一、什么是 CAS CAS: 全称Compare and swap,字⾯意思:”⽐较并交换“,⼀个 CAS 涉及到以下操作: 我们假设内存中的原数据V,旧的预期值A,需要修改的新值B。 比较 A 与 V 是否相等。(⽐较) 如果…

【A-013】基于SSH的共享单车管理系统/共享单车出租系统

【A-013】基于SSH的共享单车管理系统/共享单车出租系统 开发环境: Eclipse/MyEclipse、Tomcat8、Jdk1.8 数据库: MySQL 适用于: 课程设计,毕业设计,学习等等 系统介绍: 基于SSH开发的共享单车管理系统/…

python mysql错误如何处理

错误代码类型:pymysql.err.InternalError: (1054, "Unknown column jack in field list") import pymysql d_mysql {host: 127.0.0.1, port: 33333,user: *****,password: *****,db: *****,charset: utf8} conn pymysql.connect(**d_mysql) cur co…

Latex自学以及安装使用教程

你就按部就班的来,准没问题。 Step1:下载Tex live和Tex studio,安装教程参考自:LaTeX的安装教程(Texlive 2020 TeX studio) Step2: (非必要)vscodeLatex,参考自:使用VSCode编写LaTe…