数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
广告