2024.4.11
题目来源
我的题解
方法一 深度优先遍历+回溯+存储父节点
使用一个List存储深度优先遍历过程中的父节点,然后从List的右侧开始遍历,直到与当前节点互质结束。
时间复杂度:O( n 2 n^2 n2)
空间复杂度:O(n+h)。h是树的高度,表示递归栈的空间
//会超时
public int[] getCoprimes(int[] nums, int[][] edges) {
int n=nums.length;
List<Integer>[] g=createGraph(n,edges);
int[] res=new int[n];
res[0]=-1;
List<Integer> l=new ArrayList<>();
l.add(0);
dfs(g,nums,l,res,0,-1);
return res;
}
public void dfs(List<Integer>[] g,int[] nums,List<Integer> parent,int[] res,int cur,int pre){
for(int next:g[cur]){
if(next!=pre){
res[next]=check(nums,next,parent);
parent.add(next);
dfs(g,nums,parent,res,next,cur);
parent.remove(parent.size()-1);
}
}
}
//获取互质的第一个祖先节点
public int check(int[] nums,int cur,List<Integer> parent){
int res=-1;
for(int i=parent.size()-1;i>=0;i--){
if(gcd(nums[cur],nums[parent.get(i)])==1){
res=parent.get(i);
break;
}
}
return res;
}
public List<Integer>[] createGraph(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 int gcd(int x,int y){
if(y==0)
return x;
return gcd(y,x%y);
}
方法二 官方深度优先遍历
没怎么看懂,自己看官方题解吧
有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈
标签:11,parent,nums,int,res,List,next,力扣,互质 From: https://blog.csdn.net/weixin_42075274/article/details/137628449