Сложность: hard
Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки.
Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1).
Верните минимальное количество перестановок, чтобы каждая пара сидела рядом. Перестановка состоит из выбора любых двух человек, которые встают и меняются местами.
Пример:
Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.
👨💻 Алгоритм:
1⃣Мы могли бы предположить без доказательства, что решение, при котором мы делаем людей на каждом диване счастливыми по порядку, является оптимальным. Это предположение сильнее, чем гипотеза о жадном подходе, но кажется разумным, поскольку при каждом ходе мы делаем хотя бы одну пару счастливой.
2⃣При таком предположении, для какого-то дивана с несчастливыми людьми X и Y, мы либо заменяем Y на партнера X, либо заменяем X на партнера Y. Для каждой из двух возможностей мы можем попробовать оба варианта, используя подход с возвратом.
3⃣Для каждого дивана с двумя возможностями (т.е. оба человека на диване несчастливы) мы попробуем первый вариант, найдем ответ как ans1, затем отменим наш ход и попробуем второй вариант, найдем связанный ответ как ans2, отменим наш ход и затем вернем наименьший ответ.
😎 Решение:
class Solution:
def minSwapsCouples(self, row: List[int]) -> int:
self.N = len(row) // 2
self.pairs = [[0, 0] for _ in range(self.N)]
for i in range(self.N):
self.pairs[i][0] = row[2 * i] // 2
self.pairs[i][1] = row[2 * i + 1] // 2
return self.solve(0)
def swap(self, a: int, b: int, c: int, d: int):
self.pairs[a][b], self.pairs[c][d] = self.pairs[c][d], self.pairs[a][b]
def solve(self, i: int) -> int:
if i == self.N:
return 0
x, y = self.pairs[i]
if x == y:
return self.solve(i + 1)
jx, kx, jy, ky = 0, 0, 0, 0
for j in range(i + 1, self.N):
for k in range(2):
if self.pairs[j][k] == x:
jx, kx = j, k
if self.pairs[j][k] == y:
jy, ky = j, k
self.swap(i, 1, jx, kx)
ans1 = 1 + self.solve(i + 1)
self.swap(i, 1, jx, kx)
self.swap(i, 0, jy, ky)
ans2 = 1 + self.solve(i + 1)
self.swap(i, 0, jy, ky)
return min(ans1, ans2)
Ставь 👍 и забирай 📚 Базу знаний