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. 情侣牵手【配对问题 + 贪心策略】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。