2023-08-23力扣每日一题
链接:
1782. 统计点对的数目
题意:
给n个点和m条无向边(可重复),q个查询
定义edge[a]为一个点是a的边数量,定义ret[a,b]是edge[a]+edge[b]-(a与b的边)
q个查询q个答案,第i次查询值val[i],求所有的1<=a<b<=n条件下有多少ret[a,b]>val[i]
解:
TLE卡47了
看了评论区用空间换时间,双指针
实际代码:
class Solution {
public:typedef pair<int,int> pii;
vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries)
{vector<int>edgeNum(n+1);//记录edge[a]map<pii,int>edgePair;for(auto edge:edges){if(edge[0]>edge[1]) swap(edge[0],edge[1]);edgeNum[edge[0]]++;edgeNum[edge[1]]++;edgePair[{edge[0],edge[1]}]++;//记录(a与b的边)}vector<int>ans; vector<int>edgeNS(edgeNum); sort(edgeNS.begin(),edgeNS.end());//空间换时间 排序for(auto querie:queries){int temp=0;int left=1,right=n;while(left<right)//双指针 {if(edgeNS[left] + edgeNS[right] <= querie) left++;else{temp+= right-left;right--;}}for(auto Pair:edgePair){int s=edgeNum[Pair.first.first]+edgeNum[Pair.first.second];if(s>querie && s-Pair.second<=querie) temp--;}ans.push_back(temp);}return ans;
}
};
限制:
2 <= n <= 2 * 1041 <= edges.length <= 1051 <= ui, vi <= nui != vi1 <= queries.length <= 200 <= queries[j] < edges.length
相关文章:
2023-08-23力扣每日一题
链接: 1782. 统计点对的数目 题意: 给n个点和m条无向边(可重复),q个查询 定义edge[a]为一个点是a的边数量,定义ret[a,b]是edge[a]edge[b]-(a与b的边) q个查询q个答案࿰…...
分发饼干【贪心算法】
分发饼干 假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。 对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个…...
为什么网络互联地址设置为30位地址
对于点对点链路,为了节约IPv4地址,一般为其分配/30地址块,这样包含4个地址:最小地址作为网络地址,最大地址作为广播地址,剩余两个可分配地址,分配给链路两端的接口,这是最普遍的方法…...
青少年棒球锦标赛发展·棒球1号位
青少年棒球锦标赛发展 1. 青少年棒球锦标赛简介 青少年棒球锦标赛是一个令人兴奋的国际性比赛,每年都有来自世界各地的优秀青少年棒球选手参加。这个锦标赛旨在提供一个展示青少年棒球选手的技能和才华的平台,同时也是为了推动棒球在全球范围内的普及和…...
Unity实现UI图片面板滚动播放效果第二弹
效果: 场景结构: 特殊物体:panel下面用排列组件horizent layout group放置多个需要显示的面板,用mask遮罩好。 主要思路: 这次是要在最后一个toggle的地方,依然向左滚动回1,这是难点。因此实际…...
Redis的基本操作
文章目录 1.Redis简介2.Redis的常用数据类型3.Redis的常用命令1.字符串操作命令2.哈希操作命令3.列表操作命令4.集合操作命令5.有序集合操作命令6.通用操作命令 4.Springboot配置Redis1.导入SpringDataRedis的Maven坐标2.配置Redis的数据源3.编写配置类,创还能Redis…...
省级智慧农业大数据平台项目规划建设方案[195页Word]
导读:原文《省级智慧农业大数据平台项目规划建设方案[195页Word]》(获取来源见文尾),本文精选其中精华及架构部分,逻辑清晰、内容完整,为快速形成售前方案提供参考。 1 农业大数据平台项目概述 1.1 建设…...
php图片批量压缩并同时保持清晰度
php图片压缩可以通过GD库来实现。以下是一个使用GD库进行图片压缩的示例代码: // 原始图片路径 $sourceImage path/to/source/image.jpg; // 压缩后保存的路径及文件名 $compressedImage path/to/compressed/image.jpg; // 压缩后的图片质量(1-100&…...
243:vue+Openlayers 更改鼠标滚轮缩放地图大小,每次缩放小一点
第243个 点击查看专栏目录 本示例的目的是介绍如何在vue+openlayers项目中设置鼠标滚轮缩放地图大小,每次滑动一格滚轮,设定的值非默认值1。具体的设置方法,参考源代码。 直接复制下面的 vue+openlayers源代码,操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例源…...
NOI2015D. 荷马史诗
荷马史诗 题目描述 追逐影子的人,自己就是影子。 ——荷马 Allison 最近迷上了文学。她喜欢在一个慵懒的午后,细细地品上一杯卡布奇诺,静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是…...
并法编程(集合类不安全)03详细讲解未补充
还未补充...
软考:中级软件设计师:大数据
软考:中级软件设计师:大数据 提示:系列被面试官问的问题,我自己当时不会,所以下来自己复盘一下,认真学习和总结,以应对未来更多的可能性 关于互联网大厂的笔试面试,都是需要细心准备的 &#x…...
【持续更新中】QAGroup1
OVERVIEW Q&AGroup1一、语言基础1.C语言(1)含参数的宏与函数的不同点(2)sizeof与strlen的区别(3)大/小端(4)strcpy与memcpy的区别(5)extern与static的区别…...
redis应用 2:延时队列
我们平时习惯于使用 Rabbitmq 和 Kafka 作为消息队列中间件,来给应用程序之间增加异步消息传递功能。这两个中间件都是专业的消息队列中间件,特性之多超出了大多数人的理解能力。 使用过 Rabbitmq 的同学知道它使用起来有多复杂,发消息之前要…...
ChatGPT AIGC 实现动态组合图的用法
数据分析组合图,即在一张图表中组合使用多种图形类型(如柱状图、折线图、饼图等),可以在同一视图中展示多个维度或多个量度的数据,帮助数据分析师或决策者更好地理解和解释数据。 组合图的功能和作用主要包括: 提供信息视角:组合图可以对比不同类型的数据,展现数据间的…...
【网站】解压放松的治愈白噪音ASMR
70年代中期国际上新创立的无穷维Schwartz广泛函数理论,应用所严加安研究员是建立和完善该理论的数学框架的主要贡献者之一,他与法国科学院通讯院士Meyer教授提出的框架被称为Meyer-Yan空间。他与Kondratiev等新近发表的论文建立了完善的无穷维非高斯分析…...
算法通过村第四关-栈白银笔记|括号问题
文章目录 前言1. 括号匹配问题2. 最小栈问题3. 最大栈 总结 前言 提示:如果让我送给年轻人四个字,就是:量力而行。 量力而行不会失眠,不会啃老,不会为各种考试焦虑。顺其自然活得轻松。其实,量力而行最易大…...
基于MATLAB开发AUTOSAR软件应用层Code mapping专题-part 6 Data Transfers标签页介绍
这篇文章我们介绍下Data Transfers页的配置,这里边包含的内容是IRV,我之前的文章里有讲解过IRV就是 Inter-Runnable Variables,内部runnable的之间传递数据的变量,在讲解Data Store memory的文章里我们提到了,irv也可以使用Data Store memory的方式来实现,我们先看下IRV如何…...
HDLBits-Verilog学习记录 | Verilog Language-Vectors
文章目录 11.vectors | vector012.vectors in more detail | vector113.Vector part select | Vector214.Bitwise operators | Vectorgates15.Four-input gates | Gates416.Vector concatenation operator | Vector317.Vector reversal 1 | Vectorr18. Replication operator | …...
彻底搞懂 PHP 运算符 ?: 和 ??
文章目录 快速掌握?: 短三元运算符?? NULL 合并运算符 附上官方文档查阅方式 快速掌握 ?: 短三元运算符 ?: 称之为短三元运算符,它是我们熟悉的三元运算符(也叫做条件运算符)的一种特殊写法,也就是省略了三元运算符中间的部…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
