本文主要是介绍稀碎从零算法笔记Day46-LeetCode:互质树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
这几天有点懈怠了
题型:树、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 == n
1 <= nums[i] <= 50
1 <= n <= 105
edges.length == n - 1
edges[j].length == 2
0 <= uj, vj < n
uj != vj
题目思路(纯看的灵茶山艾府的题解,无思路)
题目都没看懂....
C++代码
vector<int>coprime[51];//50哥节点极限是,那就将1-50的情况都表示出来//初始化coprime数组auto init = []{for(int i = 1;i<51;i++)for(int j = 1;j<51;j++){if(gcd(i,j) == 1)//如果最大公因数为1 其中j是i的父亲{coprime[i].push_back(j);}}return 0;}();class Solution {
public:vector<vector<int>> g;vector<int>answer;//答案pair<int,int>depth_pair[51] ;//深度 编号//dfsvoid dfs(int x,int fa,int depth,vector<int> &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;}vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& 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;}
};
结算页面
这篇关于稀碎从零算法笔记Day46-LeetCode:互质树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!