關(guān)于我的 Leetcode 題目解答，代碼前往 Github：https://github.com/chenxiangcyr/leetcode-answers
Disjoint Set Union (DSU) 并查集
并查集是一種非常精巧而實(shí)用的數(shù)據(jù)結(jié)構(gòu)站辉，它主要用于處理一些不相交集合的合并問(wèn)題呢撞。
一些常見(jiàn)的用途有：
- 求連通子圖
- 求最小生成樹(shù)的 Kruskal 算法
- 求最近公共祖先（Least Common Ancestors, LCA）等损姜。
使用并查集時(shí)饰剥，首先會(huì)存在一組不相交的動(dòng)態(tài)集合 S={S1,S2,?,Sk}
每個(gè)集合可能包含一個(gè)或多個(gè)元素，并選出集合中的某個(gè)元素作為代表摧阅。每個(gè)集合中具體包含了哪些元素是不關(guān)心的汰蓉，具體選擇哪個(gè)元素作為代表一般也是不關(guān)心的。
我們關(guān)心的是棒卷，對(duì)于給定的元素顾孽，可以很快的找到這個(gè)元素所在的集合（的代表），以及合并兩個(gè)元素所在的集合比规，而且這些操作的時(shí)間復(fù)雜度都是常數(shù)級(jí)的若厚。
并查集的基本操作有三個(gè)：
- makeSet(s)：建立一個(gè)新的并查集，其中包含 s 個(gè)單元素集合蜒什。
- unionSet(x, y)：把元素 x 和元素 y 所在的集合合并测秸，要求 x 和 y 所在的集合不相交，如果相交則不合并。
- find(x)：找到元素 x 所在的集合的代表霎冯，該操作也可以用于判斷兩個(gè)元素是否位于同一個(gè)集合铃拇，只要將它們各自的代表比較一下就可以了。
并查集的實(shí)現(xiàn)原理也比較簡(jiǎn)單沈撞，就是使用樹(shù)來(lái)表示集合慷荔，樹(shù)的每個(gè)節(jié)點(diǎn)就表示集合中的一個(gè)元素，樹(shù)根對(duì)應(yīng)的元素就是該集合的代表缠俺，如圖所示：
圖中有兩棵樹(shù)显晶，分別對(duì)應(yīng)兩個(gè)集合，其中第一個(gè)集合為 {a,b,c,d}
樹(shù)的節(jié)點(diǎn)表示集合中的元素晋修，指針表示指向父節(jié)點(diǎn)的指針吧碾，根節(jié)點(diǎn)的指針指向自己，表示其沒(méi)有父節(jié)點(diǎn)墓卦。沿著每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)不斷向上查找倦春，最終就可以找到該樹(shù)的根節(jié)點(diǎn)，即該集合的代表元素落剪。
現(xiàn)在睁本，應(yīng)該可以很容易的寫(xiě)出 makeSet 和 find 的代碼了，假設(shè)使用一個(gè)足夠長(zhǎng)的數(shù)組來(lái)存儲(chǔ)樹(shù)節(jié)點(diǎn)忠怖，那么 makeSet 要做的就是構(gòu)造出如圖的森林呢堰，其中每個(gè)元素都是一個(gè)單元素集合，即父節(jié)點(diǎn)是其自身凡泣。
const int MAXSIZE = 500;
int uset[MAXSIZE];
void makeSet(int size) {
for(int i = 0;i < size;i++) uset[i] = i;
}
接下來(lái)枉疼，就是 find 操作了，如果每次都沿著父節(jié)點(diǎn)向上查找鞋拟，那時(shí)間復(fù)雜度就是樹(shù)的高度骂维，完全不可能達(dá)到常數(shù)級(jí)。這里需要應(yīng)用一種非常簡(jiǎn)單而有效的策略：路徑壓縮贺纲。
路徑壓縮：就是在每次查找時(shí)航闺，令查找路徑上的每個(gè)節(jié)點(diǎn)都直接指向根節(jié)點(diǎn)，如圖所示猴誊。
// 遞歸版本
int find(int x) {
if (x != uset[x]) uset[x] = find(uset[x]);
return uset[x];
}
// 非遞歸版本
int find(int x) {
int p = x, t;
while (uset[p] != p) p = uset[p];
while (x != p) { t = uset[x]; uset[x] = p; x = t; }
return x;
}
最后是合并操作 unionSet潦刃，并查集的合并也非常簡(jiǎn)單，就是將一個(gè)集合的樹(shù)根指向另一個(gè)集合的樹(shù)根懈叹，如圖所示乖杠。
這里也可以應(yīng)用一個(gè)簡(jiǎn)單的啟發(fā)式策略：按秩合并。該方法使用秩來(lái)表示樹(shù)高度的上界澄成，在合并時(shí)胧洒，總是將具有較小秩的樹(shù)根指向具有較大秩的樹(shù)根笆包。簡(jiǎn)單的說(shuō)，就是總是將比較矮的樹(shù)作為子樹(shù)略荡，添加到較高的樹(shù)中庵佣。為了保存秩，需要額外使用一個(gè)與 uset 同長(zhǎng)度的數(shù)組汛兜，并將所有元素都初始化為 0巴粪。
void unionSet(int x, int y) {
if ((x = find(x)) == (y = find(y))) return;
if (rank[x] > rank[y]) uset[y] = x;
else {
uset[x] = y;
if (rank[x] == rank[y]) rank[y]++;
}
}
除了按秩合并，并查集還有一種常見(jiàn)的策略：按集合中元素個(gè)數(shù)合并粥谬，將包含節(jié)點(diǎn)較少的樹(shù)根肛根，指向包含節(jié)點(diǎn)較多的樹(shù)根。這個(gè)策略與按秩合并的策略類似漏策，同樣可以提升并查集的運(yùn)行速度派哲，而且省去了額外的 rank 數(shù)組。
這樣的并查集具有一個(gè)略微不同的定義掺喻，即若 uset 的值是正數(shù)芭届，則表示該元素的父節(jié)點(diǎn)（的索引）；若是負(fù)數(shù)感耙，則表示該元素是所在集合的代表（即樹(shù)根）褂乍，而且值的相反數(shù)即為集合中的元素個(gè)數(shù)。相應(yīng)的代碼如下所示：
如果要獲取某個(gè)元素 x 所在集合包含的元素個(gè)數(shù)即硼，可以使用 -uset[find(x)] 得到逃片。
const int MAXSIZE = 500;
int uset[MAXSIZE];
void makeSet(int size) {
for(int i = 0;i < size;i++) uset[i] = -1;
}
int find(int x) {
if (uset[x] < 0) return x;
uset[x] = find(uset[x]);
return uset[x];
}
void unionSet(int x, int y) {
if ((x = find(x)) == (y = find(y))) return;
if (uset[x] < uset[y]) {
uset[x] += uset[y];
uset[y] = x;
} else {
uset[y] += uset[x];
uset[x] = y;
}
}
時(shí)間復(fù)雜度
Statement: If m operations, either Union or Find, are applied to n elements, the total run time is O(m * logn)
證明參見(jiàn)：https://en.wikipedia.org/wiki/Proof_of_O(log*n)_time_complexity_of_union%E2%80%93find
LeeCode題目
LeetCode題目：684. Redundant Connection
In this problem, a tree is an undirected 無(wú)向圖 graph that is connected and has no cycles.
The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.
The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.
Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.
Example 1:
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
Example 2:
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The given undirected graph will be like this:
Note:
- The size of the input 2D-array will be between 3 and 1000.
- Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.
class Solution {
public int[] findRedundantConnection(int[][] edges) {
int[] parent = new int[2001];
// makeSet(s)：建立一個(gè)新的并查集
for (int i = 0; i < parent.length; i++) parent[i] = i;
for (int[] edge: edges){
int f = edge[0], t = edge[1];
// 判斷兩個(gè)元素是否位于同一個(gè)集合，只要將它們各自的代表比較一下就可以了
if (find(parent, f) == find(parent, t)) {
return edge;
}
else {
unionSet(parent, f, t);
}
}
return new int[2];
}
// find(x)：找到元素 x 所在的集合的代表
private int find(int[] parent, int f) {
// 路徑壓縮
if (f != parent[f]) {
parent[f] = find(parent, parent[f]);
}
return parent[f];
}
// unionSet(x, y)：把元素 x 和元素 y 所在的集合合并只酥，要求 x 和 y 所在的集合不相交褥实，如果相交則不合并。
private void unionSet(int[] parent, int x, int y) {
if ((x = find(parent, x)) == (y = find(parent, y))) return;
parent[x] = y;
}
}
LeetCode題目：685. Redundant Connection II
In this problem, a rooted tree is a directed 有向圖 graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.
The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, ..., N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.
The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] that represents a directed edge connecting nodes u and v, where u is a parent of child v.
Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.
Example 1:
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given directed graph will be like this:
Example 2:
Input: [[1,2], [2,3], [3,4], [4,1], [1,5]]
Output: [4,1]
Explanation: The given directed graph will be like this:
Note:
- The size of the input 2D-array will be between 3 and 1000.
- Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.
class Solution {
public int[] findRedundantDirectedConnection(int[][] edges) {
int[] parent = new int[edges.length];
// makeSet(s)：建立一個(gè)新的并查集
for (int i = 0; i < edges.length; i++) parent[i] = i;
int[] candidate1 = null, candidate2 = null;
for (int[] edge: edges){
int rootx = find(parent, edge[0] - 1);
int rooty = find(parent, edge[1] - 1);
if (rootx != rooty) {
// record the last edge which results in "multiple parents" issue
if (rooty != edge[1]-1) {
candidate1 = edge;
}
else {
unionSet(parent, edge[1] - 1, edge[0] - 1);
}
}
else {
// record last edge which results in "cycle" issue, if any.
candidate2 = edge;
}
}
// if there is only one issue, return this one.
if (candidate1 == null) return candidate2;
if (candidate2 == null) return candidate1;
// If both issues present, then the answer should be the first edge which results in "multiple parents" issue
// Could use map to skip this pass, but will use more memory.
for (int[] e : edges) {
if (e[1] == candidate1[1]) {
return e;
}
}
return new int[2];
}
// find(x)：找到元素 x 所在的集合的代表
private int find(int[] parent, int f) {
// 路徑壓縮
if (f != parent[f]) {
parent[f] = find(parent, parent[f]);
}
return parent[f];
}
// unionSet(x, y)：把元素 x 和元素 y 所在的集合合并裂允，要求 x 和 y 所在的集合不相交损离，如果相交則不合并。
private void unionSet(int[] parent, int x, int y) {
if ((x = find(parent, x)) == (y = find(parent, y))) return;
parent[x] = y;
}
}
LeetCode題目：261. Graph Valid Tree
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
For example:
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.
Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
class Solution {
public boolean validTree(int n, int[][] edges) {
// initialize n isolated islands
int[] nums = new int[n];
for(int i = 0; i < nums.length; i++) {
nums[i] = i;
}
// perform union find
for (int i = 0; i < edges.length; i++) {
int x = find(nums, edges[i][0]);
int y = find(nums, edges[i][1]);
// if two vertices happen to be in the same set
// then there's a cycle
if (x == y) return false;
// union
nums[x] = y;
}
return edges.length == n - 1;
}
public int find(int nums[], int i) {
if(i != nums[i]) {
nums[i] = find(nums, nums[i]);
}
return nums[i];
}
}
LeetCode題目：305. Number of Islands II
A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example:
Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).
0 0 0
0 0 0
0 0 0
Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.
1 0 0
0 0 0 Number of islands = 1
0 0 0
Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.
1 1 0
0 0 0 Number of islands = 1
0 0 0
Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.
1 1 0
0 0 1 Number of islands = 2
0 0 0
Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.
1 1 0
0 0 1 Number of islands = 3
0 1 0
We return the result as an array: [1, 1, 2, 3]
Challenge:
- Can you do it in time complexity
O(k log mn), where k is the length of thepositions?
class Solution {
int[][] dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> result = new ArrayList<>();
if(m <= 0 || n <= 0) return result;
int count = 0;
/*
使用DSU并查集
*/
// one island = one tree
int[] roots = new int[m * n];
Arrays.fill(roots, -1);
for(int[] p : positions) {
// 該位置對(duì)應(yīng)二維數(shù)組的編號(hào)
int curIdx = n * p[0] + p[1];
// add new island
roots[curIdx] = curIdx;
count++;
for(int[] dir : dirs) {
// 遍歷四個(gè)方向
int x = p[0] + dir[0];
int y = p[1] + dir[1];
int neighbourIdx = n * x + y;
// 邊界檢測(cè)
if(x < 0 || x >= m || y < 0 || y >= n) continue;
// 如果鄰居不是島嶼則忽略
if(roots[neighbourIdx] == -1) continue;
// 鄰居島嶼的root
int neighbourRoot = find(roots, neighbourIdx);
// if neighbor is in another island
if(roots[curIdx] != neighbourRoot) {
// union two islands
roots[curIdx] = neighbourRoot;
// current tree root = joined tree root
curIdx = neighbourRoot;
count--;
}
}
result.add(count);
}
return result;
}
public int find(int[] roots, int id) {
if(id != roots[id]) {
roots[id] = find(roots, roots[id]);
}
return roots[id];
}
}
