当前位置: 首页 > news >正文

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 题目来源我的题解方法一 深度优先搜索方法二 并查集 题目来源 力扣每日一题&#xff1b;题序&#xff1a;2368 我的题解 方法一 深度优先搜索 使用深度优先搜索实现&#xff0c;在搜索过程中根据restricted进行截停。 时间复杂度&#xff1a;O(n) 空间复杂度&#…...

在云端遇见雨云:一位服务器寻觅者的指南

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

Pygame基础10-物理模拟

PyMunk PyMunk是一个模拟物理的库。 注意&#xff0c;PyMunk只是进行物理模拟&#xff0c;不包含可视化的功能。如果需要可视化&#xff0c;可使用pygame等库。 可用pip安装pymunk pip install pymunk pymunk中的概念&#xff1a; space&#xff1a; 物理空间。 包含gravity 模…...

蓝桥杯 --- 日期问题模板

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

Java 处理Mysql获取树形的数据

Mysql数据&#xff1a; 代码如下&#xff1a; Entity&#xff1a; Data Accessors(chain true) public class Region {private BigInteger id;//名称private String name;//父idprivate BigInteger parentId;private List<Region> children;private Integer createTim…...

前端三剑客 —— CSS ( 坐标问题 、定位问题和图片居中 )

前期内容回顾&#xff1a; 1.常见样式 text-shadow x轴 y轴 阴影的模糊程度 阴影的颜色 box-shadow border-radio 实现圆角 margin 内边距 padding 外边距 background 2.特殊样式 媒体查询&#xff1a;media 自定义字体&#xff1a;font-face { font-family:自定义名称&#…...

向量数据库 | AI时代的航道灯塔

向量数据库 | AI时代的航道灯塔 什么是向量检索服务拍照搜商品 你使用过向量数据库吗&#xff1f;使用体验&#xff1f;为什么向量数据库能借由大模型引起众多关注向量数据库在当前AI热潮中是昙花一现&#xff0c;还是未来AI时代的航道灯塔&#xff1f; 今天的话题主要是讨论向…...

Linux中的conntrack命令深入解析

在Linux网络管理和监控领域&#xff0c;conntrack命令是一个强大的工具&#xff0c;它提供了对netfilter连接跟踪系统的直接访问&#x1f50d;。这篇文章将深入探讨conntrack的由来、底层原理、参数意义&#xff0c;以及其常见用法&#xff0c;并对返回结果的每个字段进行详细解…...

反截屏控制技术如何防止信息通过手机拍照泄漏?

反截屏控制技术为企业数据安全提供了重要的防护措施。通过以下几点&#xff0c;有效阻止了信息通过拍照等方式的泄漏&#xff1a; 反截屏控制开启&#xff0c;用户启动截屏操作时&#xff0c;允许非涉密内容截屏操作&#xff0c;但所有涉密内容窗口会自动隐藏&#xff0c;防止涉…...

0.k8s简介

目录 k8s是什么 k8s不是什么 云原生 微服务 整体式架构与微服务架构 微服务的特性 微服务的优势 k8s是什么 Kubernetes 是一个可移植、可扩展的开源平台&#xff0c;用于管理容器化的工作负载和服务&#xff0c;可促进声明式配置和自动化。 Kubernetes 拥有一个庞大且快…...

VScode 集成终端设置默认打开当前文件夹 mac系统

一.快捷键设置 搜索 openInIntegratedTerminal 如图&#xff1a; 二.设置cmd 默认打开位置 点击设置 搜索 ntegrated:cwd 如下图&#xff1a; 三.查看ip 快捷指令&#xff1a; ipconfig getifaddr en0...

HDLbits 刷题 -- Alwaysblock2

学习&#xff1a; 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&#xff08;详细步骤&#xff09; 一、拉取镜像二、启动容器三、修改配置四、修改密码五、浏览器访问 一、拉取镜像 docker安装教程&#xff1a;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 数据&#xff1a; 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买家号注册下单容易死号?是什么原因导致?

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

【Linux】-进程知识铺垫①计算机硬件的组织:冯诺依曼体系结构详细解读②关于操作系统对软硬件及用户的意义

目录 ​编辑 1.关于计算机的体系结构 1.1 冯诺依曼体系结构的诞生 2.冯诺依曼体系结构 2.1 cpu:运算器&#xff1a;更多的是让cpu具有特殊的数据计算功能&#xff1a; 2.2 控制器 2.3输入设备 2.4输出设备 3.计算机各个硬件设备之间的关系 4.内存与计算机效率 5.关于为什么总说…...

让ECC升级S/4HANA一步到位的“全面升级方案包”

SAP最新一代商务套件S/4HANA比ECC系统拥有更高性能的存储数据库HANA、更个性化的Fiori用户界面设计系统&#xff0c;能够大大提升系统效率&#xff0c;带来便捷、高效、良好的用户体验。但企业原先使用的ECC系统里面保存了积累多年的关键流程和数据&#xff0c;让企业面对系统升…...

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…...

【网站项目】少儿编程管理系统

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

Python竞赛环境搭建全攻略

Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型&#xff08;算法、数据分析、机器学习等&#xff09;不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...

人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型

在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重&#xff0c;适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解&#xff0c;并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...