LeetCode[765]情侣牵手

难度困难

题目

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

---

示例 1:

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

输出: 1

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

---

示例 2:

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

输出: 0

解释: 无需交换座位所有的情侣都已经可以手牵手了。

---

提示:

• 2n == row.length

• 2 <= n <= 30

• n 是偶数

• 0 <= row[i] < 2n

• row 中所有元素均无重复

---

Related Topics

• 贪心

• 深度优先搜索

• 广度优先搜索

• 并查集

• 图

---

重点解题思路

第一步

明确解题手段
类似于此种连通性问题均能使用并查集来实现

第二步

可以看题和例子找出规律每个人都是0 1 2 3...n的
每个情侣之前除以2都可以得到这个情侣的下标
比如0 1都除以2第0个情侣下标
比如2 3都除以2第一个情侣下标
找出规律后
我们使用并查集将每次遍历的两个数除以2
如果相同就不连接如果不相同就连接

第三步:

总数-连通分量=操作次数
如果一次都没有操作成功那么连通分量=总数即返回0

源码

class UnionFind {
    //记录每个节点的根节点
    int[] parent;
    //记录每个子集的节点数
    int[] rank;
    //记录并查集中的联通分量数量
    int count;

    public UnionFind(int n){
        count=n;
        parent=new int[n];
        for (int i=0;i<n;i++){
            parent[i]=i;
        }
        rank=new int[n];
        Arrays.fill(rank,1);
    }

    //路径压缩
    public int find(int ind){
        if (parent[ind]!=ind){
            parent[ind]=find(parent[ind]);
        }
        return parent[ind];
    }

    //按秩合并
    public void unite(int ind1,int ind2){
        int root1=find(ind1),root2=find(ind2);
        if (root1!=root2){
            if (rank[root1]<rank[root2]){
                int temp=root2;
                root2=root1;
                root1=temp;
            }
            parent[root2]=root1;
            rank[root1]+=rank[root2];
            count--;
        }
    }

    public int getCount(){
        return count;
    }
    public boolean connected(int ind1,int ind2){
        return find(ind1)==find(ind2);
    }
}
class Solution {
    public int minSwapsCouples(int[] row) {
        int len=row.length;
        int N=len/2;
        UnionFind uf = new UnionFind(N);
        for (int i=0;i<len;i+=2){
            uf.unite(row[i]>>1,row[i+1]>>1);//连接的时候如果是同一个节点或在同一个集合内就不连接
        }
        return N-uf.getCount();
    }
}

运行结果

如果您还有什么疑问或解答有问题可在下方评论我会及时回复。

系列持续更新中点个订阅吧