题目描述：

LeetCode 765. Couples Holding Hands

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples' initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.

Example 1:

Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

Example 2:

Input: row = [3, 2, 0, 1]
Output: 0
Explanation: All couples are already seated side by side.

Note:

1. len(row) is even and in the range of [4, 60].
2. row is guaranteed to be a permutation of 0...len(row)-1.

题目大意：

N对情侣手牵手坐在2N个座位上。

第一对情侣的编号为0, 1。第N对情侣的编号为N * 2 - 2, N * 2 - 1

给定情侣的初始座次row，求最少交换多少次才能让每对情侣手牵手。

解题思路：

消去已配对情侣 + 编号标准化

消去已配对情侣：

假设第I对情侣编号为sm, bg（sm < bg）

若sm + 1 == bg 并且sm为偶数，则该对情侣已配对成功，可以消去

编号标准化：

假设初始3对情侣配对为 [[1, 2], [3, 4], [5, 0]]

将0, 2互换后得到 [[1, 0], [3, 4], [5, 2]]

消去[1, 0]得到 [[3, 4], [5, 2]]

[[3, 4], [5, 2]] 可以标准化为 [[0, 3], [1, 2]]

则问题规模减小为2对情侣

重复上述过程即可完成所有情侣的配对。

Python代码：

class Solution(object):
    def normalize(self, row):
        crow = []
        for x in range(len(row)):
            sm, bg = row[x][0], row[x][1]
            if sm > bg: sm, bg = bg, sm
            if bg % 2 and sm + 1 == bg: continue
            crow.append((sm, bg))
        shift = {v : i for i, v in enumerate(sorted(reduce(operator.add, crow, ())))}
        crow = sorted([shift[sm], shift[bg]] for sm, bg in crow)
        return crow

    def solve(self, row):
        row = self.normalize(row)
        if not row: return 0
        locs = {}
        for idx, (sm, bg) in enumerate(row):
            locs[sm], locs[bg] = idx * 2, idx * 2 + 1
        row[locs[1] / 2][locs[1] % 2] = row[0][1]
        return self.solve(row[1:]) + 1

    def minSwapsCouples(self, row):
        """
        :type row: List[int]
        :rtype: int
        """
        return self.solve([[row[x], row[x + 1]] for x in range(0, len(row), 2)])

 

本文链接：http://bookshadow.com/weblog/2018/01/14/leetcode-couples-holding-hands/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码