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

【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
解释:这个例子中,第一只老鼠吃掉第 23 块奶酪(下标从 0 开始),第二只老鼠吃掉第 01 块奶酪。
总得分为 4 + 4 + 3 + 4 = 1515 是最高得分。

示例 2:

输入:reward1 = [1,1], reward2 = [1,1], k = 2
输出:2
解释:这个例子中,第一只老鼠吃掉第 01 块奶酪(下标从 0 开始),第二只老鼠不吃任何奶酪。
总得分为 1 + 1 = 22 是最高得分。

提示:

  • 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,则总得分为:

1
其中 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. 老鼠和奶酪】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 有两只老鼠和 n 块不同类型的奶酪&#xff0c;每块奶酪都只能被其中一只老鼠吃掉。 下标为 i 处的奶酪被吃掉的得分为&#xff1a; 如果第一只老鼠吃掉&#xff0c;则得分为 reward1[i] 。如果第二…...

Reid strong baseline 代码详解

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

宝塔面板搭建网站教程:Linux下使用宝塔一键搭建网站,内网穿透发布公网上线

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

常微分方程(ODE)求解方法总结

常微分&#xff08;ODE&#xff09;方程求解方法总结 1 常微分方程&#xff08;ODE&#xff09;介绍1.1 微分方程介绍和分类1.2 常微分方程的非计算机求解方法1.3 线性微分方程求解的推导过程 2 一阶常微分方程&#xff08;ODE&#xff09;求解方法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. 简介 先打开创建对话框没有问题&#xff0c;但只要先打开编辑对话框&#xff0c;后续在打开对话框就会有默认值&#xff0c;还无法使用resetFields()重置。 下面是用来复现问题的示例代码和示例GIF。 <script setup> import…...

机器视觉特点 机器视觉实际应用

机器视觉特点 1、机器视觉是一项综合技术&#xff0c;其中包括数字图像处理技术&#xff0c;机械工程技术&#xff0c;控制技术&#xff0c;电光源照明技术&#xff0c;光学成像技术&#xff0c;传感器技术&#xff0c;模拟与数字视频技术&#xff0c;计算机硬件技术&#xff…...

elementui大型表单校验

一般很大的表单都会被拆解开&#xff0c;校验&#xff0c;&#xff0c;不会写在一个页面&#xff0c;&#xff0c;就会有多个 el-form &#xff0c;&#xff0c;主页要集合所有el-form的数据&#xff0c;&#xff0c;所以有一个map来接收&#xff0c;传送表单数据&#xff0c;&…...

Linux+Selenium

SeleniumLinux 开源社区已无CentOS7.0以下rpm维护。升级测试机器到CentOS7.X。 Selenium安装 python环境&#xff1a;pip3 install selenium 浏览器插件&#xff1a;http://chromedriver.storage.googleapis.com/index.html yum instlal google-chrome 使用以下命令确定是…...

2023-06-01 LeetCode每日一题(礼盒的最大甜蜜度)

2023-03-29每日一题 一、题目编号 二、题目链接 点击跳转到题目位置 三、题目描述 给你一个正整数数组 price &#xff0c;其中 price[i] 表示第 i 类糖果的价格&#xff0c;另给你一个正整数 k 。 商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两…...

Spring架构篇--2.7.2 远程通信基础--Netty原理--ServerBootstrap

前言&#xff1a;已经初始化了NioEventLoopGroup 的boosGroup 和 workerGroup &#xff0c;那么ServerBootstrap的作用是干嘛的呢 &#xff0c;本文在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 只打印行号&#xff08;有多少行&#xff09;2.2…...

DicomObjects.Core 3.0.17 Crack

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

电脑怎么通过网络传输文件?

可以通过网络在电脑之间传输文件吗&#xff1f; “由于天气的原因&#xff0c;我的老板决定让所有员工在家工作。但是我很多工作文件都在公司的电脑中&#xff0c;怎么才能将公司的文件远程传输到我家里的电脑上&#xff1f;电脑可以通过网络远程传输文件吗&#xff1f;” …...

人工智能之深度学习

第一章 人工智能概述 1.1人工智能的概念和历史 1.2人工智能的发展趋势和挑战 1.3人工智能的伦理和社会问题 第二章 数学基础 1.1线性代数 1.2概率与统计 1.3微积分 第三章 监督学习 1.1无监督学习 1.2半监督学习 1.3增强学习 第四章 深度学习 1.1神经网络的基本原理 1.2深度…...

性能测试设计阶段

性能测试设计阶段 性能测试是软件测试中的关键环节&#xff0c;它可以帮助我们评估软件系统在压力下的运行稳定性和性能表现。性能测试设计阶段是性能测试的基础&#xff0c;只有经过充分的设计&#xff0c;才能保证性能测试的有效性和准确性。 在性能测试设计阶段&#xff0c;…...

leetCode !! word break

方法一&#xff1a;字典树动态规划 首先,创建node类&#xff0c;每个对象应该包含:一个node array nexts(如果有通往’a’的路&#xff0c;那么对应的nexts[0]就不该为null); 一个boolean 变量&#xff08;如果到达的这个字母恰好是字典中某个候选串的结尾&#xff0c;那么 标记…...

基础学习——关于list、numpy、torch在float和int等数据类型转换方面的总结

系列文章目录 Numpy学习——创建数组及常规操作&#xff08;数组创建、切片、维度变换、索引、筛选、判断、广播&#xff09; Tensor学习——创建张量及常规操作&#xff08;创建、切片、索引、转换、维度变换、拼接&#xff09; 基础学习——numpy与tensor张量的转换 基础学习…...

华纳云美国Linux服务器常用命令分享

美国Linux服务器系统目前也是跟Windows操作系统一样用户量非常多&#xff0c;其简单的纯命令操作模式可以节省很多系统空间&#xff0c;本文小编就来分享一些美国Linux服务器系统常用的命令&#xff0c;希望能够给刚入门的美国Linux服务器系统的用户提供一些操作参考。 1、系统…...

【minio】8.x版本与SpringBoot版本不兼容报错

错误异常&#xff1a; <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…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...

spring Security对RBAC及其ABAC的支持使用

RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型&#xff0c;它将权限分配给角色&#xff0c;再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...