Skip to main content

765. 情侣牵手

765. 情侣牵手​

https://leetcode-cn.com/problems/couples-holding-hands/

N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。

人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。

这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。

示例 1:

输入: row = [0, 2, 1, 3]
输出: 1
解释: 我们只需要交换row[1]和row[2]的位置即可。

示例 2:

输入: row = [3, 2, 0, 1]
输出: 0
解释: 无需交换座位，所有的情侣都已经可以手牵手了。

说明:

  • len(row) 是偶数且数值在 [4, 60]范围内。
  • 可以保证row 是序列 0...len(row)-1 的一个全排列。

通过次数6,775 | 提交次数11,684

Fourth Try​

2020-07-01

通过union find找环的写法,也是在题解里看到的写法。刚开始看algs4的时候，学的第一个算法就是union-find，没想到在这里派上用途了。

思路转变一下，其实每个环就是自己的一个组合，最后只要找有多少个组合就行了，没想到真的跟union-find匹配上了。最后找多少个集合的时候，只要找有多少个根节点就行了。这个思路还是非常自然的。

这道765，在我精神疲惫的时候真是浪费了我许多时间。首先是题解的思路转换问题，其次是找环问题。分明union-find和BFS/DFS都是我很熟悉的内容，就是写不出来。

其实能够用union-find，本质上是所有集合必然是一个环，如果是其他题目的其他情况，就不能用直接用该算法了。还有这是无向图的找环问题，那么有向图的找环问题呢？都可以拓展开去，遇到题目的时候再来思考这些问题吧，没有题目不想思考。

