力扣每日一题(2024-06-13)2813. 子序列最大优雅度
基于官方题解,进行补充说明
给你一个长度为
n的二维整数数组items和一个整数k。
items[i] = [profiti, categoryi],其中profiti和categoryi分别表示第i个项目的利润和类别。现定义
items的 子序列 的 优雅度 可以用total_profit + distinct_categories2计算,其中total_profit是子序列中所有项目的利润总和,distinct_categories是所选子序列所含的所有类别中不同类别的数量。你的任务是从
items所有长度为k的子序列中,找出 最大优雅度 。用整数形式表示并返回
items中所有长度恰好为k的子序列的最大优雅度。注意:数组的子序列是经由原数组删除一些元素(可能不删除)而产生的新数组,且删除不改变其余元素相对顺序。
示例 1:
输入:items = [[3,2],[5,1],[10,1]], k = 2 输出:17 解释: 在这个例子中,我们需要选出长度为 2 的子序列。 其中一种方案是 items[0] = [3,2] 和 items[2] = [10,1] 。 子序列的总利润为 3 + 10 = 13 ,子序列包含 2 种不同类别 [2,1] 。 因此,优雅度为 13 + 22 = 17 ,可以证明 17 是可以获得的最大优雅度。示例 2:
输入:items = [[3,1],[3,1],[2,2],[5,3]], k = 3 输出:19 解释: 在这个例子中,我们需要选出长度为 3 的子序列。 其中一种方案是 items[0] = [3,1] ,items[2] = [2,2] 和 items[3] = [5,3] 。 子序列的总利润为 3 + 2 + 5 = 10 ,子序列包含 3 种不同类别 [1, 2, 3] 。 因此,优雅度为 10 + 32 = 19 ,可以证明 19 是可以获得的最大优雅度。示例 3:
输入:items = [[1,1],[2,1],[3,1]], k = 3 输出:7 解释: 在这个例子中,我们需要选出长度为 3 的子序列。 我们需要选中所有项目。 子序列的总利润为 1 + 2 + 3 = 6,子序列包含 1 种不同类别 [1] 。 因此,最大优雅度为 6 + 12 = 7 。提示:
1 <= items.length == n <= 105items[i].length == 2items[i][0] == profitiitems[i][1] == categoryi1 <= profiti <= 1091 <= categoryi <= n1 <= k <= n
步骤
-
初始化变量:
-
categorySet:用于记录当前子序列中出现的不同类别。 -
profit:记录当前子序列的总利润。 -
res:记录最大的优雅度。 -
st:用来记录那些在子序列中出现了多次的类别的项目的利润。
-
-
排序:首先按利润从高到低对项目进行排序。这样可以确保我们在选择前 k 个项目时,总利润是最大的。
-
遍历项目:对排序后的项目进行遍历。
-
如果当前项目在前 k 个范围内(即子序列还没有达到长度 k):
-
将其利润加入
profit。 -
将其类别加入
categorySet,如果类别已经存在,则将利润压入st堆栈中。
-
-
如果当前项目在 k+1 项目之后(即子序列已经达到长度 k),并且
st堆栈不为空,且当前项目的类别不在categorySet中:-
从
st中弹出一个利润最小的项目,用当前项目替换它,增加profit和categorySet。
-
-
-
计算优雅度:在每次更新
profit和categorySet后,计算当前优雅度,并更新最大优雅度res。
主要逻辑解释
-
排序:
Arrays.sort(items, (item0, item1) -> item1[0] - item0[0]);-
这个步骤确保我们优先选择利润高的项目,以保证前 k 个项目的总利润最大。
-
-
前 k 项目:
if (i < k) {profit += items[i][0];if (!categorySet.add(items[i][1])) {st.push(items[i][0]);}-
对于前 k 个项目,直接将利润加入总利润
profit。 -
将项目的类别加入
categorySet,如果类别已经存在,则将利润压入st堆栈中。
-
-
替换逻辑:
else if (!st.isEmpty() && categorySet.add(items[i][1])) {profit += items[i][0] - st.pop(); }-
对于第 k+1 项目之后的项目,如果
st堆栈不为空,且当前项目的类别不在categorySet中:-
从
st中弹出一个利润最小的项目,并用当前项目替换它。这样确保增加新的类别,同时总利润减少最少。
-
-
-
计算优雅度:
res = Math.max(res, profit + (long)categorySet.size() * categorySet.size());-
每次更新
profit和categorySet后,计算当前优雅度,并更新最大优雅度res。
-
代码
class Solution {// 初始化变量Set<Integer> categorySet = new HashSet<>(); // 用于记录当前子序列中出现的不同类别long profit = 0; // 当前子序列的总利润long res = 0; // 记录最大的优雅度Deque<Integer> st = new ArrayDeque<>(); // 记录重复类别项目的利润public long findMaximumElegance(int[][] items, int k) {// 按利润从高到低排序Arrays.sort(items, (item0, item1) -> item1[0] - item0[0]);for (int i = 0; i < items.length; i++ ) {if (i < k) {// 在前 k 个项目中// 将项目的利润加入总利润profit += items[i][0];if (!categorySet.add(items[i][1])) {// 如果类别已经存在于 categorySet 中,将利润压入堆栈。以便后面替换st.push(items[i][0]);}} else if (!st.isEmpty() && categorySet.add(items[i][1])) {// 在第 k+1 项目及之后,并且当前项目的类别不在 categorySet 中// 且堆栈不为空时,进行替换操作// 用当前项目替换利润最小的重复类别项目profit += items[i][0] - st.pop();}// 计算当前优雅度并更新最大优雅度res = Math.max(res, profit + (long)categorySet.size() * categorySet.size());}// 返回最大优雅度return res;}
}
详解 st 队列
st 的作用是在处理项目时,用于记录那些在子序列中类别出现重复的项目的利润。具体来说,当 st 不为空且当前项目的类别与已选子序列中的所有类别都不相同时,可以通过从 st 弹出一个利润最小的项目,用当前项目替换它,从而增加不同类别的数量,并尽量减少总利润的减少。下面是更详细的解释:
st 的作用
-
记录重复类别的项目利润:当一个项目的类别在子序列中已经存在时,将其利润值记录到
st中。这是因为这些项目不会增加不同类别的数量,但它们的利润可能在后续处理中被替换掉。 -
替换以增加不同类别的数量:在处理第
k+1个及之后的项目时,如果当前项目的类别不在已选子序列的类别集合categorySet中,并且st不为空,可以将当前项目的利润与st中最小的利润值进行替换,从而增加不同类别的数量并尽量保持总利润的最大化。
详细解释
假设我们当前已经选择了前 k 个项目,这时 categorySet 中记录了这些项目的类别。如果其中某些类别重复了,那么这些重复类别项目的利润将被压入 st。当我们处理第 k+1 个及之后的项目时:
-
如果当前项目的类别不在
categorySet中,且st不为空:-
我们可以将
st中最小的利润值弹出,并用当前项目替换它。这样做有两个好处:-
增加不同类别的数量。
-
尽量减少总利润的减少,因为我们选择了
st中最小的利润值进行替换。
-
-
代码示例中的 st 用法
for (int i = 0; i < items.length; i++) {if (i < k) {profit += items[i][0];if (!categorySet.add(items[i][1])) {st.push(items[i][0]);}} else if (!st.isEmpty() && categorySet.add(items[i][1])) {profit += items[i][0] - st.pop();}res = Math.max(res, profit + (long)categorySet.size() * categorySet.size());
}
分步解释
-
处理前
k个项目:-
profit += items[i][0];:将利润加到总利润中。 -
if (!categorySet.add(items[i][1])) { st.push(items[i][0]); }:-
如果项目类别已经存在于
categorySet中,将其利润值压入st。
-
-
-
处理第
k+1个及之后的项目:-
else if (!st.isEmpty() && categorySet.add(items[i][1])) { profit += items[i][0] - st.pop(); }:-
如果当前项目的类别不在
categorySet中,且st不为空,弹出st中最小的利润值(假设st是一个优先队列,能够快速获得最小值),并用当前项目的利润替换它。
-
-
相关文章:
力扣每日一题(2024-06-13)2813. 子序列最大优雅度
基于官方题解,进行补充说明 给你一个长度为 n 的二维整数数组 items 和一个整数 k 。 items[i] [profiti, categoryi],其中 profiti 和 categoryi 分别表示第 i 个项目的利润和类别。 现定义 items 的 子序列 的 优雅度 可以用 total_profit distinct_…...
MySQL -- 优化
1. 查询优化 使用索引 示例:有一个包含数百万用户的表,名为 users,常见的查询是通过 email 字段查找用户。 CREATE INDEX idx_email ON users(email);通过创建索引 idx_email,SELECT * FROM users WHERE email exampleexample…...
学会python——密码校验(python实例三)
目录 1、认识Python 2、环境与工具 2.1 python环境 2.2 pycharm编译 3、纠正密码输入的格式问题 3.1 代码构思 3.2 代码示例 3.3 运行结果 4、总结 1、认识Python Python 是一个高层次的结合了解释性、编译性、互动性和面向对象的脚本语言。 Python 的设计具有很强的可…...
【Python】中的X[:,0]、X[0,:]、X[:,:,0]、X[:,:,1]、X[:,m:n]、X[:,:,m:n]和X[: : -1]
Python中 x[m,n]是通过numpy库引用数组或矩阵中的某一段数据集的一种写法,m代表第m维,n代表m维中取第几段特征数据。 通常用法: x[:,n]或者x[n,:] X[:,0]表示对一个二维数组,取该二维数组第一维中的所有数据,第二维中取第0个数据。 X[0,:]使用类比前者。 举例说明: x[:,0…...
【Java基础】OkHttp 超时设置详解
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...
巴西:海外媒体投放,大舍传媒实现企业与巴西媒体间的交流
引言 随着全球化的进程,海外市场的开拓对于企业的发展至关重要。巴西作为南美洲最大的经济体和人口大国,具有巨大的商机。在与巴西媒体的交流中,大舍传媒的投放成为了一种高效的宣传和合作途径。 巴西媒体的多样性 巴西媒体以其丰富多样的…...
MT7981B+MT7976C+MT7531A RF定频测试方法
1、从下面网址下载QA软件包,然后在WIN系统下安装QA环境。 https://download.csdn.net/download/zhouwu_linux/89428691?spm1001.2014.3001.5501 在WINDOWS 7系统下先安装WinPcap_4_1_3.exe。 2、搭建硬件环境,电脑先连接仪器,主板网络与电…...
支持微信支付宝账单,极空间Docker部署一个开箱即用的私人账本『cashbook』
支持微信支付宝账单,Docker部署一个开箱即用的私人账本『cashbook』 哈喽小伙伴好,我是Stark-C~ 不知道屏幕前的各位富哥富姐们有没有请一个专业的私人财务助理管理自己的巨额资产,我不是给大家炫耀,我在月薪300的时候就已经有了…...
异常检测方法
1 异常检测方法适用范围 什么时候我们需要异常点检测算法呢?常用的有三种情况。 1.做数据预处理的时候需要对异常的数据做过滤,防止对归一化等处理的结果。2.对没有标记输出的特征数据做筛选,找出异常的数据。3.对有标记输出的特征数据做二…...
在网站建设时,如何选择适合自己的网站模版
可以根据以下几个地方选择适合的网站模板 1.公司的核心业务 根据公司的业务内容来确定网站展示的内容之一,不同的业务内容可以有不同的展示方式,以此来确定网站的展示风格之一,公司肯定是要有明确的业务内容,并且能够在网站…...
rabbitmq单机安装及性能测试
RabbitMQ单机安装及性能测试 本文使用CentOS7.9安装RabbitMQ单机环境,并进行性能测试。 1. 安装RabbitMQ RabbitMQ依赖Erlang,版本配套关系参考官网:https://www.rabbitmq.com/docs/which-erlang。 本文安装RabbitMQ3.8.21,Erlang版本要求…...
字节流和字符流的区别
字节流和字符流的区别 字节流 **数据单位:**Byte为单位进行数据传输和处理。 **应用场景:**适用于所有类型的文件,包括视频、视频、音频等二进制文件,以及文本文件。 比如InputStrem和子类(FileInputStream&#x…...
【仿真建模-anylogic】EventRate原理解析
Author:赵志乾 Date:2024-06-13 Declaration:All Right Reserved!!! 1. 类图 2. 原理解析 EventOriginator是Anylogic中各类事件的父类,对外暴露的接口主要有: 函数功能boolean isActive()判定…...
Linux安装Qt5.14.2
下载 qt 5.14.2下载网址 下载qt-opensource-linux-x64-5.14.2.run Linux系统下载.run文件(runfile文件),windows系统下载.exe文件,mac系统下载.dmg文件。 md5sums.txt中是各个文件对应的MD5校验码。 验证MD5校验码 md5sum是li…...
Linux so文件无法找到及某条命令找不到的解决办法
前言 在一些定制软件中可能会自带so文件。或者自带一些二进制命令。 这时会如果运行某个程序会发生 **.so 文件无法找到的错误。 以及 * 某条命令无法找到的错误。 比如像是下面这样 解决办法: so文件无法找到 通过往 LD_LIBRARY_PATH 变量中追加路径来告诉程序…...
工业交换机的供电功率配置
在工业领域中,交换机作为网络设备中的重要组成部分,其供电功率配置必不可少。工业交换机的供电功率配置不仅关系到设备的稳定运行,还直接影响到整个工业生产系统的效率和安全性。因此,在选择工业交换机时,必须对供电功…...
实现一个vue js小算法 选择不同的时间段 不交叉
以上图片选择了时间段 现在需要判断 当前选择的时间段 不能够是 有交叉的所以现在需要循环判断 //判断时间段是否重叠交叉 export function areIntervalsNonOverlapping(intervals:any) {// 辅助函数:将时间字符串转换为从当天午夜开始计算的分钟数function conver…...
GStreamer安装——iOS
安装iOS开发 支持从iOS6开始的所有版本 先决条件 iOS开发需要下载Xcode和iOSSDK。Xcode 可以在App Store或 这里 iOSSDK,如果它还没有包含在您的Xcode版本中, 可以从下载选项卡下的Xcode首选项菜单下载。 最低要求iOS版本为6.0。的最低要求版本 Xcode…...
【云计算】Docker部署Nextcloud网盘并实现随地公网远程访问
配置文件 切换root权限,新建一个nextcloud的文件夹,进入该目录,创建docker-compose.yml [cpslocalhost ~]$ su root Password: 666666 [rootlocalhost cps]# ls Desktop Documents Downloads Music Pictures Public Templates Vide…...
贪心+构造,CF1153 C. Serval and Parenthesis Sequence
一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 Problem - 1153C - Codeforces 二、解题报告 1、思路分析 对于括号匹配问题我们经典做法是左括号当成1,右括号当成-1 那么只要任意前缀非负且最终总和为0那么该括号序列就是合法 对于本题&…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...
Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?
Pod IP 的本质与特性 Pod IP 的定位 纯端点地址:Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址(如 10.244.1.2)无特殊名称:在 Kubernetes 中,它通常被称为 “Pod IP” 或 “容器 IP”生命周期:与 Pod …...
加密通信 + 行为分析:运营商行业安全防御体系重构
在数字经济蓬勃发展的时代,运营商作为信息通信网络的核心枢纽,承载着海量用户数据与关键业务传输,其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级,传统安全防护体系逐渐暴露出局限性&a…...
ArcGIS Pro+ArcGIS给你的地图加上北回归线!
今天来看ArcGIS Pro和ArcGIS中如何给制作的中国地图或者其他大范围地图加上北回归线。 我们将在ArcGIS Pro和ArcGIS中一同介绍。 1 ArcGIS Pro中设置北回归线 1、在ArcGIS Pro中初步设置好经纬格网等,设置经线、纬线都以10间隔显示。 2、需要插入背会归线…...
