2023-08-23 LeetCode每日一题(统计点对的数目)
2023-08-23每日一题
一、题目编号
1782. 统计点对的数目
二、题目链接
点击跳转到题目位置
三、题目描述
给你一个无向图,无向图由整数 n ,表示图中节点的数目,和 edges 组成,其中 edges[i] = [ui, vi] 表示 ui 和 vi 之间有一条无向边。同时给你一个代表查询的整数数组 queries 。
第 j 个查询的答案是满足如下条件的点对 (a, b) 的数目:
- a < b
- cnt 是与 a 或者 b 相连的边的数目,且 cnt 严格大于 queries[j] 。
请你返回一个数组 answers ,其中 answers.length == queries.length 且 answers[j] 是第 j 个查询的答案。
请注意,图中可能会有 重复边 。
示例 1:
示例 2:
提示:
- 2 <= n <= 2 * 104
- 1 <= edges.length <= 105
- 1 <= ui, vi <= n
- ui != vi
- 1 <= queries.length <= 20
- 0 <= queries[j] < edges.length
四、解题代码
class Solution {unordered_map<int, int> cnt;int find(int left, int right, vector<int>& arr, int num){int ans = -1; while(left <= right){int mid = ((right - left) >> 1) + left;if(arr[mid] > num){ans = mid;right = mid - 1; } else{left = mid + 1; }}return ans;}public:void swap(int &x, int &y){int temp = x;x = y;y = temp;}vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {vector<int> degree(n);for(int i = 0; i < edges.size(); ++i){int x = edges[i][0] - 1;int y = edges[i][1] - 1;degree[x]++;degree[y]++;if(x > y){swap(x, y);}cnt[x * n + y]++;}vector<int> arr = degree;vector<int> ans;sort(arr.begin(), arr.end()); for(int i = 0; i < queries.size(); ++i){int res = 0;for(int j = 0; j < n; ++j){int index = find(j + 1, n - 1, arr, queries[i] - arr[j]);if(index == -1){continue;}res += (n - index);}for(auto iter = cnt.begin(); iter != cnt.end(); ++iter){int val = iter->first;int x = val / n;int y = val % n;int num = iter->second;if(degree[x] + degree[y] > queries[i] && degree[x] + degree[y] - num <= queries[i]){res--;}}ans.push_back(res);}return ans;}
};
五、解题思路
(1) 首先先统计一下每一个点的度数,然后用哈希表记录点x和点y共边的条数,那么与点x相连的边或者与点y相连的边的和为度数之和减去共边条数。
(2) 然后将度数在放在一个新的数组arr中,并且从小到大排序。
(3) 为了方便计算,将点的下标由1 ~ n改变成0 ~ n - 1。
(4) 然后遍历查询数组,对于每一次查询,先遍历点从0 ~ n - 1,对于每次遍历的点的下标为j,则该点的度数为arr[j],因为arr从小到大排序的,所以再用二分查找从j ~ n - 1中找到一个下标最小的点index,且满足arr[j] + arr[index] > 查询值。那么此时数对的数量为n - index,加上即可。
(5) 最后不要忘记减去共边的情况。如果度数之和满足条件但是减去共边之后不满足条件,就需要剔除。
(6) 最后返回结果数组即可。
相关文章:
2023-08-23 LeetCode每日一题(统计点对的数目)
2023-08-23每日一题 一、题目编号 1782. 统计点对的数目二、题目链接 点击跳转到题目位置 三、题目描述 给你一个无向图,无向图由整数 n ,表示图中节点的数目,和 edges 组成,其中 edges[i] [ui, vi] 表示 ui 和 vi 之间有一…...
LLMs之Code:SQLCoder的简介、安装、使用方法之详细攻略
LLMs之Code:SQLCoder的简介、安装、使用方法之详细攻略 目录 SQLCoder的简介 1、结果 2、按问题类别的结果 SQLCoder的安装 1、硬件要求 2、下载模型权重 3、使用SQLCoder 4、Colab中运行SQLCoder 第一步,配置环境 第二步,测试 第…...
数学建模(四)整数规划—匈牙利算法
目录 一、0-1型整数规划问题 1.1 案例 1.2 指派问题的标准形式 2.2 非标准形式的指派问题 二、指派问题的匈牙利解法 2.1 匈牙利解法的一般步骤 2.2 匈牙利解法的实例 2.3 代码实现 一、0-1型整数规划问题 1.1 案例 投资问题: 有600万元投资5个项目&…...
openGauss学习笔记-47 openGauss 高级数据管理-权限
文章目录 openGauss学习笔记-47 openGauss 高级数据管理-权限47.1 语法格式47.2 参数说明47.3 示例 openGauss学习笔记-47 openGauss 高级数据管理-权限 数据库对象创建后,进行对象创建的用户就是该对象的所有者。数据库安装后的默认情况下,未开启三权分…...
开始MySQL之路——MySQL 事务(详解分析)
MySQL 事务概述 MySQL 事务主要用于处理操作量大,复杂度高的数据。比如说,在人员管理系统中,你删除一个人员,你即需要删除人员的基本资料,也要删除和该人员相关的信息,如信箱,文章等等…...
注解和class对象和mysql
注解 override 通常是用在方法上的注解表示该方法是有重写的 interface 表示一个注解类 比如 public interface override{} 这就表示是override是一个注解类 target 修饰注解的注解表示元注解 deprecated 修饰某个元素表示该元素已经过时了 1.不代表该元素不能用了&…...
【桌面小屏幕项目】ESP32开发环境搭建
视频教程链接: 【【有手就行系列】嵌入式单片机教程-桌面小屏幕实战教学 从设计、硬件、焊接到代码编写、调试 ESP32 持续更新2022】 https://www.bilibili.com/video/BV1wV4y1G7Vk/?share_sourcecopy_web&vd_source4fa5fad39452b08a8f4aa46532e890a7 一、esp…...
CSS 滚动容器与固定 Tabbar 自适应的几种方式
问题 容器高度使用 px 定高时,随着页面高度发生变化,组件展示的数量不能最大化的铺满,导致出现底部留白。容器高度使用 vw 定高时,随着页面宽度发生变化,组件展示的数量不能最大化的铺满,导致出现底部留白…...
IP 地址追踪工具
IP 地址跟踪工具是一种网络实用程序,允许您扫描、跟踪和获取详细信息,例如 IP 地址的 MAC 和接口 ID。IP 跟踪解决方案通过使用不同的网络扫描协议来检查网络地址空间来收集这些详细信息。一些高级 IP 地址跟踪器软件(如 OpUtils)…...
最新企业网盘产品推荐榜发布
随着数字化发展,传统的文化存储方式已无法跟上企业发展的步伐。云存储的出现为企业提供了新的文件管理存储模式。企业网盘作为云存储的代表性工具,被越来越多的企业所青睐。那么在众多企业网盘产品中,企业该如何找到合适的企业网盘呢…...
实用的面试经验分享:程序员们谈论他们的面试历程
🌷🍁 博主猫头虎 带您 Go to New World.✨🍁 🦄 博客首页——猫头虎的博客🎐 🐳《面试题大全专栏》 文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~🌺 &a…...
6.oracle中listagg函数使用
1. 作用 可以实现行转列,将多列数据聚合为一列,实现数据的压缩 2. 语法 listagg(measure_expr,delimiter) within group ( order by order_by_clause); 解释: measure_expr可以是基于任何列的表达式 delimiter分隔符,…...
习题练习 C语言(暑期)
编程能力小提升! 前言一、转义字符二、重命名与宏定义三、三目运算符四、计算日期到天数转换五、计算字符串长度六、宏定义应用七、const常量八、C语言基础九、const常量(二)十、符号运算十一、记负均正十二、SWITCH,CASE十三、错…...
C++中虚函数表的概念
当一个类对象指针调用虚函数时,这就涉及到 运行时多态 的概念。这意味着实际调用的函数取决于对象的实际类型,而不仅仅是指针的静态类型。 假设我们有以下的类层次结构: class Base { public:virtual void print() {std::cout << &qu…...
代码随想录算法训练营第四十八天 | 198.打家劫舍,213.打家劫舍II,337.打家劫舍III
代码随想录算法训练营第四十八天 | 198.打家劫舍,213.打家劫舍II,337.打家劫舍III 198.打家劫舍213.打家劫舍II337.打家劫舍III 198.打家劫舍 题目链接 视频讲解 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金ÿ…...
uniapp项目实战系列(1):导入数据库,启动后端服务,开启代码托管
目录 前言前期准备1.数据库的导入2.运行后端服务2.1数据库的后端配置2.2后端服务下载依赖,第三方库2.3启动后端服务 3.开启gitcode代码托管 ✨ 原创不易,还希望各位大佬支持一下! 👍 点赞,你的认可是我创作的动力&…...
在互联网+的背景下,企业如何创新客户服务?
随着互联网的发展,开始数字化转型的潮流,移动互联网平台为各个行业带来了发展的新方向。企业有了移动互联网的加持,为客户提供了更好的服务。当移动互联网平台能够为客户提供更好的用户体验时,相应地,客户也给企业带来…...
国内的化妆品核辐射检测
化妆品核辐射物质检测是指检测化妆品中的放射性物质,包括放射性核素和放射性同位素。这些放射性物质主要来源于环境中的放射性污染,如空气、水和土壤中的放射性物质,以及化妆品生产过程中的放射性污染,如原料、设备、工艺等。化妆…...
春秋云镜:CVE-2019-9042(Sitemagic CMS v4.4 任意文件上传漏洞)
一、题目 靶标介绍: Sitemagic CMS v4.4 index.php?SMExtSMFiles 存在任意文件上传漏洞,攻击者可上传恶意代码执行系统命令。 进入题目: admin/admin /index.php?SMExtSMFiles&SMTemplateTypeBasic&SMExecModeDedicated&SMFil…...
20230828工作日志:
今天遇到了很多问题,下次可以做得更好更快的几个地方: 1 sql语句的检查 肯定要先在navicate 里执行看,是否有语法错误。即使没有,也还是要注意一些问题:IDEA里换行的时候,“后面要空一格,如果连…...
flink on yarn 部署
需要jars -rwxr-xrwx 3 root supergroup 58284 2022-11-30 03:44 /lib/flink/commons-cli-1.5.0.jar -rw-r--r-- 3 root supergroup 48497 2022-12-10 03:04 /lib/flink/flink-cep-scala_2.12-1.14.3.jar -rw-r--r-- 3 root supergroup 189468 2022-12-10…...
postgresql基于postgis常用空间函数
1、ST_AsGeoJSON 图元转geojson格式 select ST_AsGeoJSON(l.geom) from g_zd l limit 10 2、 ST_Transform 坐标转换 select st_transform(l.shape, 3857) from sde_wf_cyyq l limit 10select st_astext(st_transform(l.shape, 3857)) from sde_wf_cyyq l limit 103、st_aste…...
详细讲解移植u-boot.2022.10版本移植到开发板基本方法
大家好,我是ST。 今天给大家讲一讲如何将u-boot.2022.10版本移植到imx6ull开发板上。 环境 选项内容编译主机UbuntuLTS 18.04目标板ATK I.MX6ULL(512MB DDR3 8GB EMMC)u-boot版本2022.10交叉编译工具链gcc-linaro-7.5.0-2019.12-i686…...
Vue.js2+Cesium1.103.0 十一、Three.js 炸裂效果
Vue.js2Cesium1.103.0 十一、Three.js 炸裂效果 Demo ThreeModelBoom.vue <template><div:id"id"class"three_container"/> </template><script> /* eslint-disable eqeqeq */ /* eslint-disable no-unused-vars */ /* eslint-d…...
Nodejs快速搭建简单的HTTP服务器,并发布公网远程访问
前言 Node.js 是能够在服务器端运行 JavaScript 的开放源代码、跨平台运行环境。Node.js 由 OpenJS Foundation(原为 Node.js Foundation,已与 JS Foundation 合并)持有和维护,亦为 Linux 基金会的项目。Node.js 采用 Google 开发…...
爬虫入门01
1. 请求头中最常见的一些重要内容 User-Agent : 请求载体的身份标识(⽤啥发送的请求)Referer: 防盗链(这次请求是从哪个⻚⾯来的? 反爬会⽤到)cookie: 本地字符串数据信息(⽤户登录信息, 反爬的token) 2. 响应头中一些重要内容 cookie: 本地字符串数据信息(⽤户登录信息, 反…...
解读GIS软件:从ArcGIS到山海鲸可视化的全方位介绍
在现代社会,地理信息系统(GIS)的应用已经渗透到了各个领域,为我们提供了丰富的地理数据分析和可视化工具。下面介绍几款常见的GIS工具软件,一起来了解它们的特点和优势。 1. ArcGIS: ArcGIS由Esri公司开发,…...
嵌入式通用硬件模块设计——串口音频播放模块
模块功能展示: 串口音频控制模块 一、简介 方案为串口音频播放芯片功放芯片,口音频播放芯片IC为my1690-16s,功放为PAM8406。 1、my1690-16s 迈优科技的一款由串口控制的插卡MP3播放控制芯片,支持串口控制播放指定音频、音量调节…...
【PLSQL】PLSQL基础
文章目录 一:记录类型1.语法2.代码实例 二:字符转换三:%TYPE和%ROWTYPE1.%TYPE2.%ROWTYPE 四:循环1.LOOP2.WHILE(推荐)3.数字式循环 五:游标1.游标定义及读取2.游标属性3.NO_DATA_FOUND和%NOTFO…...
【C++笔记】C++内存管理
【C笔记】C内存管理 一、C中动态内存申请的方式二、new和delete的实现原理2.1、operator new和operator delete函数 一、C中动态内存申请的方式 在C语言中我们需要动态申请空间的时候我们通常都是用malloc函数,但是malloc函数对自定义类型是没什么问题的࿰…...
十四五双碳双控时代下的“低碳认证”
目录 前言 十四五双碳双控时代下的“低碳认证” 一、关于“低碳认证” 二、低碳认证优势 三、环境产品认证EPD 四、EPD相关运营机构 五、碳中和相关机构 六、EPD的认证流程 七、低碳产品认证认证流程和要求 八、相关机构认证证书样例 九、证书附件表 前言 通过本篇文…...
Android——基本控件(下)(十九)
1. 菜单:Menu 1.1 知识点 (1)掌握Android中菜单的使用; (2)掌握选项菜单(OptionsMenu)的使用; (3)掌握上下文菜单(ContextMenu&am…...
聚类分析 | MATLAB实现基于DBSCAD密度聚类算法可视化
聚类分析 | MATLAB实现基于LP拉普拉斯映射的聚类可视化 目录 聚类分析 | MATLAB实现基于LP拉普拉斯映射的聚类可视化效果一览基本介绍程序设计参考资料 效果一览 基本介绍 基于DBSCAD密度聚类算法可视化,MATLAB程序。 使用带有KD树加速的dbscan_with_kdtree函数进行…...
reactantd(12)动态表单的默认值问题
最近遇到一个需求是有一个表单可以输入各种信息,然后还需要有一个编辑功能,点击编辑的时候需要把当前数据填入到表单里面。在网上查了很多种方法,然后我的思路是使用initialValues搭配setState()使用。默认值都为空,然后点击单条数…...
无涯教程-Python机器学习 - Stochastic Gradient Boosting函数
它也称为梯度提升机。在下面的Python食谱中,我们将通过使用pima Indians糖尿病数据集上的 sklearn 的 GradientBoostingClassifier 类来创建随机梯度Boostingensemble模型进行分类。 首先,导入所需的软件包,如下所示: from pandas import read_csv from sklearn.model_select…...
SOLIDWORKS中多实体文件到装配体的转换技巧
我们在做机械等工程设计中,有时为了节省时间,需要把多实体的“零件”,直接转换为装配体,不再另外装配,这样能大大简化设计的操作时间,复杂程度。 在这里,我们首先要了解,SOLIDWORKS文…...
Transformer (Attention Is All You Need) 论文精读笔记
Transformer(Attention Is All You Need) Attention Is All You Need 参考:跟李沐学AI-Transformer论文逐段精读【论文精读】 摘要(Abstract) 首先摘要说明:目前,主流的序列转录(序列转录:给…...
Git企业开发控制理论和实操-从入门到深入(二)|Git的基本操作
前言 那么这里博主先安利一些干货满满的专栏了! 首先是博主的高质量博客的汇总,这个专栏里面的博客,都是博主最最用心写的一部分,干货满满,希望对大家有帮助。 高质量博客汇总https://blog.csdn.net/yu_cblog/cate…...
Positive Technologies 专家帮助修复 Western Digital 网络存储设备中的一个危险漏洞
Positive Technologies 专家帮助修复 Western Digital 网络存储设备中的一个危险漏洞 经过验证的攻击者可利用该漏洞在受攻击的设备上注入恶意软件并远程访问文件 Western Digital 感谢 Positive Technologies 专家 Nikita Abramov 发现 Western Digital NAS 固件中的一个漏洞…...
【springboot】springboot定时任务:
文章目录 一、文档:二、案例: 一、文档: 【cron表达式在线生成器】https://cron.qqe2.com/ 二、案例: EnableScheduling //开启任务调度package com.sky.task;import com.sky.entity.Orders; import com.sky.mapper.OrderMapper; …...
腾讯云学生服务器申请、学生认证入口及学生机价格表
腾讯云学生服务器申请、学生认证入口及学生机价格表,学生机申请流程,腾讯云学生服务器优惠活动:轻量应用服务器2核2G学生价30元3个月、58元6个月、112元一年,轻量应用服务器4核8G配置191.1元3个月、352.8元6个月、646.8元一年&…...
pip安装mysqlclient依赖报错 /bin/sh: 1: mysql_config: not found如何解决
报错信息: Collecting mysqlclient2.1.0Downloading https://mirrors.aliyun.com/pypi/packages/de/79/d02be3cb942afda6c99ca207858847572e38146eb73a7c4bfe3bdf154626/mysqlclient-2.1.0.tar.gz (87 kB)|███████████████████████████…...
基于paddleocr的版面分析
前处理: DocTr: Document Image Transformer for Geometric Unwarping and Illumination Correction (1)几何矫正 给定一张存在几何和光照畸变的文档图像,我们首先用一个包含六个卷积模块的特征提取器对其进行特征提取…...
网工内推 | IT网工,华为、华三认证优先,15k*13薪
01 广东善能科技发展股份有限公司 招聘岗位:IT网络工程师 职责描述: 1、负责公司项目售后技术支持工作; 2、负责项目交付实施,配置调试、运维等; 3、参加合作厂商产品技术知识培训; 4、参加合作厂商工程师…...
leetcode 739. 每日温度
2023.8.28 本题用暴力双层for循环解会超时,所以使用单调栈来解决,本质上是用空间换时间。维护一个单调递减栈,存储的是数组的下标。 代码如下: class Solution { public:vector<int> dailyTemperatures(vector<int>&…...
【活体检测模型】活体检测思路推演
ref:https://arxiv.org/pdf/1611.05431.pdf https://github.com/miraclewkf/ResNeXt-PyTorch 用分类的思想做活体检测,要求准确的分出正负样本,否则,支付宝被别人用了,问题就很严重。 大部分的商用场景还是 摇摇头、张张口&#x…...
【微服务部署】03-健康检查
文章目录 1. 探针集成实现高可用1.1 LivenessProbe1.2 ReadinessProbe1.3 StartupProbe 2. 健康检查看板2.1 组件包 1. 探针集成实现高可用 LivenessReadinessStartup 1.1 LivenessProbe 判断服务是否存活结束“非存活”状态服务根据重启策略决定是否重启服务 1.2 Readines…...
SQL注入之报错注入
文章目录 报错注入是什么?报错注入获取cms账号密码成功登录 报错注入是什么? 在注入点的判断过程中,发现数据库中SQL 语句的报错信息,会显示在页面中,因此可以利用报错信息进行注入。 报错注入的原理,就是在…...
基于大数据+django+mysql的银行信用卡用户的数仓系统
系统阐述的是银行信用卡用户的数仓系统的设计与实现,对于Python、B/S结构、MySql进行了较为深入的学习与应用。主要针对系统的设计,描述,实现和分析与测试方面来表明开发的过程。开发中使用了 django框架和MySql数据库技术搭建系统的整体架构…...
【网络】多路转接——五种IO模型 | select
🐱作者:一只大喵咪1201 🐱专栏:《网络》 🔥格言:你只管努力,剩下的交给时间! 五种IO模型 | select 🍧五种IO模型🍧select🧁认识接口🧁…...