LeetCode-1766. 互质树【树 深度优先搜索 广度优先搜索 数组 数学 数论】
LeetCode-1766. 互质树【树 深度优先搜索 广度优先搜索 数组 数学 数论】
- 题目描述:
- 解题思路一:DFS 中记录节点值的深度和编号,回溯写法。关键点是1 <= nums[i] <= 50
- 解题思路二:0
- 解题思路三:0
题目描述:
给你一个 n 个节点的树(也就是一个无环连通无向图),节点编号从 0 到 n - 1 ,且恰好有 n - 1 条边,每个节点有一个值。树的 根节点 为 0 号点。
给你一个整数数组 nums 和一个二维数组 edges 来表示这棵树。nums[i] 表示第 i 个点的值,edges[j] = [uj, vj] 表示节点 uj 和节点 vj 在树中有一条边。
当 gcd(x, y) == 1 ,我们称两个数 x 和 y 是 互质的 ,其中 gcd(x, y) 是 x 和 y 的 最大公约数 。
从节点 i 到 根 最短路径上的点都是节点 i 的祖先节点。一个节点 不是 它自己的祖先节点。
请你返回一个大小为 n 的数组 ans ,其中 ans[i]是离节点 i 最近的祖先节点且满足 nums[i] 和 nums[ans[i]] 是 互质的 ,如果不存在这样的祖先节点,ans[i] 为 -1 。
示例 1:

输入:nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
输出:[-1,0,0,1]
解释:上图中,每个节点的值在括号中表示。
- 节点 0 没有互质祖先。
- 节点 1 只有一个祖先节点 0 。它们的值是互质的(gcd(2,3) == 1)。
- 节点 2 有两个祖先节点,分别是节点 1 和节点 0 。节点 1 的值与它的值不是互质的(gcd(3,3) == 3)但节点 0 的值是互质的(gcd(2,3) == 1),所以节点 0 是最近的符合要求的祖先节点。
- 节点 3 有两个祖先节点,分别是节点 1 和节点 0 。它与节点 1 互质(gcd(3,2) == 1),所以节点 1 是离它最近的符合要求的祖先节点。
示例 2:

