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

LCP 30. 魔塔游戏 - 力扣(LeetCode)

题目描述

小扣当前位于魔塔游戏第一层,共有 N 个房间,编号为 0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于数组 nums,其中正数表示道具补血数值,即血量增加对应数值;负数表示怪物造成伤害值,即血量减少对应数值;0 表示房间对血量无影响。

小扣初始血量为 1,且无上限。假定小扣原计划按房间编号升序访问所有房间补血/打怪,为保证血量始终为正值,小扣需对房间访问顺序进行调整,每次仅能将一个怪物房间(负数的房间)调整至访问顺序末尾。请返回小扣最少需要调整几次,才能顺利访问所有房间。若调整顺序也无法访问完全部房间,请返回 -1。

题目示例

输入:nums = [100,100,100,-250,-60,-140,-50,-50,100,150]
输出:1
解释:初始血量为 1。至少需要将 nums[3] 调整至访问顺序末尾以满足要求。

解题思路

思路

我们按照原计划访问所有房间。当访问到第 i 个房间时,如果生命值小于等于 0,那么我们必须要对房间顺序进行调整:

显然选择第 i 个房间之后的房间是没有意义的,它并不会改变当前的生命值;

因此我们只能选择第 i 个房间及之前的房间。对于所有可选的房间,无论将哪个房间调整至末尾,都不会改变最终的生命值(因为数组 nums 的和不会变化)。由于我们希望调整的次数最少,因此应当贪心地选择最小的那个 nums[j] 调整至末尾,使得当前的生命值尽可能高。

算法

在遍历房间的过程中,如果 nums[i] 为负数,我们将其放入一个小根堆(优先队列)中。当计算完第 i 个房间的生命值影响后,如果生命值小于等于 0,那么我们取出堆顶元素,表示将该房间调整至末尾,并将其补回生命值中。由于一定会从小根堆中取出一个小于等于 nums[i] 的值,因此调整完成后,生命值一定大于 0。

当所有房间遍历完成后,我们还需要将所有从堆中取出元素的和重新加入生命值,如果生命值小于等于 0,说明无解。

参考代码

