資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中帶交換的最小子字串
假設我們給定一個字串 s，以及一個字串中索引對的陣列 pairs，其中 pairs[i] = [a, b] 表示字串的兩個索引（從 0 開始）。我們可以根據給定的 pairs 中的任意一對索引交換字元任意次數。我們必須找到可以使用交換後 s 可以更改成的字典序最小的字串。因此，如果輸入類似於 s = “dcab” 和 pairs = [[0,3], [1,2]]，則輸出將為 “bacd”。交換 s[0] 和 s[3]，s = "bcad"，然後交換 s[1] 和 s[2]，s = "bacd"。
為了解決這個問題，我們將遵循以下步驟：
n := 陣列的大小，parent := 建立一個大小為 n 的陣列，並用 -1 填充它
建立一個名為 ret 的大小為 n 的字串，並用 * 填充它
對於 i 從 0 到 pairs 的大小
u := pairs[i, 0] 和 v := pairs[i, 1]
如果 u 的父節點與 v 的父節點相同，則跳到下一個迭代
parent[u 的父節點] := v 的父節點
定義一個大小為 n 的陣列 arr1
對於 i 從 0 到 n – 1：將 s[i] 插入到 arr[i 的父節點] 中
對於 i 從 0 到 n – 1：透過從右讀取值對 arr[i] 進行排序
對於 i 從 0 到 n – 1 –
ret[i] := arr1[i 的父節點] 的最後一個條目
從 arr1[i 的父節點] 中刪除最後一個節點
示例（C++）
讓我們看看以下實現以更好地理解：
class Solution {
public:
vector <int> parent;
int getParent(int x){
if(parent[x] == -1) return x;
return parent[x] = getParent(parent[x]);
}
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int n = s.size();
parent = vector <int>(n, -1);
string ret(n, '*');
for(int i = 0; i < pairs.size(); i++){
int u = pairs[i][0];
int v = pairs[i][1];
if(getParent(u) == getParent(v)) continue;
parent[getParent(u)] = getParent(v);
}
vector < char > arr1[n];
for(int i = 0; i < n; i++){
arr1[getParent(i)].push_back(s[i]);
}
for(int i = 0; i < n; i++){
sort(arr1[i].rbegin(), arr1[i].rend());
}
for(int i = 0; i < n; i++){
ret[i] = arr1[getParent(i)].back();
arr1[getParent(i)].pop_back();
}
return ret;
}
};輸入
"dcab" [[0,3],[1,2]]
輸出
"bacd"
更新於: 2020-03-31
334 次檢視
廣告