leetcode之情侣牵手

记录一道一直想不出的题：

N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。

输入: row = [0, 2, 1, 3]

输出: 1

解释: 我们只需要交换row[1]和row[2]的位置即可。

算法解释：固定row[i]，检查row[i+1]是否是其情侣，若不是，找到其情侣，更换位置。

class Solution(object):
    def minSwapsCouples(self, row):
        ans = 0
        for i in xrange(0, len(row), 2):
            x = row[i]
            if row[i+1] == x^1: continue
            ans += 1
            for j in xrange(i+1, len(row)):
                if row[j] == x^1:
                    row[i+1], row[j] = row[j], row[i+1]
                    break
        return ans

转载：
作者：LeetCode
链接：https://leetcode-cn.com/problems/couples-holding-hands/solution/qing-lu-qian-shou-by-leetcode/