专栏首页算法修养LeetCode 1766. Tree of Coprimes

LeetCode 1766. Tree of Coprimes

题目

题意: 对于树上的每个节点,找出与它的值互质的最近的祖先节点。

题解: 由于节点上的值在1-50之间,所以算互质很好算,事先算法。然后就是深度优先遍历树的时候维护路径上的节点的位置,利用1-50这个小范围,快速找到与当前节点值互质的值出现在哪些位置上

struct Node
{
    int value;
    int next;
}edge[500005];

int head[100005];
int pos;
void init()
{
    memset(head,-1,sizeof(head));
    pos=0;
}

void add(int x,int y)
{
    edge[pos].value = y;
    edge[pos].next = head[x];
    head[x] = pos++;
}

int gcd(int x, int y)
{
    if(x<y)
        swap(x,y);
    
    return x%y==0 ? y : gcd(x%y, y); 
}

class Solution {
public:
    vector<int> p[55];
    int s[100005];
    int s_p;
    vector<int> a[55];
    int vis[100005];
    vector<int> ans;
    vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {
        
        init();
        for(int i=0;i<edges.size();i++)
        {
            add(edges[i][0], edges[i][1]);
            add(edges[i][1], edges[i][0]);
        }
        
        for(int i=1;i<=50;i++)
        {
            for(int j=1;j<=50;j++)
            {
                if(gcd(i,j)==1)
                {
                    p[i].push_back(j);
                }
            }
        }
        
        memset(vis,0,sizeof(vis));
        s_p=0;
        
        for(int i=0;i<nums.size();i++)
        {
            ans.push_back(0);
        }
        s[s_p] = 0;
        a[nums[0]].push_back(0);
        vis[0]=1;
        ans[0]=-1;
        dfs(0, nums);
        
        return ans;
        
        
    }
    
    void dfs(int root, vector<int>& nums)
    {
        
        
        for(int i=head[root]; i!=-1; i=edge[i].next)
        {
            int v = edge[i].value;
            if(vis[v]==1)
                continue;
            
            int res = -1;
            for(int j=0;j<p[nums[v]].size();j++)
            {
                if(a[p[nums[v]][j]].size()>0)
                {
                    res = max(res, a[p[nums[v]][j]][a[p[nums[v]][j]].size()-1]);
                }
            }
            
            if(res!=-1)
                ans[v] = s[res];
            else
                ans[v] = -1;
            
            vis[v]=1;
            
            s[++s_p] = v;
            a[nums[v]].push_back(s_p);
            
            dfs(v, nums);
            
            s_p--;
            a[nums[v]].pop_back();
        }
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 543. Diameter of Binary Tree

    Given a binary tree, you need to compute the length of the diameter of the tree....

    大学里的混子
  • LeetCode: Maximum Depth of Binary Tree

    Given a binary tree, find its maximum depth.

    卡尔曼和玻尔兹曼谁曼
  • 【leetcode】Minimum Depth of Binary Tree

    Given a binary tree, find its minimum depth.

    阳光岛主
  • 【leetcode】Maximum Depth of Binary Tree

    Given a binary tree, find its maximum depth.

    阳光岛主
  • Leetcode: Minimum Depth of Binary Tree

    题目: Given a binary tree, find its minimum depth.

    卡尔曼和玻尔兹曼谁曼
  • LeetCode 1516. Move Sub-Tree of N-Ary Tree(DFS)

    Given the root of an N-ary tree of unique values, and two nodes of the tree p an...

    Michael阿明
  • Leetcode 111 Minimum Depth of Binary Tree

    Given a binary tree, find its minimum depth. The minimum depth is the number o...

    triplebee
  • Leetcode 104 Maximum Depth of Binary Tree

    Given a binary tree, find its maximum depth. The maximum depth is the number o...

    triplebee
  • LeetCode 662. Maximum Width of Binary Tree

    Given a binary tree, write a function to get the maximum width of the given tree...

    大学里的混子
  • Leetcode-Easy 543. Diameter of Binary Tree

    543. Diameter of Binary Tree 描述: 求二叉树最长路径长度 ? 思路: 深度优先搜索 代码 # Definit...

    致Great
  • Leetcode-Easy 572. Subtree of Another Tree

    572. Subtree of Another Tree 描述: 给定两个二叉树s和t,判断t是否s的一个子树。要求结构完全一致 ? ? 思...

    致Great
  • Leetcode 104. Maximum Depth of Binary Tree

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • Leetcode 111. Minimum Depth of Binary Tree

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • leetcode: 111. Minimum Depth of Binary Tree

    JNingWei
  • leetcode: 104. Maximum Depth of Binary Tree

    JNingWei
  • 【LeetCode】104. Maximum Depth of Binary Tree

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • LeetCode 112 Minimum Depth of Binary Tree

    ShenduCC
  • LeetCode 104 Maximum Depth of Binary Tree

    给予一颗二叉树,返回其树的深度。 最大深度是从根节点到最远叶节点的最长路径上的节点数。

    一份执着✘
  • LeetCode 0104 - Maximum Depth of Binary Tree

    Given a binary tree, find its maximum depth.

    Reck Zhang

扫码关注云+社区

领取腾讯云代金券