2024.3.2力扣每日一题——受限条件下可到达节点的数目
2024.3.2
- 题目来源
- 我的题解
- 方法一 深度优先搜索
- 方法二 并查集
题目来源
力扣每日一题;题序:2368
我的题解
方法一 深度优先搜索
使用深度优先搜索实现,在搜索过程中根据restricted进行截停。
时间复杂度:O(n)
空间复杂度:O(n)
int res=0;
public int reachableNodes(int n, int[][] edges, int[] restricted) {List<Integer>[] g=createTree(n,edges);boolean[] bRestricted=new boolean[n];for(int i:restricted){bRestricted[i]=true;}dfs(g,0,-1,bRestricted);return res;
}
public List<Integer>[] createTree(int n,int[][] edges){List<Integer>[] g=new ArrayList[n];for(int i=0;i<n;i++){g[i]=new ArrayList<>();}for(int[] t:edges){int from = t[0];int to = t[1];g[from].add(to);g[to].add(from);}return g;
}
public void dfs(List<Integer>[] g,int cur,int pre,boolean[] bRestricted){res++;for(int next:g[cur]){//防止循环遍历 并且不能是受限节点if(next!=pre&&!bRestricted[next])dfs(g,next,cur,bRestricted);}
}
方法二 并查集
如果忽略受限的点,树就会变成若干个连通块,要计算的就是 0号点所在连通块的大小。
因此,可以用并查集来不断地将点集进行合并,依次考虑每一条边,如果边上两个点都没有受限,那么合并这两个点的所在集合,否则跳过该边。最终查询 0号点所在连通块的大小即可。
时间复杂度:O(n×α(n)),其中 n 是无向树中点的个数,α是反阿克曼函数。使用路径压缩和按秩合并优化后的并查集,单次查询和合并操作的时间复杂度是 O(α(n)),通常比较小,可以忽略。
空间复杂度:O(n)
public int reachableNodes(int n, int[][] edges, int[] restricted) {boolean[] bRestricted=new boolean[n];for(int i:restricted){bRestricted[i]=true;}UF uf=new UF(n);for(int[] v:edges){//如果起始和结束节点有一个是受限的节点,则不合并if(bRestricted[v[0]]||bRestricted[v[1]]){continue;}uf.union(v[0],v[1]);}return uf.getCount();
}
class UF{private int count;private int parent[];public UF(int n){count=n;parent=new int[n];for (int i = 0; i < n; i++) {parent[i]=i;}}public void union(int p,int q){int parentP=find(p);int parentQ=find(q);if (parentP==parentQ)return;parent[parentQ]=parentP;count--;}public boolean isConnection(int p,int q){int parentP=find(p);int parentQ=find(q);return parentP==parentQ;}public int find(int x){if(parent[x]!=x){parent[x]=find(parent[x]);//路径压缩}return parent[x];}public int getCount(){int cnt=0;//找0所在的集合int rt=find(0);for(int i=0;i<parent.length;i++){if(rt==find(i))cnt++;}return cnt;}
}
有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~
相关文章:
2024.3.2力扣每日一题——受限条件下可到达节点的数目
2024.3.2 题目来源我的题解方法一 深度优先搜索方法二 并查集 题目来源 力扣每日一题;题序:2368 我的题解 方法一 深度优先搜索 使用深度优先搜索实现,在搜索过程中根据restricted进行截停。 时间复杂度:O(n) 空间复杂度&#…...

在云端遇见雨云:一位服务器寻觅者的指南
引言:寻觅一座云端归宿 当我踏入数字世界的边缘,带着对网络的探索与期待,我迫切需要一座安全可靠的数字栖息地。云计算技术正如一场魔法般的变革,而在这片广袤的云端中,雨云就像是一位友善的向导,引领我穿越…...

Pygame基础10-物理模拟
PyMunk PyMunk是一个模拟物理的库。 注意,PyMunk只是进行物理模拟,不包含可视化的功能。如果需要可视化,可使用pygame等库。 可用pip安装pymunk pip install pymunk pymunk中的概念: space: 物理空间。 包含gravity 模…...

蓝桥杯 --- 日期问题模板
目录 1.如何判断闰年 2.如何遍历当前年份的每一天 3.如果想要输出某一年某一天到某一年某一天之间一共有多少天。 4.精确到具体周几到周几的问题分析 5.如何直接通过一层for循环枚举年月日 习题: 蓝桥杯竞赛特别喜欢考日期问题,今天给大家分享一下…...

Java 处理Mysql获取树形的数据
Mysql数据: 代码如下: Entity: Data Accessors(chain true) public class Region {private BigInteger id;//名称private String name;//父idprivate BigInteger parentId;private List<Region> children;private Integer createTim…...

前端三剑客 —— CSS ( 坐标问题 、定位问题和图片居中 )
前期内容回顾: 1.常见样式 text-shadow x轴 y轴 阴影的模糊程度 阴影的颜色 box-shadow border-radio 实现圆角 margin 内边距 padding 外边距 background 2.特殊样式 媒体查询:media 自定义字体:font-face { font-family:自定义名称&#…...

向量数据库 | AI时代的航道灯塔
向量数据库 | AI时代的航道灯塔 什么是向量检索服务拍照搜商品 你使用过向量数据库吗?使用体验?为什么向量数据库能借由大模型引起众多关注向量数据库在当前AI热潮中是昙花一现,还是未来AI时代的航道灯塔? 今天的话题主要是讨论向…...
Linux中的conntrack命令深入解析
在Linux网络管理和监控领域,conntrack命令是一个强大的工具,它提供了对netfilter连接跟踪系统的直接访问🔍。这篇文章将深入探讨conntrack的由来、底层原理、参数意义,以及其常见用法,并对返回结果的每个字段进行详细解…...

反截屏控制技术如何防止信息通过手机拍照泄漏?
反截屏控制技术为企业数据安全提供了重要的防护措施。通过以下几点,有效阻止了信息通过拍照等方式的泄漏: 反截屏控制开启,用户启动截屏操作时,允许非涉密内容截屏操作,但所有涉密内容窗口会自动隐藏,防止涉…...
0.k8s简介
目录 k8s是什么 k8s不是什么 云原生 微服务 整体式架构与微服务架构 微服务的特性 微服务的优势 k8s是什么 Kubernetes 是一个可移植、可扩展的开源平台,用于管理容器化的工作负载和服务,可促进声明式配置和自动化。 Kubernetes 拥有一个庞大且快…...

VScode 集成终端设置默认打开当前文件夹 mac系统
一.快捷键设置 搜索 openInIntegratedTerminal 如图: 二.设置cmd 默认打开位置 点击设置 搜索 ntegrated:cwd 如下图: 三.查看ip 快捷指令: ipconfig getifaddr en0...

HDLbits 刷题 -- Alwaysblock2
学习: For hardware synthesis, there are two types of always blocks that are relevant: Combinational: always (*)Clocked: always (posedge clk) Clocked always blocks create a blob of combinational logic just like combinational always blocks, but…...

一、Docker部署GitLab(详细步骤)
Docker部署GitLab(详细步骤) 一、拉取镜像二、启动容器三、修改配置四、修改密码五、浏览器访问 一、拉取镜像 docker安装教程:https://qingsi.blog.csdn.net/article/details/131270071 docker pull gitlab/gitlab-ce:latest二、启动容器 …...
Vue3 Ajax(axios)
Vue 版本推荐使用 axios 来完成 ajax 请求。 安装方法 使用 cdn: <script src"https://unpkg.com/axios/dist/axios.min.js"></script> 使用 npm: $ npm install axios GET 方法 我们可以简单的读取 JSON 数据: const app {data() {r…...

正则表达式引擎库汇合
1.总览表格 一些正则表达式库的对比 index库名编程语言说明代码示例编译指令1Posix正则C语言是C标准库中用于编译POSIX风格的正则表达式库 posix-re.cgcc posix-re.c 2PCRE库C语言提供类似Perl语言的一个正则表达式引擎库。 一般系统上对应/usr/lib64/libpcre.so这个库文件&am…...

eBay买家号注册下单容易死号?是什么原因导致?
随着电子商务的迅猛发展,跨境电商平台eBay日益成为众多消费者和商家的首选。然而,自去年下半年以来,eBay推出的新规则给买家号的注册带来了前所未有的挑战。许多新用户反映,在注册eBay买家号后,往往遭遇刚注册就被冻结…...

【Linux】-进程知识铺垫①计算机硬件的组织:冯诺依曼体系结构详细解读②关于操作系统对软硬件及用户的意义
目录 编辑 1.关于计算机的体系结构 1.1 冯诺依曼体系结构的诞生 2.冯诺依曼体系结构 2.1 cpu:运算器:更多的是让cpu具有特殊的数据计算功能: 2.2 控制器 2.3输入设备 2.4输出设备 3.计算机各个硬件设备之间的关系 4.内存与计算机效率 5.关于为什么总说…...

让ECC升级S/4HANA一步到位的“全面升级方案包”
SAP最新一代商务套件S/4HANA比ECC系统拥有更高性能的存储数据库HANA、更个性化的Fiori用户界面设计系统,能够大大提升系统效率,带来便捷、高效、良好的用户体验。但企业原先使用的ECC系统里面保存了积累多年的关键流程和数据,让企业面对系统升…...
AutoGluon
官网 amazon (base) PS C:\Users\gg葱> conda env list # conda environments: # pytorch1 C:\Users\gg葱\.conda\envs\pytorch1 base * D:\ANCDD:\Documents\LMm\env\pytorch2(base) PS C:\Users\gg葱> conda create --prefixD:/Doc…...

【网站项目】少儿编程管理系统
🙊作者简介:拥有多年开发工作经验,分享技术代码帮助学生学习,独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。🌹赠送计算机毕业设计600个选题excel文件,帮助大学选题。赠送开题报告模板ÿ…...

idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...

解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...