1697. 检查边长度限制的路径是否存在

2024-02-01 06:04

本文主要是介绍1697. 检查边长度限制的路径是否存在,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Problem: 1697. 检查边长度限制的路径是否存在

文章目录

  • 思路
  • 解题方法
  • 复杂度
  • Code

思路

这是一个关于边长度限制路径存在性的问题。给定一个无向图,每条边都有一个长度。同时给定一些查询,每个查询包含两个节点和一个长度限制。需要判断是否存在一条路径连接这两个节点,并且路径上的边的长度都不超过限制。

可以使用并查集来解决这个问题。首先对边按照长度进行排序,然后对查询按照限制长度进行排序。然后使用并查集来判断两个节点是否在同一个连通分量中。遍历查询,对于每个查询,将小于等于限制长度的边添加到并查集中,然后判断两个节点是否在同一个连通分量中。

解题方法

创建一个大小为n的数组father,用于存储每个节点的父节点。
创建一个大小为m的二维数组questions,用于存储查询的信息。其中questions[i][0]表示查询的起始节点,questions[i][1]表示查询的终止节点,questions[i][2]表示查询的限制长度,questions[i][3]表示查询的索引。
对边的列表edgeList按照边的长度进行排序。
对查询的列表queries按照限制长度进行排序。
使用并查集的find和union操作,遍历查询列表,对于每个查询,将小于等于限制长度的边添加到并查集中,然后判断起始节点和终止节点是否在同一个连通分量中。
将判断结果存储到一个大小为m的布尔数组ans中,ans[i]表示第i个查询的结果。
返回ans作为查询结果。

复杂度

时间复杂度:

排序边和查询的时间复杂度为 O ( E l o g E + M l o g M ) O(ElogE + MlogM) O(ElogE+MlogM),其中E为边的数量,M为查询的数量。并查集的时间复杂度为 O ( l o g N ) O(logN) O(logN),其中N为节点的数量

空间复杂度:

O ( N ) O(N) O(N),用于存储并查集的father数组。

Code

class Solution {public int MAXN = 100001;public int[][] questions = new int[MAXN][4];public int[] father = new int[MAXN];public void build(int n) {for (int i = 0; i < n; i++) {father[i] = i;}}public int find(int i) {if (i != father[i]) {father[i] = find(father[i]);}return father[i];}public boolean isSameSet(int x, int y) {return find(x) == find(y);}public void union(int x, int y) {father[find(x)] = find(y);}public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {Arrays.sort(edgeList, (a, b) -> (a[2] - b[2]));int k = edgeList.length;int m = queries.length;for (int i = 0; i < m; i++) {questions[i][0] = queries[i][0];questions[i][1] = queries[i][1];questions[i][2] = queries[i][2];questions[i][3] = i;}Arrays.sort(questions, 0, m, (a, b) -> a[2] - b[2]);build(n);boolean[] ans = new boolean[m];for (int i = 0, j = 0; i < m; i++) {for (; j < k && edgeList[j][2] < questions[i][2]; j++) {union(edgeList[j][0], edgeList[j][1]);}ans[questions[i][3]] = isSameSet(questions[i][0], questions[i][1]);}return ans;}
}

这篇关于1697. 检查边长度限制的路径是否存在的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/666281

相关文章

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决

Linux如何快速检查服务器的硬件配置和性能指标

《Linux如何快速检查服务器的硬件配置和性能指标》在运维和开发工作中,我们经常需要快速检查Linux服务器的硬件配置和性能指标,本文将以CentOS为例,介绍如何通过命令行快速获取这些关键信息,... 目录引言一、查询CPU核心数编程(几C?)1. 使用 nproc(最简单)2. 使用 lscpu(详细信

SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

《SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志》在SpringBoot项目中,使用logback-spring.xml配置屏蔽特定路径的日志有两种常用方式,文中的... 目录方案一:基础配置(直接关闭目标路径日志)方案二:结合 Spring Profile 按环境屏蔽关

python判断文件是否存在常用的几种方式

《python判断文件是否存在常用的几种方式》在Python中我们在读写文件之前,首先要做的事情就是判断文件是否存在,否则很容易发生错误的情况,:本文主要介绍python判断文件是否存在常用的几种... 目录1. 使用 os.path.exists()2. 使用 os.path.isfile()3. 使用

VSCode设置python SDK路径的实现步骤

《VSCode设置pythonSDK路径的实现步骤》本文主要介绍了VSCode设置pythonSDK路径的实现步骤,包括命令面板切换、settings.json配置、环境变量及虚拟环境处理,具有一定... 目录一、通过命令面板快速切换(推荐方法)二、通过 settings.json 配置(项目级/全局)三、

使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

《使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)》字体设计和矢量图形处理是编程中一个有趣且实用的领域,通过Python的matplotlib库,我们可以轻松将字体轮廓... 目录背景知识字体轮廓的表示实现步骤1. 安装依赖库2. 准备数据3. 解析路径指令4. 绘制图形关键

如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)

《如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)》:本文主要介绍如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)问题,具有很好的参考价值,希望对大家有所帮助,如有... 目录先在你打算存放的地方建四个文件夹更改这四个路径就可以修改默认虚拟内存分页js文件的位置接下来从高级-

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一:使用正则表达式方法二:手动检查特定字符Pytho

Nginx 413修改上传文件大小限制的方法详解

《Nginx413修改上传文件大小限制的方法详解》在使用Nginx作为Web服务器时,有时会遇到客户端尝试上传大文件时返回​​413RequestEntityTooLarge​​... 目录1. 理解 ​​413 Request Entity Too Large​​ 错误2. 修改 Nginx 配置2.1