LeetCode探索(並查集)
並查集
並查集的核心模板是一個數據結構，包含一個數組root[]，表示每個節點的父親節點，以及兩個方法find()和union用於查詢和合併。
public class DSU{
int[] root;
public DSU(int n){
root = new int[n];
for(int i=0;i<n;i++)
root[i] = i;
}
public int find(int x){
if(root[x] == x) return x;
//路徑壓縮，非必須
return root[x] = find(root[x]);
}
public boolean union(int x,int y){
int rootX = root[x];
int rootY = root[y];
//合併，如果兩個點的父節點已經一致了，
//說明存在環
if(rootX == rootY) return false;
//合併，如果題目要求可能需要按照集合大小或者其他條件合併。
root[rootX] = rootY;
return true;
}
}
以圖判樹
題目：https://leetcode-cn.com/problems/graph-valid-tree/
題目大意：
給定從 0 到 n-1 標號的 n 個結點，和一個無向邊列表（每條邊以結點對來表示），請編寫一個函數用來判斷這些邊是否能夠形成一個合法有效的樹結構。
範例 1： 輸入: n = 5, 邊列表 edges = [[0,1], [0,2], [0,3], [1,4]]
輸出: true範例 2: 輸入: n = 5, 邊列表 edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
輸出: false
分析：
判斷一個圖是否爲樹的要點就在於兩個點，這個圖是否連通和這個圖是否有環。如果一個圖強連通並且沒有環，說明這個圖是一棵樹。
那麼這道題就比較適合用並查集去做，我們在合併集合的過程中判斷是否有環，如果有環則返回false，合併完成之後檢視所有節點是否在同一個集閤中，如果不是則返回false，其他情況返回true。
class Solution {
public class DSU{
int[] root;
int count;
public DSU(int n){
root = new int[n];
for(int i=0;i<n;i++)
root[i] = i;
count = n;
}
public int find(int x){
//沒有壓縮路徑，
//在leetcode中的額外空間會小一些
//執行時間差不多
while(root[x] != x){
x = root[x];
}
return x;
}
public boolean union(int x,int y){
//記得使用find
int rootX = find(x);
int rootY = find(y);
if(rootX == rootY) return false;
root[rootX] = rootY;
//每合併一個節點就減少一個連通分量
count--;
return true;
}
}
public boolean validTree(int n, int[][] edges) {
DSU dsu = new DSU(n);
for(int[] e:edges){
if(!dsu.union(e[0],e[1]))
return false;
}
//判斷連通分量的個數是否爲1
return dsu.count == 1;
}
}
按字典序排列最小的等效字串
題目：https://leetcode-cn.com/problems/lexicographically-smallest-equivalent-string/submissions/
題目大意：
給出長度相同的兩個字串：A 和 B，其中 A[i] 和 B[i] 是一組等價字元。舉個例子，如果 A = 「abc」 且 B = 「cde」，那麼就有 ‘a’ == ‘c’, ‘b’ == ‘d’, ‘c’ == ‘e’。
等價字元遵循任何等價關係的一般規則：
自反性：‘a’ == ‘a’
對稱性：‘a’ == ‘b’ 則必定有 ‘b’ == ‘a’
傳遞性：‘a’ == ‘b’ 且 ‘b’ == ‘c’ 就表明 ‘a’ == ‘c’
例如，A 和 B 的等價資訊和之前的例子一樣，那麼 S = 「eed」, 「acd」 或 「aab」，這三個字串都是等價的，而 「aab」 是 S 的按字典序最小的等價字串
利用 A 和 B 的等價資訊，找出並返回 S 的按字典序排列最小的等價字串。
範例 1：
輸入：A = 「parker」, B = 「morris」, S = 「parser」 輸出：「makkek」
解釋：根據 A 和 B 中的等價資訊，我們可以將這些字元分爲 [m,p], [a,o], [k,r,s], [e,i] 共 4組。每組中的字元都是等價的，並按字典序排列。所以答案是 「makkek」。
範例 2：輸入：A = 「hello」, B = 「world」, S = 「hold」 輸出：「hdld」
解釋：根據 A 和 B 中的等價資訊，我們可以將這些字元分爲 [h,w], [d,e,o], [l,r] 共 3 組。所以只有 S 中的第二個字元 ‘o’ 變成 ‘d’，最後答案爲 「hdld」。
範例 3：輸入：A = 「leetcode」, B = 「programs」, S = 「sourcecode」 輸出：「aauaaaaada」
解釋：我們可以把 A 和 B 中的等價字元分爲 [a,o,e,r,s,c], [l,p], [g,t] 和 [d,m] 共 4 組，因此 S 中除了 ‘u’ 和 ‘d’ 之外的所有字母都轉化成了 ‘a’，最後答案爲 「aauaaaaada」。
分析：
這道題也是一道很典型的並查集，首先根據給出的兩個字串進行合併，最後再進行查詢。
class Solution {
public class DSU{
public int[] root;
public DSU(){
root = new int[26];
for(int i=0;i<26;i++){
root[i] = i;
}
}
public int find(int x){
if(root[x] == x)
return x;
return root[x] = find(root[x]);
}
public void union(int x,int y){
x=find(x);
y=find(y);
if(x==y)
{
return;
}
// 取最小的節點爲root節點
if(x>y)
{
root[x]=y;
}else {
root[y]=x;
}
}
}
public String smallestEquivalentString(String A, String B, String S) {
char[] charA = A.toCharArray();
char[] charB = B.toCharArray();
DSU dsu = new DSU();
for(int i=0;i<charA.length;i++){
//合併
dsu.union(charA[i]-'a',charB[i] - 'a');
}
StringBuilder sb = new StringBuilder();
for(int i=0;i<S.length();i++){
char c = S.charAt(i);
//查詢
sb.append((char)(dsu.find(c-'a')+'a'));
}
return sb.toString();
}
}
島嶼數量Ⅱ
題目：https://leetcode-cn.com/problems/number-of-islands-ii/
題目大意：
假設你設計一個遊戲，用一個 m 行 n 列的 2D 網格來儲存你的遊戲地圖。
起始的時候，每個格子的地形都被預設標記爲「水」。我們可以通過使addLand 進行操作，將位置 (row, col) 的「水」變成「陸地」。
你將會被給定一個列表，來記錄所有需要被操作的位置，然後你需要返回計算出來 每次 addLand 操作後島嶼的數量。
注意：一個島的定義是被「水」包圍的「陸地」，通過水平方向或者垂直方向上相鄰的陸地連線而成。你可以假設地圖網格的四邊均被無邊無際的「水」所包圍。
範例:
輸入: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]] 輸出:
[1,1,2,3]
解析:
起初，二維網格 grid 被全部注入「水」。（0 代表「水」，1 代表「陸地」）0 0 0
0 0 0
0 0 0
操作 #1：addLand(0, 0) 將 grid[0][0] 的水變爲陸地。1 0 0
0 0 0 島嶼的數量爲 1
0 0 0
操作 #2：addLand(0, 1) 將grid[0][1] 的水變爲陸地。1 1 0
0 0 0 島嶼的數量爲 1
0 0 0
操作 #3：addLand(1, 2) 將 grid[1][2] 的水變爲陸地。1 1 0
0 0 1 島嶼的數量爲 2
0 0 0
操作 #4：addLand(2, 1) 將 grid[2][1] 的水變爲陸地。1 1 0
0 0 1 島嶼的數量爲 3
0 1 0
分析：
這道題也可以使用並查集來做，首先把每個網格看做是一個單獨的節點，當一個網格從0變成1之後，首先增加一個連通分量，判斷是否可以合併到上下左右四個網格的集閤中，如果可以的話就往並查集中加入這條邊，並且減少對應的連通分量。
最後判斷一下有幾個連通分量。
class Solution {
public class DUS{
int[] root;
int count;
public DUS(int m,int n){
int length = m*n;
root = new int[length];
count = 0;
for(int i=0;i<length;i++)
root[i] = i;
}
public int find(int x){
if(root[x] == x)
return x;
return root[x] = find(root[x]);
}
public boolean union(int x,int y){
int rootX = find(x);
int rootY = find(y);
if(rootX == rootY)
return false;
root[rootY] = rootX;
return true;
}
}
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> res = new ArrayList<>();
if(m == 0 || n == 0 || positions.length == 0)
return res;
int[][] grid = new int[m][n];
DUS dus = new DUS(m,n);
for(int[] add:positions){
int x = add[0],y = add[1];
if(grid[x][y] == 1){
res.add(dus.count);
continue;
}
//先假設這個節點爲單獨的節點，增加連通分量
grid[x][y] = 1;
dus.count++;
if(x>0 && grid[x-1][y] == 1){
//加入對應的邊，並且減少連通分量
if(dus.union(x*n+y,(x-1)*n+y))
dus.count--;
}
if(y>0 && grid[x][y-1] == 1){
if(dus.union(x*n+y,(x)*n+y-1))
dus.count--;
}
if(x < m-1 && grid[x+1][y] == 1){
if(dus.union(x*n+y,(x+1)*n+y))
dus.count--;
}
if(y < n-1 && grid[x][y+1] == 1){
if(dus.union(x*n+y,x*n+y+1))
dus.count--;
}
res.add(dus.count);
}
return res;
}
}
