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

【Leetcode】【每日一题】【简单】2558. 从数量最多的堆取走礼物

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/take-gifts-from-the-richest-pile/description/?envType=daily-question&envId=2023-10-28

给你一个整数数组 gifts ,表示各堆礼物的数量。每一秒,你需要执行以下操作:

  • 选择礼物数量最多的那一堆。
  • 如果不止一堆都符合礼物数量最多,从中选择任一堆即可。
  • 选中的那一堆留下平方根数量的礼物(向下取整),取走其他的礼物。

返回在 k 秒后剩下的礼物数量

示例 1:

输入:gifts = [25,64,9,4,100], k = 4
输出:29
解释: 
按下述方式取走礼物:
- 在第一秒,选中最后一堆,剩下 10 个礼物。
- 接着第二秒选中第二堆礼物,剩下 8 个礼物。
- 然后选中第一堆礼物,剩下 5 个礼物。
- 最后,再次选中最后一堆礼物,剩下 3 个礼物。
最后剩下的礼物数量分别是 [5,8,9,4,3] ,所以,剩下礼物的总数量是 29 。

示例 2:

输入:gifts = [1,1,1,1], k = 4
输出:4
解释:
在本例中,不管选中哪一堆礼物,都必须剩下 1 个礼物。 
也就是说,你无法获取任一堆中的礼物。 
所以,剩下礼物的总数量是 4 。

自己的思路

这道题目简单地来说,是给最小元素开平方,以示例1为例

先给数组gifts排序,给最后一个元素,即最大的元素开平方。循环4次。 

代码 

class Solution {public long pickGifts(int[] gifts, int k) {int len = gifts.length;for (int i = 0; i < k; i++) {Arrays.sort(gifts);gifts[len - 1] = (int) Math.sqrt(gifts[len -1]);}long res = 0;for (int i = 0; i < len; i++) {res += gifts[i];}return res;}
}

力扣官方题解

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/take-gifts-from-the-richest-pile/solutions/2477680/cong-shu-liang-zui-duo-de-dui-qu-zou-li-kt246/

 

最大堆

思想感觉和我的差不多,不同的是它使用了一个优先队列(PriorityQueue) pq,并且使用了一个自定义的比较器,将较大的礼物排在前面。而我每次都需要重新排序。

比较器

定义是在创建优先队列时传入的参数,也就是在创建 PriorityQueue<Integer> 对象时,通过 lambda 表达式来定义的比较器。

在这段代码中,比较器的定义使用了箭头函数 (a, b) -> b - a。箭头函数的左边是输入参数,即要比较的两个整数 a 和 b;箭头函数的右边是返回值,即要比较的结果。既然返回值是 a - b,那么比较器的规则就是按照从大到小的顺序对整数进行排序。

具体来说,当 a > b 时,a - b 的值为正数,返回值为正数,表示 a 在 b 的前面;当 a = b 时,a - b 的值为零,返回值为零,表示 a 和 b 相等,顺序不变;当 a < b 时,a - b 的值为负数,返回值为负数,表示 a 在 b 的后面。

因此,通过定义这个自定义的比较器,代码创建的优先队列 pq 会按照从大到小的顺序存储礼物的价值。这样,在每次取出最大值和加入平方根后的操作中,总是可以保证 pq 中的最大值是当前最有价值的礼物。

代码

class Solution {public long pickGifts(int[] gifts, int k) {PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);for (int gift : gifts) {pq.offer(gift);}while (k > 0) {k--;int x = pq.poll();pq.offer((int) Math.sqrt(x));}long res = 0;while (!pq.isEmpty()) {res += pq.poll();}return res;}
}

相关文章:

【Leetcode】【每日一题】【简单】2558. 从数量最多的堆取走礼物

力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台备战技术面试&#xff1f;力扣提供海量技术面试资源&#xff0c;帮助你高效提升编程技能&#xff0c;轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/take-gifts-from-the-richest-pi…...

LeetCode 每日一题 2023/10/23-2023/10/29

记录了初步解题思路 以及本地实现代码&#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 10/23 2678. 老人的数目10/24 1155. 掷骰子等于目标和的方法数10/25 2698. 求一个整数的惩罚数10/26 2520. 统计能整除数字的位数10/27 1465. 切割后面积最大的蛋糕10/28 2…...

