【2611. 老鼠和奶酪】
来源:力扣(LeetCode)
描述:
有两只老鼠和 n
块不同类型的奶酪,每块奶酪都只能被其中一只老鼠吃掉。
下标为 i 处的奶酪被吃掉的得分为:
- 如果第一只老鼠吃掉,则得分为
reward1[i]
。 - 如果第二只老鼠吃掉,则得分为
reward2[i]
。
给你一个正整数数组 reward1
,一个正整数数组 reward2
,和一个非负整数 k
。
请你返回第一只老鼠恰好吃掉 k
块奶酪的情况下,最大 得分为多少。
示例 1:
输入:reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2
输出:15
解释:这个例子中,第一只老鼠吃掉第 2 和 3 块奶酪(下标从 0 开始),第二只老鼠吃掉第 0 和 1 块奶酪。
总得分为 4 + 4 + 3 + 4 = 15 。
15 是最高得分。
示例 2:
输入:reward1 = [1,1], reward2 = [1,1], k = 2
输出:2
解释:这个例子中,第一只老鼠吃掉第 0 和 1 块奶酪(下标从 0 开始),第二只老鼠不吃任何奶酪。
总得分为 1 + 1 = 2 。
2 是最高得分。
提示:
- 1 <= n == reward1.length == reward2.length <= 105
- 1 <= reward1[i], reward2[i] <= 1000
- 0 <= k <= n
方法:贪心 + 排序
有 n 块不同类型的奶酪,分别位于下标 0 到 n − 1。下标 i 处的奶酪被第一只老鼠吃掉的得分为 reward1[i],被第二只老鼠吃掉的得分为 reward2[i]。
如果 n 块奶酪都被第二只老鼠吃掉,则得分为数组 reward2 的元素之和,记为 sum。如果下标 i 处的奶酪被第一只老鼠吃掉,则得分的变化量是 reward1[i] − reward2[i]。
创建长度为 n 的数组 diffs,其中 diffs[i] = reward1[i]−reward2[i]。题目要求计算第一只老鼠恰好吃掉 k 块奶酪的情况下的最大得分,假设第一只老鼠吃掉的 k 块奶酪的下标分别是 i1 到 ik,则总得分为:
其中 sum 为确定的值。根据贪心思想,为了使总得分最大化,应使下标 i1 到 ik 对应的 diffs 的值最大,即应该选择 diffs 中的 k 个最大值。
贪心思想的正确性说明如下:假设下标 i1 到 ik 对应的 diffs 的值不是最大的 k 个值,则一定存在下标 ij 和下标 p 满足 diffs[p] ≥ diffs[ij] 且 p 不在 i1 到 ik 的 k 个下标中,将 diffs[ij] 替换成 diffs[p] 之后的总得分不变或增加。因此使用贪心思想可以使总得分最大。
具体做法是,将数组 diffs 排序,然后计算 sum 与数组 diffs 的 k 个最大值之和,即为第一只老鼠恰好吃掉 k 块奶酪的情况下的最大得分。
代码:
class Solution {
public:int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {int ans = 0;int n = reward1.size();vector<int> diffs(n);for (int i = 0; i < n; i++) {ans += reward2[i];diffs[i] = reward1[i] - reward2[i];}sort(diffs.begin(), diffs.end());for (int i = 1; i <= k; i++) {ans += diffs[n - i];}return ans;}
};
执行用时:124ms, 在所有 C++ 提交中击败了69.45%的用户
内存消耗:101 MB, 在所有 C++ 提交中击败了82.99%的用户
复杂度分析
时间复杂度:O(nlogn),其中 n 是数组 reward1 和 reward2 的长度。创建数组 diffs 需要 O(n) 的时间,将数组 diffs 排序需要 O(nlogn) 的时间,排序后计算 diffs 的 k 个最大值之和需要 O(k) 的时间,其中 k ≤ n,因此时间复杂度是 O(nlogn)。
空间复杂度:O(n),其中 n 是数组 reward1 和 reward2 的长度。需要创建长度为 n 的数组 diffs 并排序,数组需要 O(n) 的空间,排序需要 O(logn) 的递归调用栈空间,因此空间复杂度是 O(n)。
方法二:贪心 + 优先队列
方法一当中,计算最大得分的做法是创建长度为 n 的数组 diffs,其中 diffs[i] = reward1[i] − reward2[i],将数组 diffs 排序之后计算 sum 与数组 diffs 的 k 个最大值之和。也可以使用优先队列存储数组 diffs 中的 k 个最大值,优先队列的队首元素为最小元素,优先队列的空间是 O(k)。
用 sum 表示数组 reward2 的元素之和。同时遍历数组 reward1 和 reward2,当遍历到下标 i 时,执行如下操作。
将 reward1[i] − reward2[i] 添加到优先队列。
如果优先队列中的元素个数大于 k,则取出优先队列的队首元素,确保优先队列中的元素个数不超过 k。
遍历结束时,优先队列中有 k 个元素,为数组 reward1 和 reward2 的 k 个最大差值。计算 sum 与优先队列中的 k 个元素之和,即为第一只老鼠恰好吃掉 k 块奶酪的情况下的最大得分。
代码:
class Solution {
public:int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {int ans = 0;int n = reward1.size();priority_queue<int, vector<int>, greater<int>> pq;for (int i = 0; i < n; i++) {ans += reward2[i];pq.emplace(reward1[i] - reward2[i]);if (pq.size() > k) {pq.pop();}}while (!pq.empty()) {ans += pq.top();pq.pop();}return ans;}
};
执行用时:152ms, 在所有 C++ 提交中击败了45.26%的用户
内存消耗:102.4 MB, 在所有 C++ 提交中击败了63.91%的用户
复杂度分析
时间复杂度:O(nlogk),其中 n 是数组 reward1 和 reward2 的长度,k 是第一只老鼠吃掉的奶酪块数。遍历两个数组的过程中,每个下标处的优先队列操作时间是 O(logk),共需要 O(nlogk) 的时间,遍历数组之后计算优先队列中的 k 个元素之和需要 O(klogk) 的时间,其中 k ≤ n,因此时间复杂度是 O(nlogk+klogk) = O(nlogk)。
空间复杂度:O(k),其中 k 是第一只老鼠吃掉的奶酪块数。优先队列需要 O(k) 的空间。
author:LeetCode-Solution
相关文章:

