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

力扣每日一题(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 <= 105
  • items[i].length == 2
  • items[i][0] == profiti
  • items[i][1] == categoryi
  • 1 <= profiti <= 109
  • 1 <= categoryi <= n
  • 1 <= k <= n

步骤

  1. 初始化变量

    • categorySet:用于记录当前子序列中出现的不同类别。

    • profit:记录当前子序列的总利润。

    • res:记录最大的优雅度。

    • st:用来记录那些在子序列中出现了多次的类别的项目的利润。

  2. 排序:首先按利润从高到低对项目进行排序。这样可以确保我们在选择前 k 个项目时,总利润是最大的。

  3. 遍历项目:对排序后的项目进行遍历。

    • 如果当前项目在前 k 个范围内(即子序列还没有达到长度 k):

      • 将其利润加入 profit

      • 将其类别加入 categorySet,如果类别已经存在,则将利润压入 st 堆栈中。

    • 如果当前项目在 k+1 项目之后(即子序列已经达到长度 k),并且 st 堆栈不为空,且当前项目的类别不在 categorySet 中:

      • st 中弹出一个利润最小的项目,用当前项目替换它,增加 profitcategorySet

  4. 计算优雅度:在每次更新 profitcategorySet 后,计算当前优雅度,并更新最大优雅度 res

主要逻辑解释

  1. 排序Arrays.sort(items, (item0, item1) -> item1[0] - item0[0]);

    • 这个步骤确保我们优先选择利润高的项目,以保证前 k 个项目的总利润最大。

  2. 前 k 项目

    if (i < k) {profit += items[i][0];if (!categorySet.add(items[i][1])) {st.push(items[i][0]);}
    • 对于前 k 个项目,直接将利润加入总利润 profit

    • 将项目的类别加入 categorySet,如果类别已经存在,则将利润压入 st 堆栈中。

  3. 替换逻辑

    else if (!st.isEmpty() && categorySet.add(items[i][1])) {profit += items[i][0] - st.pop();
    }
    • 对于第 k+1 项目之后的项目,如果 st 堆栈不为空,且当前项目的类别不在 categorySet 中:

      • st 中弹出一个利润最小的项目,并用当前项目替换它。这样确保增加新的类别,同时总利润减少最少。

  4. 计算优雅度

    res = Math.max(res, profit + (long)categorySet.size() * categorySet.size());
    • 每次更新 profitcategorySet 后,计算当前优雅度,并更新最大优雅度 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 的作用

  1. 记录重复类别的项目利润:当一个项目的类别在子序列中已经存在时,将其利润值记录到 st 中。这是因为这些项目不会增加不同类别的数量,但它们的利润可能在后续处理中被替换掉。

  2. 替换以增加不同类别的数量:在处理第 k+1 个及之后的项目时,如果当前项目的类别不在已选子序列的类别集合 categorySet 中,并且 st 不为空,可以将当前项目的利润与 st 中最小的利润值进行替换,从而增加不同类别的数量并尽量保持总利润的最大化。

详细解释

假设我们当前已经选择了前 k 个项目,这时 categorySet 中记录了这些项目的类别。如果其中某些类别重复了,那么这些重复类别项目的利润将被压入 st。当我们处理第 k+1 个及之后的项目时:

  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());
}
分步解释
  1. 处理前 k 个项目

    • profit += items[i][0];:将利润加到总利润中。

    • if (!categorySet.add(items[i][1])) { st.push(items[i][0]); }

      • 如果项目类别已经存在于 categorySet 中,将其利润值压入 st

  2. 处理第 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. 子序列最大优雅度

基于官方题解&#xff0c;进行补充说明 给你一个长度为 n 的二维整数数组 items 和一个整数 k 。 items[i] [profiti, categoryi]&#xff0c;其中 profiti 和 categoryi 分别表示第 i 个项目的利润和类别。 现定义 items 的 子序列 的 优雅度 可以用 total_profit distinct_…...

MySQL -- 优化

1. 查询优化 使用索引 示例&#xff1a;有一个包含数百万用户的表&#xff0c;名为 users&#xff0c;常见的查询是通过 email 字段查找用户。 CREATE INDEX idx_email ON users(email);通过创建索引 idx_email&#xff0c;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 超时设置详解

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

巴西:海外媒体投放,大舍传媒实现企业与巴西媒体间的交流

引言 随着全球化的进程&#xff0c;海外市场的开拓对于企业的发展至关重要。巴西作为南美洲最大的经济体和人口大国&#xff0c;具有巨大的商机。在与巴西媒体的交流中&#xff0c;大舍传媒的投放成为了一种高效的宣传和合作途径。 巴西媒体的多样性 巴西媒体以其丰富多样的…...

MT7981B+MT7976C+MT7531A RF定频测试方法

1、从下面网址下载QA软件包&#xff0c;然后在WIN系统下安装QA环境。 https://download.csdn.net/download/zhouwu_linux/89428691?spm1001.2014.3001.5501 在WINDOWS 7系统下先安装WinPcap_4_1_3.exe。 2、搭建硬件环境&#xff0c;电脑先连接仪器&#xff0c;主板网络与电…...

支持微信支付宝账单,极空间Docker部署一个开箱即用的私人账本『cashbook』

支持微信支付宝账单&#xff0c;Docker部署一个开箱即用的私人账本『cashbook』 哈喽小伙伴好&#xff0c;我是Stark-C~ 不知道屏幕前的各位富哥富姐们有没有请一个专业的私人财务助理管理自己的巨额资产&#xff0c;我不是给大家炫耀&#xff0c;我在月薪300的时候就已经有了…...

