当前位置: 首页 > 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;也就是省略了三元运算符中间的部…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...