【2611. 老鼠和奶酪】
来源:力扣(LeetCode) 描述: 有两只老鼠和 n 块不同类型的奶酪,每块奶酪都只能被其中一只老鼠吃掉。 下标为 i 处的奶酪被吃掉的得分为: 如果第一只老鼠吃掉,则得分为 reward1[i] 。如果第二…...

Reid strong baseline 代码详解
本项目是对Reid strong baseline代码的详解。项目暂未加入目标检测部分,后期会不定时更新,请持续关注。 本相比Reid所用数据集为Markt1501,支持Resnet系列作为训练的baseline网络。训练采用表征学习度量学习的方式。 目录 训练参数 训练代…...

宝塔面板搭建网站教程:Linux下使用宝塔一键搭建网站,内网穿透发布公网上线
文章目录 前言1. 环境安装2. 安装cpolar内网穿透3. 内网穿透4. 固定http地址5. 配置二级子域名6. 创建一个测试页面 转载自cpolar内网穿透的文章:使用宝塔面板快速搭建网站,并内网穿透实现公网远程访问 前言 宝塔面板作为简单好用的服务器运维管理面板&…...

常微分方程(ODE)求解方法总结
常微分(ODE)方程求解方法总结 1 常微分方程(ODE)介绍1.1 微分方程介绍和分类1.2 常微分方程的非计算机求解方法1.3 线性微分方程求解的推导过程 2 一阶常微分方程(ODE)求解方法2.1 欧拉方法2.1.1 欧拉方法2…...
【华为OD机试】区间交集【2023 B卷|200分】
【华为OD机试】-真题 !!点这里!! 【华为OD机试】真题考点分类 !!点这里 !! 题目描述 给定一组闭区间,其中部分区间存在交集。 任意两个给定区间的交集,称为公共区间 (如:[1,2],[2,3]的公共区间为[2,2],[3,5],[3,6]的公共区间为[3,5])。 公共区间之间若存在交集,则需…...

Vue3 | Element Plus resetFields不生效
Vue3 | Element Plus resetFields不生效 1. 简介 先打开创建对话框没有问题,但只要先打开编辑对话框,后续在打开对话框就会有默认值,还无法使用resetFields()重置。 下面是用来复现问题的示例代码和示例GIF。 <script setup> import…...
机器视觉特点 机器视觉实际应用
机器视觉特点 1、机器视觉是一项综合技术,其中包括数字图像处理技术,机械工程技术,控制技术,电光源照明技术,光学成像技术,传感器技术,模拟与数字视频技术,计算机硬件技术ÿ…...