class Solution {public int magicTower(int[] nums) {// 建立小根堆,使得每次取都取最小值PriorityQueue<Integer> pq = new PriorityQueue<>();int ans = 0;            // 记录调整次数long hp = 1, delay = 0; // 记录当前血量 和 延迟掉血量// 从头开始遍历for(int i = 0; i < nums.length; i++) {// 遇到正数,血量直接相加if(nums[i] > 0) {hp += nums[i];// 遇到负数相加之后,血量相加,将负数血量放到小根堆} else if(nums[i] < 0) {hp += nums[i];pq.offer(nums[i]);// 看是否比0小,如果小于0,将之前最大的负数放到后面if(hp <= 0) {ans++;int curr = pq.poll();hp -= curr;delay += curr;}}}hp += delay;return hp <= 0 ? -1 : ans;}
}

相关文章:

LCP 30. 魔塔游戏 - 力扣(LeetCode)

题目描述 小扣当前位于魔塔游戏第一层&#xff0c;共有 N 个房间&#xff0c;编号为 0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于数组 nums&#xff0c;其中正数表示道具补血数值&#xff0c;即血量增加对应数值&#xff1b;负数表示怪物造成伤害值&#xff0c;即血量减…...

数据结构——单向链表和双向链表的实现(C语言版)

目录 前言 1. 链表 1.1 链表的概念及结构 1.2 链表的分类 2. 单链表接口实现 2.1 数据结构设计与接口函数声明 2.2 创建结点&#xff0c;打印&#xff0c;查找 2.3 尾插&#xff0c;头插&#xff0c;尾删&#xff0c;头删 2.4 插入或删除 2.4.1在指定位置后 2.4.2在…...

TCP和UDP相关问题(重点)(4)——4.使用TCP的协议有哪些?使用UDP的协议有哪些?

4.使用TCP的协议有哪些&#xff1f;使用UDP的协议有哪些&#xff1f; 使用TCP的协议有&#xff1a;HTTP3.0之前的HTTP协议、HTTPS、FTP、SMTP、SSH... 使用UDP的协议有&#xff1a;HTTP3.0、DNS、DHCP......

Python进阶--爬取美女图片壁纸(基于回车桌面网的爬虫程序)

目录 一、前言 二、爬取下载美女图片 1、抓包分析 a、分析页面 b、明确需求 c、抓包搜寻 d、总结特点 2、编写爬虫代码 a、获取图片页网页源代码 b、提取所有图片的链接和标题 c、下载并保存这组图片 d、 爬取目录页的各种类型美女图片的链接 e、实现翻页 三、各…...

[office] excel如何计算毛重和皮重的时间间隔 excel计算毛重和皮重时间间隔方法 #笔记#学习方法

excel如何计算毛重和皮重的时间间隔 excel计算毛重和皮重时间间隔方法 在日常工作中经常会到用excel&#xff0c;有时需要计算毛重和皮重的时间间隔&#xff0c;具体的计算方式是什么&#xff0c;一起来了解一下吧 在日常工作中经常会到用excel&#xff0c;在整理编辑过磅数据…...

Pandas 对带有 Multi-column(多列名称) 的数据排序并写入 Excel 中

Pandas 从Excel 中读取带有 Multi-column的数据 正文 正文 我们使用如下方式写入数据&#xff1a; import pandas as pd import numpy as npdf pd.DataFrame(np.array([[10, 2, 0], [6, 1, 3], [8, 10, 7], [1, 3, 7]]), columns[[Number, Name, Name, ], [col 1, col 2, co…...

如何为Kafka加上账号密码(一)

Kafka认证基本概念 一直以来&#xff0c;我们公司内网的Kafka集群都是在裸奔&#xff0c;只要知道端口号&#xff0c;任何人都能连上集群操作一番。直到有个主题莫名消失&#xff0c;才引起我们的警觉&#xff0c;是时候该考虑为它添加一套认证策略了。 认证和授权就是一对孪生…...

Elasticsearch的Index Lifecycle Management(ILM)

Elasticsearch的Index Lifecycle Management&#xff08;ILM&#xff09;功能提供了一种自动化管理索引生命周期的方式。ILM使得用户可以基于特定的条件&#xff08;如索引的年龄、大小等&#xff09;来自动执行如回滚、删除等操作&#xff0c;进而优化存储和提高查询性能。ILM…...

2、学习 Nacos 注册中心

学习 Nacos 注册中心 一、使用Nacos作为注册中心1、父pom.xml文件配置SpringCloudAlibaba的dependency-management依赖2、在微服务中添加Nacos客户端依赖3、配置Nacos服务地址 二、服务的分级存储模型1、配置实例的集群属性2、权重配置 三、命名空间 一、使用Nacos作为注册中心…...

Java 如何操作 nginx 服务器上的文件?

随着Java技术的不断发展&#xff0c;越来越多的开发人员开始使用Java来操作服务器上的文件。其中&#xff0c;如何操作nginx服务器上的文件也是许多Java开发人员所关注的重点之一。本文将介绍Java操作nginx服务器上文件的基本方法。 一、使用Java的File类 Java的File类可以用…...

时序预测 | MATLAB实现基于CNN-GRU-AdaBoost卷积门控循环单元结合AdaBoost时间序列预测

时序预测 | MATLAB实现基于CNN-GRU-AdaBoost卷积门控循环单元结合AdaBoost时间序列预测 目录 时序预测 | MATLAB实现基于CNN-GRU-AdaBoost卷积门控循环单元结合AdaBoost时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 1.MATLAB实现基于CNN-GRU-AdaBo…...

中创ET4410 台式LCR数字电桥 简单开箱测评

最近买了一台LCR电桥&#xff0c;完善一下自己实验室的设备&#xff0c;选了中创ET4410&#xff0c;这款性价比高一点。 1199元在PDD买的&#xff0c;好像胜利的VC4090C也是找中创代工的。 ET4410介绍 本系列LCR数字电桥是采用自动平衡电桥原理设计的元件参数分析仪&#xf…...

格式化dingo返回内容

dingo api返回的内容中添加code 和 message &#xff0c;保持与异常返回的内容格式相一致。 失败会存在code 和 message &#xff0c;我们只需要关注成功的情况 非分页返回&#xff0c;可以创建一个父类controller&#xff0c;通过调用sucess方法来返回 class Controller ext…...

QGIS编译(跨平台编译)之四十六:minizip编译(Windows、Linux、MacOS环境下编译)

文章目录 一、minizip介绍二、minizip下载三、Linux下编译四、MacOS下编译五、Windows下编译一、minizip介绍 Minizip 是一个用于处理 ZIP 文件的开源库,它基于 zlib 库构建。zlib 是一个广泛使用的、免费的、开源的压缩库,提供数据压缩和解压缩功能。Minizip 扩展了 zlib 的…...

MySQL进阶查询篇(1)-索引的类型与创建

MySQL数据库索引是提高查询效率的重要手段之一。索引是一种特殊的数据结构&#xff0c;用于快速定位数据。通过创建索引&#xff0c;可以大大提高查询性能&#xff0c;减少数据库的IO操作。 MySQL数据库支持多种不同类型的索引&#xff0c;常用的索引类型包括&#xff1a; B-…...

【STL】list模拟实现

vector模拟实现 一、接口大框架函数声明速览二、结点类的模拟实现1、构造函数 三、迭代器类的模拟实现1、迭代器类存在的意义2、迭代器类的模板参数说明3、构造函数4、运算符的重载&#xff08;前置和后置&#xff09;&#xff08;1&#xff09;前置&#xff08;2&#xff09;后…...

常用的文件系统、存储类型小整理

最近接触到了五花八门的文件系统、存储类型&#xff0c;名词听得头大&#xff0c;趁假期整理学习一番~ 名称OSSFastDFSJuiceFSCIFSCephFSEFSNFS全称Object Storage Service (对象存储服务)Fast Distributed File System (快速分布式文件系统)Juice File System (Juice 文件系统…...

Java写标准输出进度条

学Java这么久了&#xff0c;突发奇想写一个 进度条 玩玩&#xff0c;下面展示一下成功吧&#xff01; Java代码实现如下 public class ProcessBar {public static void main(String[] args) {//进度条StringBuilder processBarnew StringBuilder();//进度条长度int total100;/…...

leetcode 算法 69.x的平方根(python版)

需求 给你一个非负整数 x &#xff0c;计算并返回 x 的 算术平方根 。 由于返回类型是整数&#xff0c;结果只保留 整数部分 &#xff0c;小数部分将被 舍去 。 注意&#xff1a;不允许使用任何内置指数函数和算符&#xff0c;例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1&#…...

【golang】24、go get 和 go mod:indrect 与 go mod tidy

文章目录 go get 会执行如下操作&#xff1a; 操作 go.mod 文件&#xff08;add、update、remove&#xff09;下载依赖到 $GOPATH/pkg/mod 中若已安装&#xff0c;则更新该包&#xff0c;到最新版本 试验前置准备&#xff1a;首先删除已下载的依赖&#xff0c;rm -rf $GOPATH…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...