首页 > 其他分享 >Leetcode 952. 按公因数计算最大组件大小

Leetcode 952. 按公因数计算最大组件大小

时间:2024-09-17 13:34:50浏览次数:7  
标签:nums self 952 num uf root Leetcode roots 公因数

1.题目基本信息

1.1.题目描述

给定一个由不同正整数的组成的非空数组 nums ,考虑下面的图:

  • 有 nums.length 个节点,按从 nums[0] 到 nums[nums.length - 1] 标记;
  • 只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时,nums[i] 和 nums[j]之间才有一条边。

返回 图中最大连通组件的大小。

1.2.题目地址

https://leetcode.cn/problems/largest-component-size-by-common-factor/description

2.解题方法

2.1.解题思路

并查集+求质因数

2.2.解题步骤

第一步,遍历每个数字num,并获取每个数字的各个质因数,将质因数和num在并查集中进行连接到同一个集合中

第二步,遍历,遍历每一个num,获取每个数在并查集中的root,统计相同root的num的个数,个数最大的那个即为最大连通组件的大小

3.解题代码

Python代码

from collections import defaultdict

# # ==> 并查集模板(附优化)
class UnionFind():
    def __init__(self):
        self.roots={}
        # Union优化:存储根节点主导的集合的总节点数
        self.rootSizes={}
    
    def add(self,x):
        if x not in self.roots:
            self.roots[x]=x
            self.rootSizes[x]=1
    
    def find(self,x):
        root=x
        while root != self.roots[root]:
            root=self.roots[root]
        # 优化:压缩路径
        while x!=root:
            temp=self.roots[x]
            self.roots[x]=root
            x=temp
        return root
    
    def union(self,x,y):
        rootx,rooty=self.find(x),self.find(y)
        if rootx!=rooty:
            # 优化:小树合并到大树上
            if self.rootSizes[rootx]<self.rootSizes[rooty]:
                self.roots[rootx]=rooty
                self.rootSizes[rooty]+=self.rootSizes[rootx]
            else:
                self.roots[rooty]=rootx
                self.rootSizes[rootx]+=self.rootSizes[rooty]


# 获取一个正整数的各个分解的质因素及数量;生成的item为(质因数,数量)
def getNumFactors(num):
    factor=2
    while factor*factor<=num:
        if num%factor==0:
            cnt=0
            while num%factor==0:
                cnt+=1
                num=num//factor
            yield (factor,cnt)
        factor+=1
    if num>1:
        yield (num,1)

class Solution:
    def largestComponentSize(self, nums: List[int]) -> int:
        uf=UnionFind()
        for num in nums:
            if num==1:
                continue
            for factor,_ in getNumFactors(num):
                uf.add(num)
                uf.add(factor)
                uf.union(num,factor)
        result=0
        cntMap=defaultdict(int)
        for num in nums:
            if num==1:
                continue
            numRoot=uf.find(num)
            cntMap[numRoot]+=1
            result=max(result,cntMap[numRoot])
        # print(result)
        return result

4.执行结果

在这里插入图片描述

标签:nums,self,952,num,uf,root,Leetcode,roots,公因数
From: https://www.cnblogs.com/geek0070/p/18417109

相关文章

  • Leetcode 19.删除链表的倒数第第N个结点
    1.题目基本信息题目:给你一个链表,删除链表的倒数第n个结点,并且返回链表的头结点。地址:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/2.解题方法2.1.解题思路使用快慢指针2.2.解题步骤第一步,初始化快指针为head,慢指针指向一个哑结点,哑结点......
  • Leetcode 2183. 统计可以被 K 整除的下标对数目
    1.题目基本信息1.1.题目描述给你一个下标从0开始、长度为n的整数数组nums和一个整数k,返回满足下述条件的下标对(i,j)的数目:0<=i<j<=n-1且nums[i]*nums[j]能被k整除。1.2.题目地址https://leetcode.cn/problems/count-array-pairs-divisible-by-k......
  • Leetcode—815. 公交路线【困难】(unordered_map+queue)
    2024每日刷题(163)Leetcode—815.公交路线bfs实现代码classSolution{public:intnumBusesToDestination(vector<vector<int>>&routes,intsource,inttarget){if(source==target){return0;}unordered_map<......
  • Java LeetCode每日一题
            1184.公交站间的距离    需求:        环形公交路线上有n个站,按次序从0到n-1进行编号。我们已知每一对相邻公交站之间的距离,distance[i]表示编号为i的车站和编号为(i+1)%n的车站之间的距离。        环线上的公交......
  • Day17 二叉树part07| LeetCode 235. 二叉搜索树的最近公共祖先 ,701.二叉搜索树中的插
    235.二叉搜索树的最近公共祖先235.二叉搜索树的最近公共祖先利用二叉搜索树的特性——有序树,可知,如果中间节点是p和q的公共节点,那个中间节点的数值一定在[p,q]区间因此,从根节点往下搜索,遇到的第一个位于[p,q]或[q,p]区间的节点就是最近公共祖先classSolution{......
  • LeetCode题集-4 - 寻找两个有序数组的中位数,图文并茂,六种解法,万字讲解
    题目:给定两个大小分别为m和n的正序(从小到大)数组nums1和nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为O(log(m+n))。作为目前遇到的第一个困难级别题目,我感觉这题还是挺难的,研究了三天总算研究明白了,下面就给大家分享一下这题的几种解法,请......
  • leetcode刷题day20|二叉树Part08(669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索
    669.修剪二叉搜索树思路:理解了删除二叉搜索树中的节点,这个题理解起来就不难了。还是选用中序遍历递归。递归三步曲:1、传入参数:根节点,最小值,最大值;返回值为根节点;2、终止条件:如果节点为空,直接返回空;3、递归逻辑:如果最小值小于该节点,递归调用该节点的右孩子(检查右孩子......
  • leetcode刷题day19|二叉树Part07(235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的
    235.二叉搜索树的最近公共祖先思路:二叉搜索树首先考虑中序遍历。根据二叉搜索树的特性,如果p,q分别在中间节点的左右两边,该中间节点一定是最近公共祖先,如果在同一侧,则递归这一侧即可。递归三部曲:1、传入参数:根节点,p,q,返回节点。2、终止条件:因为p,q一定存在,所以不会遍历到......
  • Day16 二叉树part06| LeetCode 530.二叉搜索树的最小绝对差 ,501.二叉搜索树中的众数,23
    530.二叉搜索树的最小绝对差530.二叉搜索树的最小绝对差classSolution{publicList<Integer>res=newArrayList<>();voidtraversal(TreeNoderoot){if(root==null)return;traversal(root.left);......
  • C++速通LeetCode简单第17题-爬楼梯
    思路要点:将问题转化为求斐波那契数列的第n项,然后迭代。思路分析:最后一次爬的阶数不是1就是2,假设爬n阶的方法数是f(n),假设最后一次爬1阶,那么爬前面的n-1阶的方法数是f(n-1);假设最后一次爬2阶,那么爬前面n-1阶的方法数是f(n-2)。所以可以得到:f(n)=f(n-1)+f(n-2),也就是斐波......