输入:nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
输出:[-1,0,-1,0,0,0,-1]
提示:
nums.length == n
1 <= nums[i] <= 50
1 <= n <= 105
edges.length == n - 1
edges[j].length == 2
0 <= uj, vj < n
uj != vj
解题思路一:DFS 中记录节点值的深度和编号,回溯写法。关键点是1 <= nums[i] <= 50
对于节点 x,我们需要计算节点值与 nums[x] 互质的最近祖先节点是哪个。
最暴力的做法是,枚举 x 的所有祖先节点。但如果这棵树是一条链,枚举 x 的所有祖先节点需要 O(n) 的时间,每个点都这样枚举的话,总共需要 O(n2) 的时间,太慢了。
注意到,所有节点的节点值都不超过 50,我们可以枚举 [1,50] 中与 nums[x] 互质的数。由于要计算的是「最近」祖先,对于节点值相同的祖先,只需枚举深度最大的。因此,对于节点 x,我们至多枚举它的 50 个祖先。这样总共只需要 O(nU) 的时间,其中 U=50。
具体来说,我们需要在递归这棵树的同时,维护两组信息:
- valDepth 数组。其中 valDepth[j] 保存节点值等于 j 的最近祖先的深度。
- valNodeId 数组。其中 valNodeId[j] 保存节点值等于 j 的最近祖先的节点编号。
设当前节点值为 val=nums[x],我们枚举 [1,50] 中与 val互质的数字 j,计算出 valDepth[j] 的最大值,及其对应的节点编号,即为答案 ans[x]。
代码实现时,可以预处理 [1,50]中有哪些数对是互质的。
# 预处理:coprime[i] 保存 [1, MX) 中与 i 互质的所有元素
MX = 51
coprime = [[j for j in range(1, MX) if gcd(i, j) == 1]for i in range(MX)]
class Solution:def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:n = len(nums)g = [[] for _ in range(n)]for x, y in edges:g[x].append(y)g[y].append(x)ans = [0] * nval_depth_id = [(-1, -1)] * MX # 包含深度和节点编号def dfs(x: int, fa: int, depth: int) -> None:val = nums[x] # x 的节点值# 计算与 val 互质的祖先节点值中,节点深度最大的节点编号ans[x] = max(val_depth_id[j] for j in coprime[val])[1]tmp = val_depth_id[val] # 用于恢复现场val_depth_id[val] = (depth, x) # 保存 val 对应的节点深度和节点编号for y in g[x]:if y != fa:dfs(y, x, depth + 1)val_depth_id[val] = tmp # 恢复现场dfs(0, -1, 0)return ans
时间复杂度:O(n)
空间复杂度:O(n)
解题思路二:0
时间复杂度:O(n)
空间复杂度:O(n)
解题思路三:0
时间复杂度:O(n)
空间复杂度:O(n)
相关文章:
LeetCode-1766. 互质树【树 深度优先搜索 广度优先搜索 数组 数学 数论】
LeetCode-1766. 互质树【树 深度优先搜索 广度优先搜索 数组 数学 数论】 题目描述:解题思路一:DFS 中记录节点值的深度和编号,回溯写法。关键点是1 < nums[i] < 50解题思路二:0解题思路三:0 题目描述࿱…...
“数据安全服务能力”评定资格认证!不容错过
数据安全服务能力评定是指对数据安全服务提供商从事数据安全服务综合能力的评定,包括技术能力、服务能力、质量保证能力、人员构成与素质、经营业绩、资产状况等要素。 一、能力评定类型与等级 数据安全服务能力分为二个类型:数据安全评估、数据安全建…...
【MATLAB 分类算法教程】_3麻雀搜索算法优化支持向量机SVM分类 - 教程和对应MATLAB代码
分类代码案例3:麻雀搜索算法优化支持向量机SVM分类 - MATLAB完全代码教程 1. 初始化代码2.读取数据代码3.数据预处理代码4.利用麻雀搜索算法SSA求解最佳的SVM参数c和g代码5.根据最佳的参数进行SVM模型训练代码6.SVM模型预测代码7.准确率分析以及分类结果对比作图代码本文以红酒…...
利用机器学习库做动态定价策略的例子
动态定价是一个复杂的问题,涉及到市场需求、库存、竞争对手行为、季节性因素等多个变量。在实际应用中,动态定价通常需要复杂的模型和大量的数据分析。我选择使用Python(Golearn库)进行机器学习模型的训练和部署,而将G…...
Tcpdump -r 解析pcap文件
当我们使用命令抓包后,想在命令行直接读取筛选怎么办?-r参数就支持了这个 当你使用 tcpdump 的 -r 选项读取一个之前捕获的数据包文件,并想要筛选指定 IP 地址和端口的包时,你可以在命令中直接加入过滤表达式。这些过滤表达式可以…...
[dvwa] sql injection(Blind)
blind 0x01 low 1’ and length(version()) 6 # syntax: substr(string , from<start from 1>, cut length) 1’ and substr(version(),1,1) ‘5’ # 1’ and substr(version(),2,1) ‘.’ # 1’ and substr(version(),3,1) ‘7’ # 1’ and substr(version(),4,…...
linux 挂载云盘 NT只能挂载2T,使用parted挂载超过2T云盘
一、删除原来挂载好的云盘和分区 1、查看挂载号的云盘 fdisk -l 发现我们有5千多G但是只挂载了2T,心里非常的慌张!十分的不爽! 好,我们把它干掉,重新分区! 2、解除挂载 umount /homeE 没保存跳转到&…...
用Skimage学习数字图像处理(021):图像特征提取之线检测(下)
本节是特征提取之线检测的下篇,讨论基于Hough变换的线检测方法。首先简要介绍Hough变换的基本原理,然后重点介绍Skimage中含有的基于Hough变换的直线和圆形检测到实现。 目录 10.4 Hough变换 10.4.1 原理 10.4.2 实现 10.4 Hough变换 Hough变换&…...
ArduPilot飞控之Gazebo + SITL + MP的Jetson Orin环境搭建
ArduPilot飞控之Gazebo SITL MP的Jetson Orin环境搭建 1. 源由2. Linux环境整理3. 安装Gazebo环境3.1 安装Gazebo3.2 安装插件3.3 配置插件3.4 测试Gazebo 4. 安装Arudpilot-SITL环境4.1 克隆工程4.2 编译准备4.3 环境配置4.4 配置编译4.5 测试运行 5. 测试运行6. 参考资料 1…...
前端错误监控的方法有哪些
前端错误监控是指通过各种手段收集、分析和处理前端应用运行中发生的错误 常用的前端错误监控的方法有 使用 try catch 方法 捕获特定代码块中的错误多用于处理特定函数或代码段可能抛出的异常,尤其是异步代码网络请求错误监控 promise.catchtry catch全局错误处理…...
✌粤嵌—2024/3/11—跳跃游戏
代码实现: 方法一:递归记忆化 int path; int used[10000];bool dfs(int *nums, int numsSize) {if (path numsSize - 1) {return true;}for (int i 1; i < nums[path]; i) {if (used[path i]) {continue;}path i;used[path] 1;if (dfs(nums, num…...
Docker入门实战教程
文章目录 Docker引擎的安装Docker比vm虚拟机快 Docker常用命令帮助启动类命令镜像命令docker imagesdocker searchdocker pulldocker system dfdocker rmi 容器命令redis前台交互式启动redis后台守护式启动Nginx容器运行ubuntu交互式运行tomcat交互式运行对外暴露访问端口 Dock…...
数据结构初阶:二叉树(一)
树概念及结构 树的概念 树是一种 非线性 的数据结构,它是由 n ( n>0 )个有限结点组成一个具有层次关系的集合。 把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的 。 有一个特殊的结点&a…...
基于逻辑回归和支持向量机的前馈网络进行乳腺癌组织病理学图像分类
CNN(卷积神经网络)通过使用反向传播方法来学习特征,这种方法需要大量的训练数据,并且存在梯度消失问题,从而恶化了特征学习。 CNN卷积神经网络 CNN由一个多层神经网络组成,该网络从标记的训练数据集中学习…...
35-4 fastjson漏洞复现
环境准备:35-2 fastjson反序列化漏洞介绍 及漏洞环境搭建-CSDN博客 fastjson_tool.jar下载:fastjson_rce_tool: fastjson命令执行自动化利用工具, remote code execute,JNDI服务利用工具 RMI/LDAP (gitee.com) 一、攻击机kali开启nc监听6666端口(或其他端口也行,只要不…...
Qt-控件篇
QPushbutton 1、设置按钮文本 pushButton->setText("按钮"); 2、获取按钮文本 pushButton->text(); 3、设置按钮的大小为特定值(宽度和高度) pushButton->setFixedSize(width,height); 4、设置按钮悬停时的工具提示文本。 pushButto…...
实现 Table 的增加和删除,不依赖后端数据回显
需求 删除前 删除后 分析 首先写一个 Table <a-card style"width:100%"><template#extra><a-button type"text" click"addSelectItem" style"margin-right: 5px">添加</a-button><a-button type&quo…...
个人网站开发记录(七)——三系统后端nodejs+express
前言 这种已经完全工程化了的()后端其实已经没啥好说的了,因为就是单纯的写接口然后调用接口就完事了! 正文 唯一值得一提的大概是我在写这个系统的时候搞了https的链接,具体来说就是先申请一个ssl证书,…...
C#入门理解设计模式的6大原则
**设计模式的原则是指导设计模式创建和应用的基本原则,这些原则有助于创建灵活、可维护且可扩展的软件系统。**1. 单一职责原则(Single Responsibility Principle, SRP) 单一职责原则指出一个类应该只有一个引起它变化的原因。换句话说&…...
Linux如何切换root用户
Linux如何切换root用户 sudosudo -i想一直使用root权限,可以使用su命令 sudo 执行命令后,输入用户密码可以短暂的获取root权限 sudo -i 通过此命令直接输入当前管理员用户的密码就可以进入root用户了 想一直使用root权限,可以使用su命令 …...
uniapp圆环进度条组件实战:从零到一打造个性化数据展示
Uniapp圆环进度条组件实战:从零到一打造个性化数据展示 在移动应用开发中,数据可视化是提升用户体验的关键因素之一。圆环进度条作为一种直观的数据展示方式,广泛应用于健身追踪、学习进度、任务完成度等场景。Uniapp作为跨平台开发框架&…...
【离线无忧】PyAutoGUI内网环境高效安装指南
1. 为什么需要离线安装PyAutoGUI? 最近接手了一个自动化测试项目,需要在完全隔离的内网环境中部署PyAutoGUI。刚开始觉得这不过是个普通的Python包,直到发现服务器连pip都跑不通时才意识到问题的严重性。这种场景在企业开发中其实非常常见—…...
从智慧灯杆到无人驾驶:如何用Raspberry Pi 4和Arduino搭建微型智慧城市实验平台
从智慧灯杆到无人驾驶:如何用Raspberry Pi 4和Arduino搭建微型智慧城市实验平台 在创客文化和高校工程教育中,低成本硬件的创新应用正掀起一场微型智慧城市实验的革命。只需一块树莓派主板、几个传感器和开源软件,就能在桌面上复现价值数百万…...
微信聊天记录永久保存与智能分析:WeChatMsg完全使用指南
微信聊天记录永久保存与智能分析:WeChatMsg完全使用指南 【免费下载链接】WeChatMsg 提取微信聊天记录,将其导出成HTML、Word、CSV文档永久保存,对聊天记录进行分析生成年度聊天报告 项目地址: https://gitcode.com/GitHub_Trending/we/WeC…...
AI神器10秒搞定网申,求职效率翻倍
投简历填表单填到崩溃?这个AI神器帮你10秒搞定网申,海投效率直接拉满! 秋招春招跑过招聘季的朋友,一定都懂这种窒息感: 好不容易筛好了目标公司,点开招聘官网,迎面而来就是几十项的简历表单。姓名、电话、邮箱、教育经历从高中填到大学、实习经历要写清每段的起止时间…...
手把手教你用STM32实现BLDC电机的SPWM控制(附代码调试心得)
STM32实战:无刷直流电机SPWM控制全解析与代码优化指南 从理论到实践:BLDC电机控制的核心逻辑 第一次接触无刷直流电机(BLDC)控制时,我被它优雅的工作原理所吸引——没有电刷的火花和磨损,却能实现高效的能量转换。在工业自动化、无…...
为什么90%的Python项目误用SM9?——基于NIST SP 800-56A rev3与GB/T 38635.2的合规性性能审计清单
第一章:SM9密码算法的合规性认知误区与审计必要性在国产密码应用推广过程中,SM9标识密码体系常被误认为“天然合规”——仅因列入《GB/T 38635.1—2020 信息安全技术 SM9标识密码算法 第1部分:总则》即等同于满足等保2.0、密评及《商用密码管…...
OpenClaw对接Qwen3-VL:30B:飞书智能助手配置
OpenClaw对接Qwen3-VL:30B:飞书智能助手配置 1. 为什么选择这个组合? 去年我在团队内部尝试搭建一个能处理图片和文本的智能助手时,遇到了三个痛点:一是商业API调用成本太高,二是数据安全性无法保证,三是…...
wan2.1-vae提示词评估体系:构建BLEU-Style指标量化中文提示词有效性
wan2.1-vae提示词评估体系:构建BLEU-Style指标量化中文提示词有效性 1. 为什么需要评估提示词质量 在AI图像生成领域,提示词的质量直接影响最终生成效果。好的提示词能准确表达创作意图,而模糊或不当的提示词可能导致生成结果与预期不符。特…...
Ryujinx开源项目:跨平台Switch游戏模拟解决方案
Ryujinx开源项目:跨平台Switch游戏模拟解决方案 【免费下载链接】Ryujinx 用 C# 编写的实验性 Nintendo Switch 模拟器 项目地址: https://gitcode.com/GitHub_Trending/ry/Ryujinx 在数字化娱乐日益普及的今天,如何让Nintendo Switch游戏突破硬件…...
