力扣(LeetCode)2512. 奖励最顶尖的K名学生(C++)
优先队列+哈希集合+反向思维(或自定义排序)
模拟,请直接看算法思路:
两个哈希集合S1和S2, S1存正面词汇,S2存负面词汇;一个优先队列pq,pq存{score, id}键值对,即学生分数-学生id。
算法流程:
- 初始化S1和S2
- 遍历report,report里存的是句子,每个句子report[i]对应一个学生student_id[i]的评价,抠出句子的每个单词report[i][j],将单词分数(对照哈希集合)加给学生。上述流程确定了学生student_id[i]的分数,将学生分数加入优先队列。
- 记录前k个学生id,存入答案数组ans,ans即为所求。
请注意:优先队列默认大根堆,按fisrt成员从大到小排序;在first成员相等时,按照second成员从大到小排序。score是first成员,id是second成员,出现矛盾:当score相同时,题目要求id从小到大排序。解决方法:1. 将score变为负数,或将id变为负数。2. 自定义排序规则(优先队列);本题解将score变为负数,解决了矛盾。
class Solution {
public:vector<int> topStudents(vector<string>& positive_feedback, vector<string>& negative_feedback, vector<string>& report, vector<int>& student_id, int k) {// 哈希集合unordered_set<string> S1, S2;vector<int> ans = vector<int> (k, 0); // 保存答案的ans顺序priority_queue <pair<int, int>, vector<pair<int,int>>> pq; // 存{score, id}键值对。for (int i = 0; i < positive_feedback.size(); i ++) {S1.insert(positive_feedback[i]);}for (int i = 0; i < negative_feedback.size(); i ++) {S2.insert(negative_feedback[i]);}for (int i = 0; i < report.size(); i ++) {int j = 0; // 遍历report[i];int score = 0, id = student_id[i];while (j < report[i].size()) {string t = "";while (j < report[i].size() && report[i][j] != ' ') {t += report[i][j ++];}j ++;if (S1.count(t)) score -= 3; // 得分,数值变小else if (S2.count(t)) score ++; // 扣分,数值变大}pq.push({score, id});if (pq.size() > k) pq.pop();}int i = k - 1;while (i >= 0) { // while (pq.size() && i >= 0) {int id = pq.top().second;pq.pop();ans[i --] = id;}return ans;}
};
时间复杂度 O ( n l o g k ) O(nlogk) O(nlogk) : n n n是 r e p o r t report report的长度, k k k 是常数(奖励最顶尖的前k名学生),优先队列内部最多维护 k + 1 k+1 k+1名学生,一共 n n n名学生进一次优先队列,最多 n n n名学生出一次优先队列,时间复杂度 O ( n l o g k ) O(nlogk) O(nlogk)。
空间复杂度 O ( n ) O(n) O(n) : 两个哈希集合/ans数组的空间复杂度 O ( n ) O(n) O(n),优先队列的最坏空间复杂度 O ( k ) O(k) O(k),总体空间复杂度 O ( n ) O(n) O(n) 。
AC

致语
- 理解思路很重要。
- 请读者放心留言,可以是疑惑的点,或者感谢/夸奖也可以!!墨染看到会回复的。
相关文章:
力扣(LeetCode)2512. 奖励最顶尖的K名学生(C++)
优先队列哈希集合反向思维(或自定义排序) 模拟,请直接看算法思路: 两个哈希集合S1和S2, S1存正面词汇,S2存负面词汇;一个优先队列pq,pq存{score, id}键值对,即学生分数-学生id。 算法流程: 初…...
CubeMX+BabyOS 使用方法
MCU:STM32G030F 编译器:MDK 托管工具:Sourcetree CubeMX创建工程 BabyOS克隆 添加子模块 git submodule add https://gitee.com/notrynohigh/BabyOS.git BabyOS 切换dev 分支 查看当前分支 git branch -a 切换本地分支到dev git che…...
OpenResty安装-(基于Nginx的高性能Web平台,可在Nginx端编码业务)
文章目录 安装OpenResty1.安装1)安装开发库2)安装OpenResty仓库3)安装OpenResty4)安装opm工具5)目录结构6)配置nginx的环境变量 2.启动和运行3.备注 安装OpenResty 1.安装 首先你的Linux虚拟机必须联网 …...
算法-DFS+记忆化/动态规划-不同路径 II
算法-DFS记忆化/动态规划-不同路径 II 1 题目概述 1.1 题目出处 https://leetcode.cn/problems/unique-paths-ii 1.2 题目描述 2 DFS记忆化 2.1 思路 注意题意,每次要么往右,要么往下走,也就是说不能走回头路。但是仍有可能走到之前已经…...
黑盒测试方法:原理+实战
目录 一、如何设计测试用例 二、黑盒测试常用方法 1、基于需求进行测试用例的设计 2、等价类 3、边界值 4、判定表分析法(因果分析法) 5、正交表 6、场景设计法 三、案例补充 1、使用Fiddler模拟弱网 2、针对一个接口该如何测试 一、如何设计测试…...
SQLite事务处理
语法 BEGIN TRANSACTION; COMMIT TRANSACTION; (或END TRANSACTION;) ROLLBACK TRANSACTION; 事务处理 除了一些PRAGMA语句以外,其它访问数据库的语句会自动启动事务处理,并且在结束时自动提交。 通过上一节的命令可以手动控制…...
Java中CountDownLatch使用场景
在Java的并发API中,CountDownLatch是一个同步器,它允许一个或多个线程等待一组操作完成。 如果您正在开发一个服务器应用程序,该应用程序在开始处理请求之前需要初始化各种资源。这些资源可能是这样的: 加载配置文件建立数据库连…...
漏刻有时数据可视化Echarts组件开发(41)svg格式地图应用
1.定义SVG文件 var svg ;2.注册地图函数 Echarts.registerMap是Echarts图表库中用于注册地图的函数。它可以将第三方地图或自定义地图数据与Echarts进行集成,使用Echarts的API进行绘制。使用方法如下: echarts.registerMap(mapName, geoJson) 参数map…...
firefox的主题文件位置在哪?记录以防遗忘
这篇文章写点轻松的 最近找到了一个自己喜欢的firefox主题,很想把主题的背景图片找到,所以找了下主题文件所在位置 我的firefox版本:版本: 118.0.1 (64 位)主题名称: Sora Kawai 我的位置在 C:\Users\mizuhokaga\AppData\Roaming\Mozilla\Firefox\Profiles\w0e4e24v.default…...
Vuex获取、修改参数值及异步数据处理
14天阅读挑战赛 学不可以已... 目录 一、Vuex简介 1.1 vuex介绍 1.2 vuex核心 二、Vuex使用 2.1 Vuex安装 2.2 创建store模块 2.3 创建vuex的store实例并注册上面引入的各大模块 三、使用Vuex获取、修改值案例 3.1 创建两个菜单组件 3.2 配置路由 3.3 模拟菜单数据 …...
【 OpenGauss源码学习 —— 列存储(autoanalyze)(二)】
列存储(autoanalyze)(二) 概述PgStat_StatTabEntry 结构体pgstat_count_heap_insert 与 pgstat_count_cu_insert 函数CStoreInsert::BatchInsertCommon 函数pgstat_count_cu_update 函数pgstat_count_cu_delete 函数pgstat_count_…...
使用postman 调用 Webservice 接口
1. 先在浏览器地址栏 访问你的webService地址 地址格式: http://127.0.0.1:8092/xxxx/ws(这个自己的决定)/xxxxXccv?wsdl 2. post man POST 访问wwebService接口 地址格式: http://127.0.0.1:8092/xxxx/ws(这个自己的决定)/xxxxXccv <soapenv:Envelope xmlns:soapenv…...
程序员Google插件推荐
文章目录 AdBlock (广告拦截插件)SuperCopy 超级复制Octotree (github增强工具)GitZip for github (github增强工具)JSON-handleSimpleExtManager(管理谷歌插件)OneTab (标签页合并)PostWoman(接口调试)篡改猴 (Tampermonkey)FeHelper(前端助手) AdBlock (广告拦截插件) ☆ 拦截…...
机器学习中常见的监督学习方法和非监督学习方法有哪些。
问题描述:最近面试某些公司算法岗,看到一道简答题,让你举例熟悉的监督学习方法和非监督学习方法。 问题解答: 监督学习方法常见的比较多: 线性回归(Linear Regression): 用于回归问…...
UEFI基础——测试用例Hello Word
Hello 测试用例 硬件环境:龙芯ls3a6000平台 软件环境:龙芯uefi固件 GUID获取网址:https://guidgen.com 一、创建工程 mkdir TextPkg/三个文件 Hello.c 、 Hello.inf 、HelloPkg.dsc 1.1 Hello.c /** fileThe application to print hello …...
【tomcat、java】
java:maven配置 1.安装插件 <build><plugins><plugin><groupId>org.apache.tomcat.maven</groupId><artifactId>tomcat7-maven-plugin</artifactId><version>2.1</version><configuration><port&…...
京东获取推荐商品列表 API
item_recommend-获取推荐商品列表 请求参数 请求参数:type 参数说明:type:推荐类型 进入API测试页 响应参数 Version: Date: 名称类型必须示例值描述 items items[]0获取推荐商品列表 num_iid Bigint010021415166448宝贝ID detail_url String0http…...
rust cfg的使用
前提是一个crate倒入另一个crate。 先看结构 test_lib目录结构 这与另一个crate处于同一个目录,所以另一crate倒入的时候在Cargo.toml中使用如下语句。 test_lib = {path = "../test_lib" }先在test_lib/src/abc/abc.rs中添加没有cfg的两个函数做测试。 pub fn…...
电脑屏幕怎么录制?5 个最佳免费录屏软件
您是否想使用网络摄像头录制优酷视频、抖音直播或在线课程等项目,但完全不知道如何开始? 不用担心。有很多软件选项可以帮助您。虽然每一款都有不同的功能,但它们都能够录制网络摄像头并输出精美的高质量视频。 以下是我们精选的最佳作品。…...
vscode 调试使用 make 编译的项目
1、首先点击运行 --> 启动调试: 2、选择g或gcc生成和调试活动文件: 3、出现下面提示是正常的,点击仍要调试: 点击打开“launch.json”: 4、此时会在项目工作目录下生成tsak.josn和launch.json文件: 如…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