Android:Installed Build Tools revision 33.0.2 is corrupted.

Remove and install again using the SDK Manager. 使用33.0.2及以上版本的build-tools编译Android应用时。 有些人会按照提示去SDK Manager中重新安装build tools&#xff0c;然后发现这样做是无用的 编译时会收到&#xff1a;Build-tool 33.0.2 is missing DX at D:\Sdk\b…...

语法复习之C语言与指针

内存是如何存储数据的&#xff1f; 在C语言中定义一个变量后&#xff0c;系统就会为其分配内存空间。这个内存空间包括了地址和长度。将变量赋值后&#xff0c;该值就被写入到了指定的内存空间中。内存空间的大小一般以字节作为基本单位。   普通变量存放的是数据&#xff0c…...

vue笔记(二)

7、事件处理 7.1、事件的基本处理 事件的使用 使用v-on&#xff1a;xxx或者用xxx绑定事件&#xff0c;其中XXX是事件名事件的回调需要配置在methods对象中&#xff0c;最终出现在VM上methods配置的函数&#xff0c;不需要箭头函数 <div id"root"><h1>…...

【IT行业就业前景广阔:探讨热门方向与就业机会】

IT行业哪个方向比较好就业? IT行业是一个快速发展的领域&#xff0c;与许多其他行业紧密结合&#xff0c;为各个行业带来了巨大的变革和机遇。在这个充满活力的行业中&#xff0c;有许多就业方向可以选择。让我们一起来探讨一下IT行业的发展背景、就业方向以及分享一些就业经…...

linux上java -jar方式运行项目及输出文件nohup.out的清理, linux上定时器的用法

linux上java -jar方式运行项目及输出文件nohup.out的清理&#xff0c; linux上定时器的用法 linux上java -jar方式运行定期自动清理nohup.out文件的内容**验证**定时器crontab使用时注意事项 linux上java -jar方式运行 参考&#xff1a;https://blog.csdn.net/qq_42169450/arti…...

macOS 12 Monterey v12.7.1正式版:开启全新的操作系统体验

macOS 12 Monterey已经向所有兼容的Mac设备推出&#xff0c;为您带来了一系列强大的新功能和改进。这个全新的操作系统版本&#xff0c;不仅带来了更流畅的用户体验&#xff0c;还增强了与iOS设备的无缝集成&#xff0c;让您的设备使用更加高效&#xff0c;更加便捷。 macOS 1…...

vue制作防止用户未登录或未填写信息就跳转页面的路由拦截器

在Vue中&#xff0c;你可以使用路由导航守卫来实现防止未登录用户跳转页面的路由拦截器。 首先&#xff0c;你需要创建一个全局前置守卫&#xff0c;用于检查用户是否已登录。在router/index.js文件中&#xff0c;添加如下代码&#xff1a; import router from /router;route…...

postgis ST_CoverageInvalidEdges用法

官方文档 概要 geometry ST_CoverageInvalidEdges(geometry winset geom, float8 tolerance 0); 描述 一个窗口函数&#xff0c;用于检查窗口分区中的多边形是否形成有效的多边形覆盖范围。 它返回线性指示器&#xff0c;显示每个多边形中无效边&#xff08;如果有&#x…...

sqlalchemy的部分函数合集

func.concat func.group_concat func.find_in_set func.sum func.left func.month func.round func.avg func.rpad func.ifnull func.replace func.date_format CONCAT 函数&#xff1a;将两个或多个字符串连接在一起。例如&#xff1a; SELECT CONCAT(Hello, , World) AS r…...

mac苹果电脑使用日常

让鼠标和触摸板滚动方向一致&#xff1a;使用 Scroll Reverser 软件。 参考&#xff1a;Mac上鼠标滚轮方向是和Win相反的&#xff0c;系统中设置后触摸板的方向又跟着变了 操作&#xff1a; 截屏&#xff1a;shift command 3 复制粘贴&#xff1a;cmdc cmdv 剪切粘贴&#x…...

多线程面试相关知识点

文章目录 (一) 进程线程和协程的区别创建线程的4种方式1. 继承Thread类2. 实现runnable接口3. 实现Callable接口4. 线程池创建 runnable 和 callable 有什么区别线程的 run()和 start()有什么区别&#xff1f;线程之间的状态变化notify()和 notifyAll()有什么区别&#xff1f;j…...