class Solution(object):
    def minSwapsCouples(self, row):
        """
        :type row: List[int]
        :rtype: int
        """
        # 搞个union find的找环写法，看最终有多少个root node就可以了
        N = len(row)

        # 每个人所在的沙发标记
        pton = dict()
        for idx, p in enumerate(row):
            pton[p] = idx // 2
        
        # union find中经典的两个数组，一个表示上一层节点，一个表示所在树的高度
        graph = [i for i in range(N//2)]
        rank = [1 for i in range(N//2)]

        def find_root(n):
            while graph[n] != n:
                n = graph[n]
            return n
        
        def union(ni, nii):
            if ni == nii:
                return
            root_ni = find_root(ni)
            root_nii = find_root(nii)
            if root_ni == root_nii:
                return 
            # 其实比较高度这里无关紧要
            if rank[root_ni] < rank[root_nii]:
                graph[root_ni] = root_nii
            elif rank[root_ni] > rank[root_nii]:
                graph[root_nii] = root_ni
            else:
                graph[root_ni] = root_nii
                rank[root_nii] += 1
        for i in range(0, N, 2):
            # 每个点如果不形成自环，都需要跟其余两个点打交道，总共三个点
            ni = i // 2
            nii = pton[row[i] ^ 1]
            niii = pton[row[i+1] ^ 1]
            union(ni, nii)
            union(ni, niii)
        count = 0
        for i in range(0, N//2):
            if graph[i] == i:  # 根节点数量
                count += 1
        return N//2 - count

Third Try​

2020-07-01

通过first try中的证明可以知道，其实只需要数这个时候图里有几个环进行，根本不需要具体的去交换。

因此问题变成了找环的写法，看起来很简单，但把我折腾得够惨。因为沙发idx和人员idx编号之间非常容易混淆，构建关联图的时候很容易就混乱了。其次是对于如何找出所有环，没有经验。以前写的算法都是只要找到一个环就可以退出了，没想过还要找到所有环的写法。

这里面有个重点，所有节点必定在某个环中，因此如果找到某个没有被遍历过的节点，沿着关联边一顿遍历，肯定能把该环上的所有元素一窝端了。所以其实搞个visited集合，每个已经访问过的点肯定在以前的环中，直接跳过就可以了。

不过我的写法还是变成了队列写法，每次向两边直接无脑扩散就行了。按题解里的列表裸写，沿着一个点一路往前怼的，真是写不出来。对于边界条件和起始条件的琐碎设置，不熟悉那种写法真是很头疼。

class Solution(object):
    def minSwapsCouples(self, row):
        """
        :type row: List[int]
        :rtype: int
        """
        # 搞个统计联通环的版本，重点是统计有几个环
        # 由于每个沙发只能有两个分支，每个环之间不可能有交集，发现一个就只有一个，只有在闭环的时候才能被发现
        # 要关注沙发编号构建完图，就可以忽略人员编号了
        # 每个元素在这个图中，至少在一个环内

        graph = collections.defaultdict(list)
        
        # pidx --> cidx
        ptoc = dict()
        for idx, p in enumerate(row):
            ptoc[p] = idx // 2  # two seats as one coach
        # print(ptoc)
        for idx in range(0, len(row), 1):
            graph[idx // 2].append(ptoc[row[idx] ^ 1])  # 每个节点有两个方向
        # print(graph)
        cycles = 0
        visited = set()
        # 每个元素都在该图中，走一遍标记一次
        for node in graph.keys():
            if node in visited:
                continue
            visited.add(node)
            cycles += 1
            # 抓住一个往前怼就行了
            queue = graph[node]
            while len(queue):
                n = queue.pop(0)
                if n in visited:
                    continue
                visited.add(n)
                queue.extend(graph[n])
        # print(cycles)
        return len(graph.keys()) - cycles
  • 执行用时：28 ms, 在所有 Python 提交中击败了40.59%的用户
  • 内存消耗：12.8 MB, 在所有 Python 提交中击败了25.00%的用户

Second Try​

2020-07-01

在换人的时候，提前设置并动态更新伴侣所在的位置，速度可以加快

class Solution(object):
    def minSwapsCouples(self, row):
        """
        :type row: List[int]
        :rtype: int
        """
        # 加速版
        pos = {i: idx for idx, i in enumerate(row)} 
        count = 0
        N = len(row)
        for idx in range(0, N, 2):
            left = row[idx]
            right = row[idx + 1]
            # x ^ 1的写法太神奇了,遇到奇数减1，遇到偶数加1，画下二进制就明白了，影响的是最后一位
            if right == left ^ 1:
                continue
            nexid = pos[left ^ 1]
            row[idx + 1] = row[nexid]
            row[nexid] = right
            # deal pos 
            pos[left ^ 1] = idx + 1
            pos[row[nexid]] = nexid
            count +=
  • 执行用时：16 ms, 在所有 Python 提交中击败了91.09%的用户
  • 内存消耗：12.7 MB, 在所有 Python 提交中击败了25.00%的用户

First Try​

2020-07-01

  • 关于构建图的问题，重点在与这个座位不是环形座位，因此只能按照[0, 1], [2, 3]的下标座位来进行匹配。
  • 从这个意义来讲，每个元素想要配对，旁边只有1个可考虑的邻座，并不是有2个邻座。
  • 重要的是构建图之后，对于联通分量的论证。
  • 每次执行换位之后，整个图能最多只能增加1个联通分量。
  • 直觉就会有疑惑，如果换过去之后，两个沙发都能匹配上，岂不是一下子增加两对？
  • 问题在与如果存在这样的两个沙发，那么本来他们也能构成一个较大的联通分量，换位之后也只是变成了2个小联通分量。
  • 因此要么是换了之后增加自身的循环分量，要么是一个大分量变成两个小分量，以此类推，可以得到需要换位的数量
  • 换位数量是 N - 已经存在的联通分量
  • 从这个思路出发，每次遇到不合适的直接换位，其实就已经是最优解了，太神奇了。

class Solution(object):
    def minSwapsCouples(self, row):
        """
        :type row: List[int]
        :rtype: int
        """
        # 关于构建图的问题，重点在与这个座位不是环形座位，因此只能按照[0, 1], [2, 3]的下标座位来进行匹配。
        # 从这个意义来讲，每个元素想要配对，旁边只有1个可考虑的邻座，并不是有2个邻座。
        # 重要的是构建图之后，对于联通分量的论证。 
        # 每次执行换位之后，整个图能最多只能增加1个联通分量。
        # 直觉就会有疑惑，如果换过去之后，两个沙发都能匹配上，岂不是一下子增加两对？
        # 问题在与如果存在这样的两个沙发，那么本来他们也能构成一个较大的联通分量，换位之后也只是变成了2个小联通分量。
        # 因此要么是换了之后增加自身的循环分量，要么是一个大分量变成两个小分量，以此类推，可以得到需要换位的数量
        # 换位数量是 N - 已经存在的联通分量
        # 从这个思路出发，每次遇到不合适的直接换位，其实就已经是最优解了，太神奇了。
        count = 0
        N = len(row)
        for idx in range(0, N, 2):
            left = row[idx]
            right = row[idx+1]
            # x ^ 1的写法太神奇了,遇到奇数减1，遇到偶数加1，画下二进制就明白了，影响的是最后一位
            if right == left ^ 1:
                continue
            for nidx in range(idx+2, N, 1):
                if row[nidx] == left ^ 1:
                    row[idx] = row[nidx]
                    row[nidx] = right
                    count += 1
                    # 只跳了第一个for
                    break
        return count

  • 执行用时：24 ms, 在所有 Python 提交中击败了60.40%的用户
  • 内存消耗：12.8 MB, 在所有 Python 提交中击败了25.00%的用户