elementui大型表单校验
一般很大的表单都会被拆解开,校验,,不会写在一个页面,,就会有多个 el-form ,,主页要集合所有el-form的数据,,所以有一个map来接收,传送表单数据,&…...
Linux+Selenium
SeleniumLinux 开源社区已无CentOS7.0以下rpm维护。升级测试机器到CentOS7.X。 Selenium安装 python环境:pip3 install selenium 浏览器插件:http://chromedriver.storage.googleapis.com/index.html yum instlal google-chrome 使用以下命令确定是…...
2023-06-01 LeetCode每日一题(礼盒的最大甜蜜度)
2023-03-29每日一题 一、题目编号 二、题目链接 点击跳转到题目位置 三、题目描述 给你一个正整数数组 price ,其中 price[i] 表示第 i 类糖果的价格,另给你一个正整数 k 。 商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两…...
Spring架构篇--2.7.2 远程通信基础--Netty原理--ServerBootstrap
前言:已经初始化了NioEventLoopGroup 的boosGroup 和 workerGroup ,那么ServerBootstrap的作用是干嘛的呢 ,本文在Spring架构篇–2.7.1 远程通信基础–Netty原理–NioEventLoopGroup 之后继续进行探究 1 首先回顾下 nettt 的使用demo&#x…...
awk编辑器
文章目录 一.awk概述1.概述2.作用3.awk的工作过程4.awk 工作原理及命令格式5.awk的基本操作及其内置变量5.1 awk的-F操作5.2 awk的-v操作5.3 内置变量 二.awk 打印1.基本打印用法1.1 默认打印1.2打印文件内容 2.对行进行操作2.1 只打印行号(有多少行)2.2…...

DicomObjects.Core 3.0.17 Crack
DicomObjects.NET 核心版简介 DicomObjects.Core Assembly DicomObjects.NET 核心版简介 DicomObjects.Core 由一组相互关联但独立的 .核心兼容的“对象”,使开发人员能够快速轻松地将DICOM功能添加到其产品中,而无需了解或编程DICOM标准的复杂性。此帮助…...

电脑怎么通过网络传输文件?
可以通过网络在电脑之间传输文件吗? “由于天气的原因,我的老板决定让所有员工在家工作。但是我很多工作文件都在公司的电脑中,怎么才能将公司的文件远程传输到我家里的电脑上?电脑可以通过网络远程传输文件吗?” …...
人工智能之深度学习
第一章 人工智能概述 1.1人工智能的概念和历史 1.2人工智能的发展趋势和挑战 1.3人工智能的伦理和社会问题 第二章 数学基础 1.1线性代数 1.2概率与统计 1.3微积分 第三章 监督学习 1.1无监督学习 1.2半监督学习 1.3增强学习 第四章 深度学习 1.1神经网络的基本原理 1.2深度…...

性能测试设计阶段
性能测试设计阶段 性能测试是软件测试中的关键环节,它可以帮助我们评估软件系统在压力下的运行稳定性和性能表现。性能测试设计阶段是性能测试的基础,只有经过充分的设计,才能保证性能测试的有效性和准确性。 在性能测试设计阶段,…...
leetCode !! word break
方法一:字典树动态规划 首先,创建node类,每个对象应该包含:一个node array nexts(如果有通往’a’的路,那么对应的nexts[0]就不该为null); 一个boolean 变量(如果到达的这个字母恰好是字典中某个候选串的结尾,那么 标记…...

基础学习——关于list、numpy、torch在float和int等数据类型转换方面的总结
系列文章目录 Numpy学习——创建数组及常规操作(数组创建、切片、维度变换、索引、筛选、判断、广播) Tensor学习——创建张量及常规操作(创建、切片、索引、转换、维度变换、拼接) 基础学习——numpy与tensor张量的转换 基础学习…...
华纳云美国Linux服务器常用命令分享
美国Linux服务器系统目前也是跟Windows操作系统一样用户量非常多,其简单的纯命令操作模式可以节省很多系统空间,本文小编就来分享一些美国Linux服务器系统常用的命令,希望能够给刚入门的美国Linux服务器系统的用户提供一些操作参考。 1、系统…...
【minio】8.x版本与SpringBoot版本不兼容报错
错误异常: <minio.version>8.4.3</minio.version><spring-boot.version>2.6.13</spring-boot.version>Description:An attempt was made to call a method that does not exist. The attempt was made from the following location:io.min…...

.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...

(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

企业大模型服务合规指南:深度解析备案与登记制度
伴随AI技术的爆炸式发展,尤其是大模型(LLM)在各行各业的深度应用和整合,企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者,还是积极拥抱AI转型的传统企业,在面向公众…...
DAY 26 函数专题1
函数定义与参数知识点回顾:1. 函数的定义2. 变量作用域:局部变量和全局变量3. 函数的参数类型:位置参数、默认参数、不定参数4. 传递参数的手段:关键词参数5 题目1:计算圆的面积 任务: 编写一…...