Задача: 765. Couples Holding Hands
Сложность: 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 {
    minSwapsCouples(row) {
        this.N = row.length / 2;
        this.pairs = Array.from({ length: this.N }, (_, i) => [Math.floor(row[2 * i] / 2), Math.floor(row[2 * i + 1] / 2)]);
        return this.solve(0);
    }

    swap(a, b, c, d) {
        const t = this.pairs[a][b];
        this.pairs[a][b] = this.pairs[c][d];
        this.pairs[c][d] = t;
    }

    solve(i) {
        if (i === this.N) return 0;
        const x = this.pairs[i][0], y = this.pairs[i][1];
        if (x === y) return this.solve(i + 1);

        let jx = 0, kx = 0, jy = 0, ky = 0;
        for (let j = i + 1; j < this.N; ++j) {
            for (let k = 0; k <= 1; ++k) {
                if (this.pairs[j][k] === x) { jx = j; kx = k; }
                if (this.pairs[j][k] === y) { jy = j; ky = k; }
            }
        }

        this.swap(i, 1, jx, kx);
        const ans1 = 1 + this.solve(i + 1);
        this.swap(i, 1, jx, kx);

        this.swap(i, 0, jy, ky);
        const ans2 = 1 + this.solve(i + 1);
        this.swap(i, 0, jy, ky);

        return Math.min(ans1, ans2);
    }
}

Ставь 👍 и забирай 📚 Базу знаний