题目
给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。
你可以 任意多次交换 在 pairs 中任意一对索引处的字符。
返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。
示例 1:
输入：s = "dcab", pairs = [[0,3],[1,2]]
输出："bacd"
解释：
交换 s[0] 和 s[3], s = "bcad"
交换 s[1] 和 s[2], s = "bacd"
示例 2：
输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]
输出："abcd"
解释：
交换 s[0] 和 s[3], s = "bcad"
交换 s[0] 和 s[2], s = "acbd"
交换 s[1] 和 s[2], s = "abcd"
示例 3：
输入：s = "cba", pairs = [[0,1],[1,2]]
输出："abc"
解释：
交换 s[0] 和 s[1], s = "bca"
交换 s[1] 和 s[2], s = "bac"
交换 s[0] 和 s[1], s = "abc"
并查集
说实话，我用笨办法也许可以试试解这道题，但是在学习过程中最大的收获应该是并查集这一块，解这道题之前最好先整明白什么是并查集
学习打卡 JavaScript 并查集 数据结构与算法并查集 Javascript 数据结构之并查集 算法学习笔记 (1) : 并查集
另外几道题的题解，用到了并查集，这几道题我没做出来。 399. 除法求值 官方的并查集
题解
class UnionFind {
constructor(n) {
this.parents = new Uint32Array(n);
this.ranks = new Uint32Array(n);
while (n--) this.parents[n] = n;
}
union(x, y) {
const rootX = this.find(x),
rootY = this.find(y);
if (rootX !== rootY) {
const t = this.ranks[rootX] - this.ranks[rootY];
if (t <= 0) {
this.parents[rootX] = rootY;
if (t === 0) this.ranks[rootY]++;
} else this.parents[rootY] = rootX;
}
}
find(x) {
while (x !== this.parents[x]) x = this.parents[x];
return x;
}
}
var smallestStringWithSwaps = function (s, pairs) {
debugger;
let unionFind = new UnionFind(s.length),
i = pairs.length,
h = new Map(),
r = '';
while (i--) unionFind.union(pairs[i][0], pairs[i][1]);
while (++i < s.length) {
const rootI = unionFind.find(i);
if (!h.has(rootI)) h.set(rootI, new MinPriorityQueue());
h.get(rootI).enqueue(s[i], s.charCodeAt(i));
}
for (i = 0; i < s.length; i++) {
const rootI = unionFind.find(i);
r += h.get(rootI).dequeue().element;
}
return r;
};
let s = 'dcab',
pairs = [
[0, 3],
[1, 2],
[0, 2],
];
console.log(smallestStringWithSwaps(s, pairs));
没有认真审题，用的笨办法还解错了
/**
* @param {string} s
* @param {number[][]} pairs
* @return {string}
*/
var smallestStringWithSwaps = function (s, pairs) {
let getS = s;
for (let index = 0; index < pairs.length; index++) {
const element = pairs[index];
let s0Index = element[0];
let s1Index = element[1];
let getS0 = getS[s0Index];
let getS1 = getS[s1Index];
let a = s0Index == 0 ? '' : getS.slice(0, s0Index);
let b = getS1;
let c = getS.slice(s0Index + 1, s1Index);
let d = getS0;
let e = s1Index == getS.length - 1 ? '' : getS.slice(s1Index + 1);
console.log('abcde', a, '|', b, '|', c, '|', d, '|', e);
getS = a + b + c + d + e;
console.log('getS', getS);
}
return getS;
};
let s = 'dcab',
pairs = [
[0, 3],
[1, 2],
[0, 2],
];