OSSDP-Lab2-acceptPR/Solution7.java at main · MortusCc/OSSDP-Lab2-acceptPR · GitHub

History

129 lines (117 loc) · 3.76 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

import java.util.HashMap;

import java.util.List;

import java.util.Map;

import java.util.PriorityQueue;

/**

* @description:

* 给你一个字符串 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"

* 提示：

* 1 <= s.length <= 10^5

* 0 <= pairs.length <= 10^5

* 0 <= pairs[i][0], pairs[i][1] < s.length

* s 中只含有小写英文字母

public class Solution7 {

public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {

if (pairs.size() <= 1) {

return s;

}

// 第 1 步：将任意交换的结点对输入并查集

int len = s.length();

UnionFind unionFind = new UnionFind(len-1);

for (List<Integer> pair : pairs) {

int index1 = pair.get(0);

int index2 = pair.get(1);

unionFind.union(index1, index2);

}

// 第 2 步：构建映射关系

char[] charArray = s.toCharArray();

// key：连通分量的代表元，value：同一个连通分量的字符集合（保存在一个优先队列中）

Map<Integer, PriorityQueue<Character>> hashMap = new HashMap<>(len);

for (int i = 0; i < len; i++)

int root = unionFind.find(i);

hashMap.computeIfAbsent(root, key -> new PriorityQueue<>()).offer(charArray[i]);

// 第 3 步：重组字符串

StringBuilder stringBuilder = new StringBuilder();

for (int i = 0; i < len; i++) {

int root = unionFind.find(i);

stringBuilder.append(hashMap.get(root).poll());

stringBuilder.append(" ");

}

return stringBuilder.toString();

}

private class UnionFind {

private int[] parent;

/**

* 以 i 为根结点的子树的高度（引入了路径压缩以后该定义并不准确）

private int[] rank;

public UnionFind(int n) {

this.parent = new int[n];

this.rank = new int[n];

for (int i = 0; i < n; i++) {

this.parent[i] = i;

this.rank[i] = 1;

}

public void union(int x, int y) {

int rootX = find(x);

int rootY = find(y);

if (rootX == rootY) {

return;

}

if (rank[rootX] == rank[rootY]) {

parent[rootX] = rootY;

// 此时以 rootY 为根结点的树的高度仅加了 1

rank[rootY]++;

} else if (rank[rootX] < rank[rootY]) {

parent[rootX] = rootY;

// 此时以 rootY 为根结点的树的高度不变

} else {

// 同理，此时以 rootX 为根结点的树的高度不变

parent[rootY] = rootX;

}

public int find(int x) {

if (x != parent[x]) {

parent[x] = find(parent[x]);

}

return parent[x];

}

OSSDP-Lab2-acceptPR/Solution7.java at main · MortusCc/OSSDP-Lab2-acceptPR · GitHub

Expand file tree

Breadcrumbs

Solution7.java

Latest commit

History

Breadcrumbs

Solution7.java

File metadata and controls