Сложность: hard
Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае.
Пример:
Input: nums = [4,6,15,35]
Output: 4
👨💻 Алгоритм:
1⃣Построить граф, в котором узлы представляют числа из массива, а ребра между узлами существуют, если два числа имеют общий делитель больше 1.
2⃣Использовать алгоритм Union-Find для объединения узлов в связные компоненты.
Для каждого числа в массиве nums найти его простые делители и использовать их для объединения узлов.
3⃣Найти размер наибольшей связной компоненты.
😎 Решение:
from collections import defaultdict
from math import gcd
def find(x, parent):
if parent[x] != x:
parent[x] = find(parent[x], parent)
return parent[x]
def union(x, y, parent, rank):
rootX = find(x, parent)
rootY = find(y, parent)
if rootX != rootY:
if rank[rootX] > rank[rootY]:
parent[rootY] = rootX
elif rank[rootX] < rank[rootY]:
parent[rootX] = rootY
else:
parent[rootY] = rootX
rank[rootX] += 1
def largestComponentSize(nums):
parent = {num: num for num in nums}
rank = {num: 0 for num in nums}
def prime_factors(n):
factors = set()
d = 2
while d * d <= n:
while (n % d) == 0:
factors.add(d)
n //= d
d += 1
if n > 1:
factors.add(n)
return factors
prime_to_index = defaultdict(list)
for num in nums:
primes = prime_factors(num)
for prime in primes:
prime_to_index[prime].append(num)
for primes in prime_to_index.values():
for i in range(1, len(primes)):
union(primes[0], primes[i], parent, rank)
size = defaultdict(int)
for num in nums:
root = find(num, parent)
size[root] += 1
return max(size.values())
Ставь 👍 и забирай 📚 Базу знаний