【每日一题Day123】LC1792最大平均通过率 | 堆
最大平均通过率【LC1792】
一所学校里有一些班级,每个班级里有一些学生,现在每个班都会进行一场期末考试。给你一个二维数组
classes,其中classes[i] = [passi, totali],表示你提前知道了第i个班级总共有totali个学生,其中只有passi个学生可以通过考试。给你一个整数
extraStudents,表示额外有extraStudents个聪明的学生,他们 一定 能通过任何班级的期末考。你需要给这extraStudents个学生每人都安排一个班级,使得 所有 班级的 平均 通过率 最大 。一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。
请你返回在安排这
extraStudents个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在10-5以内的结果都会视为正确结果。
-
思路:
- 首先添加每一个学生时,应使通过率的变化值最大,才能获得最大的平均通过率
- 实现时可以使用大顶堆存储一个二元组,内容各个班级的通过学生和总学生,堆以增加一个通过学生后,通过率的变化值从大到小排序。这样堆顶元素即为添加一个学生通过率变化最大值对应的班级,操作
extraStudents次,然后求得最终的平均通过率返回即可
-
实现
class Solution {public double maxAverageRatio(int[][] classes, int extraStudents) {PriorityQueue<double[]> pq = new PriorityQueue<double[]>((o1, o2) -> (o2[0] + 1) / (o2[1] + 1) - o2[0] / o2[1] > (o1[0] + 1) / (o1[1] + 1) - o1[0] / o1[1] ? 1 : -1 );for (int[] c : classes){pq.add(new double[]{c[0], c[1]});}for (int i = 0; i < extraStudents; i++){double[] c = pq.poll();pq.add(new double[]{c[0] + 1, c[1] + 1});}double res = 0;while (!pq.isEmpty()){double[] c = pq.poll();res += c[0] / c[1];}return res / classes.length;} }- 复杂度
- 时间复杂度:O(n+klogn)O(n+klogn)O(n+klogn),nnn为班级数量,kkk为必通过的学生人数,向堆中添加元素的时间复杂度为O(logn)O(logn)O(logn)
- 空间复杂度:O(n)O(n)O(n),小顶堆的空间复杂度为O(n)O(n)O(n)
- 复杂度
相关文章:
【每日一题Day123】LC1792最大平均通过率 | 堆
最大平均通过率【LC1792】 一所学校里有一些班级,每个班级里有一些学生,现在每个班都会进行一场期末考试。给你一个二维数组 classes ,其中 classes[i] [passi, totali] ,表示你提前知道了第 i 个班级总共有 totali 个学生&#…...
[安装之5] Mac pro更换大内存固态硬盘实践教程
近由于mac电脑内存吃紧,安装大的软件,是不是要提示一下内存不够,内心非常的不爽。作为一款A1502版的mac,128G固态硬盘通常被称为“乞丐版”。提前做好准备工作后,我周末花了一天的时间搞定这件事,为了能够帮…...
04 Python变量的声明与使用
基本上,在所有的计算机编程语言中,都会用到变量,变量将数据存储在计算机内存中。 变量是指存储数据的内存地址,通过变量名,我们可以找到这个变量名对应的内容。 命名变量时不允许使用数字、特殊字符、连字符开头。 变量可以有一个短名称(如 x、y、z),但强烈建议使用更具…...
LeetCode 2418. 按身高排序
给你一个字符串数组 names ,和一个由 互不相同 的正整数组成的数组 heights 。两个数组的长度均为 n 。 对于每个下标 i,names[i] 和 heights[i] 表示第 i 个人的名字和身高。 请按身高 降序 顺序返回对应的名字数组 names 。 示例 1: 输…...
一文了解Hotspot虚拟机下JAVA对象从创建到回收的生命周期
Java虚拟机是Java的核心和基础,他是Java编译器和操作系统平台之间处理器,能实现跨平台运行Java程序。本文主要讲解的是虚拟机如何管理对象,即Java对象在JVM虚拟机中被创建到回收的流程 Java对象从创建到回收的生命周期对象创建流程1.类加载检…...
【Java基础】Java对象创建的几种方式
先上关键内容,所用到的代码请参考文末示例代码。一、使用new关键字创建对象这是一种最常用的创建对象的方式。Student student1 new Student();二、使用Class的newInstance()方法创建对象需要有一个无参构造方法,这个newInstance()方法调用无参的构造函…...
社保缴费满15年就可以不缴了?6个很多人最关心的问题权威解答来了
一、社保缴费满15年就可以不缴了? 上海市政府新闻办公室2022年在微信号发文表示,社会保险是由国家通过立法强制建立的社会保障制度,用人单位和劳动者都必须依法参加社会保险。即使职工与用人单位商议签订了不参加社保的所谓“协议”…...
关于HDFS
目录 一、HDFS概述 二、HDFS架构与工作机制 三、HDFS的Shell操作 四、Hdfs的API操作 一、HDFS概述 HDFS:Hadoop Distributed File System;一种分布式文件管理系统,通过目录树定位文件。使用场景:一次写入,多次读出…...
C++入门:类 对象
C 在 C 语言的基础上增加了面向对象编程,C 支持面向对象程序设计。类是 C 的核心特性,通常被称为用户定义的类型。类用于指定对象的形式,它包含了数据表示法和用于处理数据的方法。类中的数据和方法称为类的成员。函数在一个类中被称为类的成…...
Python生日系统
#免费源码见文末公众号# 录入生日 def write():keyvar1.get()valuevar2.get()with open(d:\\生日系统.pickle,rb) as file:dictspickle.load(file)dicts[key]valuewith open(d:\\生日系统.pickle,wb) as file:pickle.dump(dicts,file)file.close() 查询生日 def read():namev…...
< CSDN周赛解析:第 28 期 >
CSDN周赛解析:第 27 期👉 第一题: 小Q的鲜榨柠檬汁> 题目解析> 解决方案👉 第二题: 三而竭> 解析> 解决方案> 拓展知识👉 第三题: 隧道逃生> 解析> 解决方案👉…...
【题外话】如何拯救小米11Pro这款工业垃圾
1 背景媳妇用小米11Pro手机,某日不慎摔落,幸好屏幕未碎,然而WiFi却怎样都无法打开,初以为是系统死机,几天依旧故障无法使用。现在的手机没有WiFi功能,就无法刷抖音、看视频,就是鸡肋了。后抽空去…...
Python中有哪些常用操作?这20个你都会吗
Python 是一个解释型语言,可读性与易用性让它越来越热门。 正如 Python 之禅中所述: 优美胜于丑陋,明了胜于晦涩。 在你的日常编码中,以下技巧可以给你带来意想不到的收获。 1、字符串反转 下面的代码片段,使用 P…...
【LeetCode】剑指 Offer(4)
目录 写在前面: 题目:剑指 Offer 10- I. 斐波那契数列 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 10- II. …...
庄懂的TA笔记(十二)<>
庄懂的TA笔记(十二)<>一、作业展示,答疑:1、作业:2、答疑:二、作业示范,分析:1、文档分析:2、资源分析:3、资源优化:4、光…...
学分绩点(2023寒假每日一题 5)
北京大学对本科生的成绩施行平均学分绩点制(GPA)。 既将学生的实际考分根据不同的学科的不同学分按一定的公式进行计算。 公式如下: 实际成绩 绩点 90——100 4.0 85——89 3.7 82——84 3.3 78——81 3.0 75…...
Framework学习之旅:Zygote进程
概述 在Android系统中,DVM(Dalvik 虚拟机和ART、应用程序进程以及运行系统的关键服务SystemServer进程都是由Zygote进程来创建的。通过fork(复制进程)的形式来创建应用程进程和SystemServer进程,由于Zygote进程在启动时会创建DVM…...
HTTP基础知识
关键字:一问一答用于和服务器交互什么是HTTPHTTP是个应用层协议,是HTTP客户端和HTTP服务器之间的交互数据格式。所以这里有个实例:在浏览网页的时候,浏览器会向服务器发送一个HTTP请求,告诉服务器我想访问什么..然后服…...
Delphi 10.4.2使用传统代码提示方案(auto complete)(转)
Delphi 10.4重点是实现了LSP,但现在最新的10.4.2还是不成熟,无法满足日常需要,不过没关系,可以设置为原有的方案,如下图:具体操作:Tools->Options->Editor->language->Code Insight…...
存储类别、链接与内存管理(三)
1、malloc函数详解 (1)函数声明 #include <stdlib.h> void* malloc(size_t size);malloc可以申请一定数量的空闲内存,这样的内存是匿名的,也就是malloc不会为其赋名,但是确实返回动态分配内存块的首元素地址&a…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
【SpringBoot自动化部署】
SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一,能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时,需要添加Git仓库地址和凭证,设置构建触发器(如GitHub…...
如何在Windows本机安装Python并确保与Python.NET兼容
✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...
电脑桌面太单调,用Python写一个桌面小宠物应用。
下面是一个使用Python创建的简单桌面小宠物应用。这个小宠物会在桌面上游荡,可以响应鼠标点击,并且有简单的动画效果。 import tkinter as tk import random import time from PIL import Image, ImageTk import os import sysclass DesktopPet:def __i…...
