首页 > 其他分享 >2024.4.11力扣每日一题——互质树

2024.4.11力扣每日一题——互质树

时间:2024-04-11 10:59:55浏览次数:32  
标签:11 parent nums int res List next 力扣 互质

2024.4.11

题目来源

力扣每日一题;题序:1766

我的题解

方法一 深度优先遍历+回溯+存储父节点

使用一个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

相关文章

  • 升级到windows 11后无法连接公司的WIFI
    电脑升级到win11后,就无法连接到公司的域WIFI了。其他输密码的WIFI都是正常的,包括手机热点的WIFI都可以正常连接就是无法连接到公司的加域的WIFI。重新加域,重新安装驱动,都试过了,还是不行。网上到处找解决方案。终于找到一个靠谱的问题定位到:CredentialGuard原来从Windows......
  • 【题解】CF311E Biologist题解
    CF311EBiologist题解非常好的一道最小割。思路首先看到每一个位置又会有\(01\)两种情况,然后要满足一些要求,求最大收益,考虑类似于P4313文理分科和P1361小M的作物这种集合划分的建图方法,也就是要用最小割求解。由于我们要求的是最大收益,所以我们要先明确要最小化什么,......
  • 【题解】CF1187G Gang Up
    【题解】CF1187GGangUp题意给定一个图,有\(k\)个人要走到\(1\)号节点,问最小花费。解法一眼丁真,鉴定为费用流。考虑到这道题花费会与时间有关,所以分层图,启动!。按时刻分层,现在分析每个人在第\(k\)时刻的动向:1.呆着不动。2.走到下一个节点。对于动向\(1\),从时......
  • 2024-04-11 记录日常业务之遍历对象并删除不符合条件的属性
    为什么要记录,因为很少遇到这种奇葩的需求,后端要我不要返回对象中所有值为-1的字段,我就纳了闷了,你就不能自己处理吗??好了,不吐槽了,主要是较少去处理遍历对象的操作(历来都是遍历数组),所以在这里做个记录:letparams={ a:10, b:6, c:-1, d:11, e:19, f:-1,......
  • Windows11长开无故自动重启解决办法
    1.创建后缀为.cmd的文件,写入以下内容后以管理员身份打开点击查看代码@echooffpushd"%~dp0"dir/bC:\Windows\servicing\Packages\Microsoft-Windows-GroupPolicy-ClientExtensions-Package~3*.mum>List.txtdir/bC:\Windows\servicing\Packages\Microsoft-Windows-G......
  • 修复Win11更新后Type-C耳机无声的问题
    环境超市随便买的不知名Type-C耳机电脑:华硕天选3系统:windows1123H2问题之前一直使用这副耳机,但是有一次更新之后,忽然没有声音了,华硕天选3是有连个type-c接口的,反复试了都不行,今天有空再试了一下,歪打正着修复过程首先检查音频输出设备是否选择了耳机没有问题后,去扬......
  • C/C++学习笔记-eclipse不支持C++11问题
    转 https://blog.csdn.net/qq_35703954/article/details/81540315std::thread的使用,结果编译报错信息如下: 问题分析:查看错误提示,发现thread不是命名空间std的一个成员,那么我们知道thread很明显是std的成员,那么久只有一种可能:即没有引入相关的头文件,但是检查发现,头文件也有。又......
  • 2024.4.11 Pytorch上手2 //
    Pytorch上手2ToTensor()是一个转换操作,它将PIL图片或者NumPyndarray转换成FloatTensor,并且把每一个数值归一化到[0,1]区间(原先的数值区间为[0,255])。这一步是为了方便后续的数值处理和模型训练。Pillow库介绍:Pillow是Python中一个流行的图像处理库,它是著名的PIL(Pyt......
  • CF1162B Double Matrix 题解
    传送门说句实话,如果不是先写了Showstopper这道题的话,我应该会在这里卡很久,因为做Showstopper我就卡了很久QwQ。思路太像了,实在是太像了,与Showstopper想比,仅仅就是换成二维数组,求最大值变为找递增矩阵,处理方法一模一样:将数组\(a\)和\(b\)中较小的值存在一个数组里,较......
  • 【异常】FATAL ERROR in native method: JDWP loaded classes, jvmtiError=JVMTI_ERRO
    一、异常内容IDEA启动微服务之后,提示FATALERRORinnativemethod:JDWPloadedclasses,jvmtiError=JVMTI_ERROR_OUT_OF_MEMORY(110)FATALERRORinnativemethod:JDWPloadedclasses,jvmtiError=JVMTI_ERROR_OUT_OF_MEMORY(110) atsun.misc.Unsafe.defineAnonym......