关于生成式人工智能模型应用的调研

本系列博文为深度学习/计算机视觉论文笔记&#xff0c;转载请注明出处 标题&#xff1a;A survey of Generative AI Applications 链接&#xff1a;https://arxiv.org/abs/2306.02781 摘要 生成式人工智能&#xff08;Generative AI&#xff09;近年来经历了显著的增长&…...

【问题】在安装torchvision的时候,会自动安装torch?

1 背景&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; 在使用如下命令安装torchvision的时候&#xff0c;发现之前已安装的torch被卸载了。 pip install torchvision -i https://pypi.tuna.tsinghua.edu.cn/simple 2 分析&#x1f430;&a…...

MySQL数据库备份实战

一、为什么进行数据库备份? 保证业务连续性:数据库中存储着企业的核心业务数据,如果数据丢失或损坏,将会对企业的业务运营产生重大影响。通过定期备份数据库,可以在系统故障或数据丢失时快速恢复数据,保证业务的连续性。 保护数据资产:数据库中存储着企业的重要数据资产…...

每日一题 2558. 从数量最多的堆取走礼物(简单,heapq)

怎么这么多天都是简单题&#xff0c;不多说了 class Solution:def pickGifts(self, gifts: List[int], k: int) -> int:gifts [-gift for gift in gifts]heapify(gifts)for i in range(k):heappush(gifts, -int(sqrt(-heappop(gifts))))return -sum(gifts)...

JavaScript中的Promise

JavaScript中的Promise是一种异步编程的解决方案&#xff0c;它可以避免回调地狱&#xff0c;使代码更加简洁和易于维护。本文将详细介绍Promise的API及其使用案例&#xff0c;并附有代码注释。 Promise的API Promise构造函数 Promise构造函数用于创建一个Promise实例&#…...

【OpenCV实现图像的几何变换】

文章目录 概要&#xff1a;OpenCV实现图像的几何变换、图像阈值和平滑图像变换小结 概要&#xff1a;OpenCV实现图像的几何变换、图像阈值和平滑图像 使用OpenCV库进行图像处理的三个重要主题&#xff1a;几何变换、图像阈值处理以及图像平滑。在几何变换部分&#xff0c;详细…...

2023MathorCup(妈妈杯) 数学建模挑战赛 解题思路

云顶数模最新解题思路免费分享~~ 2023妈妈杯数学建模A题B题思路&#xff0c;供大家参考~~ A题 B题...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

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

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

React父子组件通信:Props怎么用?如何从父组件向子组件传递数据?

系列回顾&#xff1a; 在上一篇《React核心概念&#xff1a;State是什么&#xff1f;》中&#xff0c;我们学习了如何使用useState让一个组件拥有自己的内部数据&#xff08;State&#xff09;&#xff0c;并通过一个计数器案例&#xff0c;实现了组件的自我更新。这很棒&#…...

CppCon 2015 学习:Reactive Stream Processing in Industrial IoT using DDS and Rx

“Reactive Stream Processing in Industrial IoT using DDS and Rx” 是指在工业物联网&#xff08;IIoT&#xff09;场景中&#xff0c;结合 DDS&#xff08;Data Distribution Service&#xff09; 和 Rx&#xff08;Reactive Extensions&#xff09; 技术&#xff0c;实现 …...

【仿生机器人】刀剑神域——爱丽丝苏醒计划,需求文档

仿生机器人"爱丽丝"系统架构设计需求文档 一、硬件基础 已完成头部和颈部硬件搭建 25个舵机驱动表情系统 颈部旋转功能 眼部摄像头&#xff08;视觉输入&#xff09; 麦克风阵列&#xff08;听觉输入&#xff09; 颈部发声装置&#xff08;语音输出&#xff09…...

5. TypeScript 类型缩小

在 TypeScript 中&#xff0c;类型缩小&#xff08;Narrowing&#xff09;是指根据特定条件将变量的类型细化为更具体的过程。它帮助开发者编写更精确、更准确的代码&#xff0c;确保变量在运行时只以符合其类型的方式进行处理。 一、instanceof 缩小类型 TypeScript 中的 in…...