当前位置：首页 > news >正文

1766. 互质树 DFS+桶

news 来源：原创 2024/5/18 14:50:25

1766. 互质树

给你一个 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 <= 1e5
edges.length == n - 1
edges[j].length == 2
0 <= uj, vj < n
uj != vj

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/tree-of-coprimes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功，一开始写dfs，没注意1e5的问题，超时，草率了。num值只有50，所以可以用哈希和桶处理，很有意思的题目。

方法：DFS+桶

1.50个数预处理是否互质，直接用 50*50 的二维数组保存

2. 用边合成图

3. dfs求解

3. 特殊优化：由于只有50个值，只要最近的祖先。那么对于相同值的两个祖先只选最近的，所以后遍历的更深的同值元素可以替代之前的。用个哈希代表桶即可，每个桶装索引和深度，由于是1-50，也可以直接用数组表示

4. 比较，桶内满足是互质的元素中，选取最深的元素，把当前的父节点填为这个元素即可

class Solution {
        boolean [][]isPrime = new boolean[51][51];
        int[] ans;
        int[] nums;
    public int[] getCoprimes(int[] nums, int[][] edges) {
        for(int i = 1; i <= 50; i++) Arrays.fill(isPrime[i],true);
        for(int i = 2; i <= 50; i++){
            for(int j = i; j<=50; j++){
                int gcd = gcd(i,j);
                if(gcd!=1) isPrime[i][j]=isPrime[j][i] = false;
            }
        }

        this.nums = nums;
        int n = nums.length;
        ans = new int[n];
        Arrays.fill(ans,-1);
        Set<Integer> []graph = new HashSet[n];
        Arrays.setAll(graph,o->new HashSet<>());
        for(int []edge:edges){
            int a = edge[0];
            int b = edge[1];
            graph[a].add(b);
            graph[b].add(a);
        }

        fillGCD(graph,new HashMap<>(),0,-1,1);
        return ans;
    }

    private void fillGCD(Set<Integer> []graph, Map<Integer,int[]> parents, int index,int p,int deep){
        int n = parents.size();
        int maxDeep = -1;
        int id = -1;
        for(int key:parents.keySet()){
            if(isPrime[key][nums[index]]&&parents.get(key)[1]>maxDeep){
                int[] item = parents.get(key);
                maxDeep = item[1];
                id = item[0];
            }
        }
        ans[index] = id;

        int[] pre = parents.getOrDefault(nums[index],new int[]{-1,-1});
        parents.put(nums[index],new int[]{index,deep});
        for(int next:graph[index]){
            if(next==p) continue;
            fillGCD(graph,parents,next,index,deep+1);
        }
        parents.put(nums[index],pre);
    }

    private int gcd(int a, int b){
        return b==0?a:gcd(b,a%b);
    }
}