There is a tree (i.e., a connected, undirected graph that has no cycles) consisting of n
nodes numbered from 0
to n - 1
and exactly n - 1
edges. Each node has a value associated with it, and the root of the tree is node 0
.
To represent this tree, you are given an integer array nums
and a 2D array edges
. Each nums[i]
represents the ith
node’s value, and each edges[j] = [uj, vj]
represents an edge between nodes uj
and vj
in the tree.
Two values x
and y
are coprime if gcd(x, y) == 1
where gcd(x, y)
is the greatest common divisor of x
and y
.
An ancestor of a node i
is any other node on the shortest path from node i
to the root. A node is not considered an ancestor of itself.
Return an array ans
of size n
, where ans[i]
is the closest ancestor to node i
such that nums[i]
and nums[ans[i]]
are coprime, or -1
if there is no such ancestor.
Example 1:
Input: nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]] Output: [-1,0,0,1] Explanation: In the above figure, each node's value is in parentheses. - Node 0 has no coprime ancestors. - Node 1 has only one ancestor, node 0. Their values are coprime (gcd(2,3) == 1). - Node 2 has two ancestors, nodes 1 and 0. Node 1's value is not coprime (gcd(3,3) == 3), but node 0's value is (gcd(2,3) == 1), so node 0 is the closest valid ancestor. - Node 3 has two ancestors, nodes 1 and 0. It is coprime with node 1 (gcd(3,2) == 1), so node 1 is its closest valid ancestor.
Example 2:
Input: nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]] Output: [-1,0,-1,0,0,0,-1]
Constraints:
nums.length == n
1 <= nums[i] <= 50
1 <= n <= 105
edges.length == n - 1
edges[j].length == 2
0 <= uj, vj < n
uj != vj
Solution: DFS + Stack
Pre-compute for coprimes for each number.
For each node, enumerate all it’s coprime numbers, find the deepest occurrence.
Time complexity: O(n * max(nums))
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
// Author: Huahua class Solution { public: vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) { constexpr int kMax = 50; const int n = nums.size(); vector<vector<int>> g(n); for (const auto& e : edges) { g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); } vector<vector<int>> coprime(kMax + 1); for (int i = 1; i <= kMax; ++i) for (int j = 1; j <= kMax; ++j) if (gcd(i, j) == 1) coprime[i].push_back(j); vector<int> ans(n, INT_MAX); vector<vector<pair<int, int>>> p(kMax + 1); function<void(int, int)> dfs = [&](int cur, int d) { int max_d = -1; int ancestor = -1; for (int co : coprime[nums[cur]]) if (!p[co].empty() && p[co].back().first > max_d) { max_d = p[co].back().first; ancestor = p[co].back().second; } ans[cur] = ancestor; p[nums[cur]].emplace_back(d, cur); for (int nxt : g[cur]) if (ans[nxt] == INT_MAX) dfs(nxt, d + 1); p[nums[cur]].pop_back(); }; dfs(0, 0); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment