Сложность: 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 {
var N: Int = 0
var pairs: [[Int]] = []
func minSwapsCouples(_ row: [Int]) -> Int {
N = row.count / 2
pairs = Array(repeating: Array(repeating: 0, count: 2), count: N)
for i in 0..<N {
pairs[i][0] = row[2 * i] / 2
pairs[i][1] = row[2 * i + 1] / 2
}
return solve(0)
}
func swap(_ a: Int, _ b: Int, _ c: Int, _ d: Int) {
let t = pairs[a][b]
pairs[a][b] = pairs[c][d]
pairs[c][d] = t
}
func solve(_ i: Int) -> Int {
if i == N { return 0 }
let x = pairs[i][0], y = pairs[i][1]
if x == y { return solve(i + 1) }
var jx = 0, kx = 0, jy = 0, ky = 0
for j in (i + 1)..<N {
for k in 0...1 {
if pairs[j][k] == x { jx = j; kx = k }
if pairs[j][k] == y { jy = j; ky = k }
}
}
swap(i, 1, jx, kx)
let ans1 = 1 + solve(i + 1)
swap(i, 1, jx, kx)
swap(i, 0, jy, ky)
let ans2 = 1 + solve(i + 1)
swap(i, 0, jy, ky)
return min(ans1, ans2)
}
}Ставь 👍 и забирай 📚 Базу знаний