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

相关文章

Java实现检查多个时间段是否有重合

《Java实现检查多个时间段是否有重合》这篇文章主要为大家详细介绍了如何使用Java实现检查多个时间段是否有重合,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录流程概述步骤详解China编程步骤1:定义时间段类步骤2:添加时间段步骤3:检查时间段是否有重合步骤4:输出结果示例代码结语作

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D

C#比较两个List集合内容是否相同的几种方法

《C#比较两个List集合内容是否相同的几种方法》本文详细介绍了在C#中比较两个List集合内容是否相同的方法,包括非自定义类和自定义类的元素比较,对于非自定义类,可以使用SequenceEqual、... 目录 一、非自定义类的元素比较1. 使用 SequenceEqual 方法(顺序和内容都相等)2.

查询Oracle数据库表是否被锁的实现方式

《查询Oracle数据库表是否被锁的实现方式》本文介绍了查询Oracle数据库表是否被锁的方法,包括查询锁表的会话、人员信息,根据object_id查询表名,以及根据会话ID查询和停止本地进程,同时,... 目录查询oracle数据库表是否被锁1、查询锁表的会话、人员等信息2、根据 object_id查询被

shell脚本快速检查192.168.1网段ip是否在用的方法

《shell脚本快速检查192.168.1网段ip是否在用的方法》该Shell脚本通过并发ping命令检查192.168.1网段中哪些IP地址正在使用,脚本定义了网络段、超时时间和并行扫描数量,并使用... 目录脚本:检查 192.168.1 网段 IP 是否在用脚本说明使用方法示例输出优化建议总结检查 1

python 字典d[k]中key不存在的解决方案

《python字典d[k]中key不存在的解决方案》本文主要介绍了在Python中处理字典键不存在时获取默认值的两种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录defaultdict:处理找不到的键的一个选择特殊方法__missing__有时候为了方便起见,

SpringBoot实现基于URL和IP的访问频率限制

《SpringBoot实现基于URL和IP的访问频率限制》在现代Web应用中,接口被恶意刷新或暴力请求是一种常见的攻击手段,为了保护系统资源,需要对接口的访问频率进行限制,下面我们就来看看如何使用... 目录1. 引言2. 项目依赖3. 配置 Redis4. 创建拦截器5. 注册拦截器6. 创建控制器8.

如何测试计算机的内存是否存在问题? 判断电脑内存故障的多种方法

《如何测试计算机的内存是否存在问题?判断电脑内存故障的多种方法》内存是电脑中非常重要的组件之一,如果内存出现故障,可能会导致电脑出现各种问题,如蓝屏、死机、程序崩溃等,如何判断内存是否出现故障呢?下... 如果你的电脑是崩溃、冻结还是不稳定,那么它的内存可能有问题。要进行检查,你可以使用Windows 11

Linux限制ip访问的解决方案

《Linux限制ip访问的解决方案》为了修复安全扫描中发现的漏洞,我们需要对某些服务设置访问限制,具体来说,就是要确保只有指定的内部IP地址能够访问这些服务,所以本文给大家介绍了Linux限制ip访问... 目录背景:解决方案:使用Firewalld防火墙规则验证方法深度了解防火墙逻辑应用场景与扩展背景:

如何提高Redis服务器的最大打开文件数限制

《如何提高Redis服务器的最大打开文件数限制》文章讨论了如何提高Redis服务器的最大打开文件数限制,以支持高并发服务,本文给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录如何提高Redis服务器的最大打开文件数限制问题诊断解决步骤1. 修改系统级别的限制2. 为Redis进程特别设置限制