Сложность: medium
В ряду домино, tops[i] и bottoms[i] представляют собой верхнюю и нижнюю половинки i-го домино. (Домино - это плитка с двумя числами от 1 до 6 - по одному на каждой половине плитки.) Мы можем повернуть i-е домино так, чтобы tops[i] и bottoms[i] поменялись значениями. Верните минимальное количество поворотов, чтобы все значения tops были одинаковыми или все значения bottoms были одинаковыми. Если это невозможно сделать, верните -1.
Пример:
Input: tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]
Output: 2
👨💻 Алгоритм:
1⃣Проверка кандидатов:
Для начала рассмотрим два кандидата для достижения цели: tops[0] и bottoms[0]. Это кандидаты для унификации значений в ряду домино, поскольку если есть решение, один из этих двух кандидатов должен быть в верхней или нижней строке всех домино.
2⃣Подсчет поворотов для каждого кандидата:
Для каждого из кандидатов (tops[0] и bottoms[0]) подсчитайте количество поворотов, необходимых для унификации значений во всех tops или во всех bottoms.
Если какой-либо домино не может быть повернут для достижения требуемого кандидата, этот кандидат исключается из рассмотрения.
3⃣Возврат минимального количества поворотов:
Верните минимальное количество поворотов из всех возможных кандидатов. Если ни один кандидат не подходит, верните -1.
😎 Решение:
class Solution:
def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
def check(x):
rotations_a = rotations_b = 0
for i in range(len(tops)):
if tops[i] != x and bottoms[i] != x:
return -1
elif tops[i] != x:
rotations_a += 1
elif bottoms[i] != x:
rotations_b += 1
return min(rotations_a, rotations_b)
rotations = check(tops[0])
if rotations != -1 or tops[0] == bottoms[0]:
return rotations
else:
return check(bottoms[0])
Ставь 👍 и забирай 📚 Базу знаний