数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中情侣牵手问题
假设有 N 对情侣，他们坐在一排 2N 个座位上，想要互相牵手。我们需要找到使每对情侣都坐在相邻位置所需的最小交换次数。
人和座位由 0 到 2N-1 的数字表示，情侣按顺序编号，例如第一对情侣为 (0, 1)，第二对情侣为 (2, 3)，以此类推，最后一对情侣为 (2N-2, 2N-1)。
情侣的初始座位由另一个名为 row 的数组给出，row[i] 表示最初坐在第 i 个座位上的人的编号。
例如，如果输入为 [0,2,4,1,3,5]，则输出为 2。
为了解决这个问题，我们将遵循以下步骤：
定义一个名为 UF 的数据块，在这个数据块中定义一些属性和函数，如下所示：
定义一个数组 parent。
通过传入一个值 N 初始化 UF 数据块，然后执行以下操作：
count := N
parent := 一个大小为 N 的数组
初始化 i := 0，当 i < N 时，更新（i 加 1），执行以下操作：
parent[i] := i
parent[i] := i
parA := getParent(a)
parB := getParent(b)
如果 parA 等于 parB，则：
返回
（count 减 1）
parent[parB] := parA
定义一个函数 getParent()，它将接收 i，
如果 parent[i] 等于 i，则：
返回 i
返回 parent[i] = getParent(parent[i])
从主方法执行以下操作：
n := row 的大小，N := n / 2
创建一个名为 uf 的 UF 数据块并用 N 初始化
初始化 gr := 0，当 gr < N 时，更新（gr 加 1），执行以下操作：
a := row[gr * 2]
b := row[gr * 2 + 1]
调用 uf 的 unionn(a / 2, b / 2)
返回 N - uf 的 count
让我们看看以下实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
class UF{
public:
vector<int> parent;
int count;
UF(int N){
count = N;
parent = vector<int>(N);
for (int i = 0; i < N; i++) {
parent[i] = i;
}
}
void unionn(int a, int b){
int parA = getParent(a);
int parB = getParent(b);
if (parA == parB)
return;
count--;
parent[parB] = parA;
}
int getParent(int i){
if (parent[i] == i)
return i;
return parent[i] = getParent(parent[i]);
}
};
int minSwapsCouples(vector<int>& row) {
int n = row.size();
int N = n / 2;
UF uf(N);
for (int gr = 0; gr < N; gr++) {
int a = row[gr * 2];
int b = row[gr * 2 + 1];
uf.unionn(a / 2, b / 2);
}
return N - uf.count;
}
};
main(){
Solution ob;
vector<int> v = {0,2,4,1,3,5};
cout << (ob.minSwapsCouples(v));
}输入
{0,2,4,1,3,5}输出
2
295 次浏览
