当前位置: 首页 > 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题...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

Golang dig框架与GraphQL的完美结合

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

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...