leetcode:765. 情侣牵手【配对问题 + 贪心策略】

分析

想不到办法就贪心
固定左边的，然后找到右边的位置，移动一次即可
需要记录每个人对应的位置，然后更新交换后的位置和row即可

ac code

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        # 考虑even的idx，然后让odd的匹配（贪心策略）
        # 不动even 只动odd
        indices = {x : i for i, x in enumerate(row)}
        ans = 0
        n = len(row)
        for i in range(n // 2):
            x = row[2 * i]
            # find partner
            if x % 2 == 0:
                y = x + 1
            else:
                y = x - 1
            if indices[y] != 2 * i + 1:
                ans += 1
                changer = row[2 * i + 1]
                changer_idx = indices[y]
                # change
                row[2 * i + 1], row[changer_idx] = y, changer 
                indices[y] = 2 * i + 1
                indices[changer] = changer_idx
                
            #print(indices)
        return ans

总结

贪心：由于是顺序的两两配对
多个配对问题可以考虑固定一个然后挪动另外一个

最后

以上就是阳光人生最近收集整理的关于leetcode:765. 情侣牵手【配对问题 + 贪心策略】的全部内容，更多相关leetcode:765.内容请搜索靠谱客的其他文章。