住房和城乡建设部网站干部学院,做网站需要什么手续资料,班级网站 模板,基层组织建设部 网站这几天有点懈怠了
题型#xff1a;树、DFS、BSF、数学
链接#xff1a;1766. 互质树 - 力扣#xff08;LeetCode#xff09;
来源#xff1a;LeetCode
题目描述
给你一个 n 个节点的树#xff08;也就是一个无环连通无向图#xff09;#xff0c;节点编号从 0 到 …这几天有点懈怠了
题型树、DFS、BSF、数学
链接1766. 互质树 - 力扣LeetCode
来源LeetCode
题目描述
给你一个 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 n1 nums[i] 501 n 105edges.length n - 1edges[j].length 20 uj, vj nuj ! vj
题目思路纯看的灵茶山艾府的题解无思路
题目都没看懂....
C代码 vectorintcoprime[51];//50哥节点极限是那就将1-50的情况都表示出来//初始化coprime数组auto init []{for(int i 1;i51;i)for(int j 1;j51;j){if(gcd(i,j) 1)//如果最大公因数为1 其中j是i的父亲{coprime[i].push_back(j);}}return 0;}();class Solution {
public:vectorvectorint g;vectorintanswer;//答案pairint,intdepth_pair[51] ;//深度 编号//dfsvoid dfs(int x,int fa,int depth,vectorint nums){int val nums[x];int max_depth 0;for(int temp : coprime[val]){auto [depth,id] depth_pair[temp];if(depth max_depth){max_depth depth;answer[x] id;}}auto tmp depth_pair[val]; depth_pair[val] {depth,x};for(int y : g[x])if(y ! fa)dfs(y,x,depth 1 ,nums);//递归depth_pair[val] tmp;}vectorint getCoprimes(vectorint nums, vectorvectorint edges) {int n nums.size();g.resize(n);for(auto e : edges){int x e[0], y e[1];g[x].push_back(y);g[y].push_back(x);}answer.resize(n ,-1);dfs(0,-1,1,nums);return answer;}
};
结算页面
