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

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 * 104
  • 1 <= edges.length <= 105
  • 1 <= ui, vi <= n
  • ui != vi
  • 1 <= queries.length <= 20
  • 0 <= queries[j] < edges.length

相关文章:

2023-08-23力扣每日一题

链接&#xff1a; 1782. 统计点对的数目 题意&#xff1a; 给n个点和m条无向边&#xff08;可重复&#xff09;&#xff0c;q个查询 定义edge[a]为一个点是a的边数量&#xff0c;定义ret[a,b]是edge[a]edge[b]-&#xff08;a与b的边&#xff09; q个查询q个答案&#xff0…...

分发饼干【贪心算法】

分发饼干 假设你是一位很棒的家长&#xff0c;想要给你的孩子们一些小饼干。但是&#xff0c;每个孩子最多只能给一块饼干。 对每个孩子 i&#xff0c;都有一个胃口值 g[i]&#xff0c;这是能让孩子们满足胃口的饼干的最小尺寸&#xff1b;并且每块饼干 j&#xff0c;都有一个…...

为什么网络互联地址设置为30位地址

对于点对点链路&#xff0c;为了节约IPv4地址&#xff0c;一般为其分配/30地址块&#xff0c;这样包含4个地址&#xff1a;最小地址作为网络地址&#xff0c;最大地址作为广播地址&#xff0c;剩余两个可分配地址&#xff0c;分配给链路两端的接口&#xff0c;这是最普遍的方法…...

青少年棒球锦标赛发展·棒球1号位

青少年棒球锦标赛发展 1. 青少年棒球锦标赛简介 青少年棒球锦标赛是一个令人兴奋的国际性比赛&#xff0c;每年都有来自世界各地的优秀青少年棒球选手参加。这个锦标赛旨在提供一个展示青少年棒球选手的技能和才华的平台&#xff0c;同时也是为了推动棒球在全球范围内的普及和…...

Unity实现UI图片面板滚动播放效果第二弹

效果&#xff1a; 场景结构&#xff1a; 特殊物体&#xff1a;panel下面用排列组件horizent layout group放置多个需要显示的面板&#xff0c;用mask遮罩好。 主要思路&#xff1a; 这次是要在最后一个toggle的地方&#xff0c;依然向左滚动回1&#xff0c;这是难点。因此实际…...

Redis的基本操作

文章目录 1.Redis简介2.Redis的常用数据类型3.Redis的常用命令1.字符串操作命令2.哈希操作命令3.列表操作命令4.集合操作命令5.有序集合操作命令6.通用操作命令 4.Springboot配置Redis1.导入SpringDataRedis的Maven坐标2.配置Redis的数据源3.编写配置类&#xff0c;创还能Redis…...

省级智慧农业大数据平台项目规划建设方案[195页Word]

导读&#xff1a;原文《省级智慧农业大数据平台项目规划建设方案[195页Word]》&#xff08;获取来源见文尾&#xff09;&#xff0c;本文精选其中精华及架构部分&#xff0c;逻辑清晰、内容完整&#xff0c;为快速形成售前方案提供参考。 1 农业大数据平台项目概述 1.1 建设…...

php图片批量压缩并同时保持清晰度

php图片压缩可以通过GD库来实现。以下是一个使用GD库进行图片压缩的示例代码&#xff1a; // 原始图片路径 $sourceImage path/to/source/image.jpg; // 压缩后保存的路径及文件名 $compressedImage path/to/compressed/image.jpg; // 压缩后的图片质量&#xff08;1-100&…...

243:vue+Openlayers 更改鼠标滚轮缩放地图大小,每次缩放小一点

第243个 点击查看专栏目录 本示例的目的是介绍如何在vue+openlayers项目中设置鼠标滚轮缩放地图大小,每次滑动一格滚轮,设定的值非默认值1。具体的设置方法,参考源代码。 直接复制下面的 vue+openlayers源代码,操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例源…...

NOI2015D. 荷马史诗

荷马史诗 题目描述 追逐影子的人&#xff0c;自己就是影子。 ——荷马 Allison 最近迷上了文学。她喜欢在一个慵懒的午后&#xff0c;细细地品上一杯卡布奇诺&#xff0c;静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是…...

并法编程(集合类不安全)03详细讲解未补充

还未补充...

软考:中级软件设计师:大数据

软考&#xff1a;中级软件设计师:大数据 提示&#xff1a;系列被面试官问的问题&#xff0c;我自己当时不会&#xff0c;所以下来自己复盘一下&#xff0c;认真学习和总结&#xff0c;以应对未来更多的可能性 关于互联网大厂的笔试面试&#xff0c;都是需要细心准备的 &#x…...

【持续更新中】QAGroup1

OVERVIEW Q&AGroup1一、语言基础1.C语言&#xff08;1&#xff09;含参数的宏与函数的不同点&#xff08;2&#xff09;sizeof与strlen的区别&#xff08;3&#xff09;大/小端&#xff08;4&#xff09;strcpy与memcpy的区别&#xff08;5&#xff09;extern与static的区别…...

redis应用 2:延时队列

我们平时习惯于使用 Rabbitmq 和 Kafka 作为消息队列中间件&#xff0c;来给应用程序之间增加异步消息传递功能。这两个中间件都是专业的消息队列中间件&#xff0c;特性之多超出了大多数人的理解能力。 使用过 Rabbitmq 的同学知道它使用起来有多复杂&#xff0c;发消息之前要…...

ChatGPT AIGC 实现动态组合图的用法

数据分析组合图,即在一张图表中组合使用多种图形类型(如柱状图、折线图、饼图等),可以在同一视图中展示多个维度或多个量度的数据,帮助数据分析师或决策者更好地理解和解释数据。 组合图的功能和作用主要包括: 提供信息视角:组合图可以对比不同类型的数据,展现数据间的…...

【网站】解压放松的治愈白噪音ASMR

70年代中期国际上新创立的无穷维Schwartz广泛函数理论&#xff0c;应用所严加安研究员是建立和完善该理论的数学框架的主要贡献者之一&#xff0c;他与法国科学院通讯院士Meyer教授提出的框架被称为Meyer-Yan空间。他与Kondratiev等新近发表的论文建立了完善的无穷维非高斯分析…...

算法通过村第四关-栈白银笔记|括号问题

文章目录 前言1. 括号匹配问题2. 最小栈问题3. 最大栈 总结 前言 提示&#xff1a;如果让我送给年轻人四个字&#xff0c;就是&#xff1a;量力而行。 量力而行不会失眠&#xff0c;不会啃老&#xff0c;不会为各种考试焦虑。顺其自然活得轻松。其实&#xff0c;量力而行最易大…...

基于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 合并运算符 附上官方文档查阅方式 快速掌握 ?: 短三元运算符 ?: 称之为短三元运算符&#xff0c;它是我们熟悉的三元运算符&#xff08;也叫做条件运算符&#xff09;的一种特殊写法&#xff0c;也就是省略了三元运算符中间的部…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...