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

怎么用dw做动态网站网络推广员招聘

怎么用dw做动态网站,网络推广员招聘,网上接手袋做是哪一个网站,如何利用网站新闻做推广LeetCode-1766. 互质树【树 深度优先搜索 广度优先搜索 数组 数学 数论】 题目描述&#xff1a;解题思路一&#xff1a;DFS 中记录节点值的深度和编号&#xff0c;回溯写法。关键点是1 < nums[i] < 50解题思路二&#xff1a;0解题思路三&#xff1a;0 题目描述&#xff1…

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)

http://www.tj-hxxt.cn/news/83683.html

相关文章:

  • 南昌做购物网站的公司关键词搜索
  • 北京哪家公司做网站好贺州seo
  • 成都html5网站建设百度如何推广广告
  • 公司的独立网站深圳抖音推广
  • 天津建设交通委网站sem竞价托管费用
  • 湘潭网站建设方案案例营销策划方案内容
  • 千博企业网站管理系统完整版 2014找竞价托管公司
  • 安庆做网站电话网站设计专业的公司
  • 个人网站怎么注册百度推广怎么推广
  • 设计网站名称google seo怎么优化
  • 网站200m虚拟主机能放多少东西有哪些网站可以免费发布广告
  • 建材做网销哪个网站好杭州百度首页排名
  • 国家卫生健康委员会官网电子注册苏州网站建设优化
  • 做网站电话沧州搭建网站工具
  • 怎么上传做 好的网站吗外贸网站模板
  • 瑞安公司做网站源码交易网站源码
  • 跟做竞价的网站友情链接有用吗微信广告推广价格表
  • 网站数据库文件名南宁网站seo外包
  • 百度公司网站排名怎么做广州百度seo代理
  • 西安专业网站建设价格福州seo视频
  • 绵阳科技网站建设网络软文
  • 手机百度网页版郑州seo排名工具
  • 建设通网站是筑龙网的吗seo关键词排名优化报价
  • 泉州网站建设技术公司南宁seo外包服务
  • 海淀制作网站的公司黄页污水
  • 点开图片跳到网站怎么做的网页设计与制作步骤
  • 做兼职什么网站靠谱2345电脑版网址导航
  • wordpress主题定制推广优化网站排名教程
  • 住房和城乡建设部网站评估哪些网站可以免费申请域名
  • 一个公司做网站需要注意什么做网站推广一般多少钱