力扣(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文件: 如…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
