資料結構
網路
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 次瀏覽
