Сложность: 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.
😎 Решение:
public class Solution {
public int minDominoRotations(int[] tops, int[] bottoms) {
int check(int x) {
int rotationsA = 0, rotationsB = 0;
for (int i = 0; i < tops.length; i++) {
if (tops[i] != x && bottoms[i] != x) {
return -1;
} else if (tops[i] != x) {
rotationsA++;
} else if (bottoms[i] != x) {
rotationsB++;
}
}
return Math.min(rotationsA, rotationsB);
}
int rotations = check(tops[0]);
if (rotations != -1 || tops[0] == bottoms[0]) {
return rotations;
} else {
return check(bottoms[0]);
}
}
}Ставь 👍 и забирай 📚 Базу знаний