异常检测方法

1 异常检测方法适用范围 什么时候我们需要异常点检测算法呢&#xff1f;常用的有三种情况。 1.做数据预处理的时候需要对异常的数据做过滤&#xff0c;防止对归一化等处理的结果。2.对没有标记输出的特征数据做筛选&#xff0c;找出异常的数据。3.对有标记输出的特征数据做二…...

在网站建设时,如何选择适合自己的网站模版

可以根据以下几个地方选择适合的网站模板 1.公司的核心业务 根据公司的业务内容来确定网站展示的内容之一&#xff0c;不同的业务内容可以有不同的展示方式&#xff0c;以此来确定网站的展示风格之一&#xff0c;公司肯定是要有明确的业务内容&#xff0c;并且能够在网站…...

rabbitmq单机安装及性能测试

RabbitMQ单机安装及性能测试 本文使用CentOS7.9安装RabbitMQ单机环境&#xff0c;并进行性能测试。 1. 安装RabbitMQ RabbitMQ依赖Erlang&#xff0c;版本配套关系参考官网&#xff1a;https://www.rabbitmq.com/docs/which-erlang。 本文安装RabbitMQ3.8.21,Erlang版本要求…...

字节流和字符流的区别

字节流和字符流的区别 字节流 **数据单位&#xff1a;**Byte为单位进行数据传输和处理。 **应用场景&#xff1a;**适用于所有类型的文件&#xff0c;包括视频、视频、音频等二进制文件&#xff0c;以及文本文件。 比如InputStrem和子类&#xff08;FileInputStream&#x…...

【仿真建模-anylogic】EventRate原理解析

Author&#xff1a;赵志乾 Date&#xff1a;2024-06-13 Declaration&#xff1a;All Right Reserved&#xff01;&#xff01;&#xff01; 1. 类图 2. 原理解析 EventOriginator是Anylogic中各类事件的父类&#xff0c;对外暴露的接口主要有: 函数功能boolean isActive()判定…...

Linux安装Qt5.14.2

下载 qt 5.14.2下载网址 下载qt-opensource-linux-x64-5.14.2.run Linux系统下载.run文件&#xff08;runfile文件&#xff09;&#xff0c;windows系统下载.exe文件&#xff0c;mac系统下载.dmg文件。 md5sums.txt中是各个文件对应的MD5校验码。 验证MD5校验码 md5sum是li…...

Linux so文件无法找到及某条命令找不到的解决办法

前言 在一些定制软件中可能会自带so文件。或者自带一些二进制命令。 这时会如果运行某个程序会发生 **.so 文件无法找到的错误。 以及 * 某条命令无法找到的错误。 比如像是下面这样 解决办法&#xff1a; so文件无法找到 通过往 LD_LIBRARY_PATH 变量中追加路径来告诉程序…...

工业交换机的供电功率配置

在工业领域中&#xff0c;交换机作为网络设备中的重要组成部分&#xff0c;其供电功率配置必不可少。工业交换机的供电功率配置不仅关系到设备的稳定运行&#xff0c;还直接影响到整个工业生产系统的效率和安全性。因此&#xff0c;在选择工业交换机时&#xff0c;必须对供电功…...

实现一个vue js小算法 选择不同的时间段 不交叉

以上图片选择了时间段 现在需要判断 当前选择的时间段 不能够是 有交叉的所以现在需要循环判断 //判断时间段是否重叠交叉 export function areIntervalsNonOverlapping(intervals:any) {// 辅助函数&#xff1a;将时间字符串转换为从当天午夜开始计算的分钟数function conver…...

GStreamer安装——iOS

安装iOS开发 支持从iOS6开始的所有版本 先决条件 iOS开发需要下载Xcode和iOSSDK。Xcode 可以在App Store或 这里 iOSSDK&#xff0c;如果它还没有包含在您的Xcode版本中&#xff0c; 可以从下载选项卡下的Xcode首选项菜单下载。 最低要求iOS版本为6.0。的最低要求版本 Xcode…...

【云计算】Docker部署Nextcloud网盘并实现随地公网远程访问

配置文件 切换root权限&#xff0c;新建一个nextcloud的文件夹&#xff0c;进入该目录&#xff0c;创建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&#xff0c;右括号当成-1 那么只要任意前缀非负且最终总和为0那么该括号序列就是合法 对于本题&…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础

第三周 Day 3 &#x1f3af; 今日目标 理解类&#xff08;class&#xff09;和对象&#xff08;object&#xff09;的关系学会定义类的属性、方法和构造函数&#xff08;init&#xff09;掌握对象的创建与使用初识封装、继承和多态的基本概念&#xff08;预告&#xff09; &a…...

《Offer来了:Java面试核心知识点精讲》大纲

文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...

算法250609 高精度

加法 #include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; char input1[205]; char input2[205]; int main(){while(scanf("%s%s",input1,input2)!EOF){int a[205]…...

Java中HashMap底层原理深度解析:从数据结构到红黑树优化

一、HashMap概述与核心特性 HashMap作为Java集合框架中最常用的数据结构之一&#xff0c;是基于哈希表的Map接口非同步实现。它允许使用null键和null值&#xff08;但只能有一个null键&#xff09;&#xff0c;并且不保证映射顺序的恒久不变。与Hashtable相比&#xff0c;Hash…...