傳送門
思路
干貨太干就不太好理解了，以下會有點話癆(￣▽￣)"
首先題目給了一個二維stones陣列，存盤每個石子的坐標，因為在同行或者同列的石子最終可以被取到只剩下一個，那么我們將同行同列的石子歸屬于一個集合，開始套用并查集的思想求一下有幾個集合似乎就搞定了？想到這是我看到題目的想法，但是為了實際使用并查集，有幾個細節需要注意：
-
本題并查集究竟要合并什么？對于一個坐標(x,y)來說它有兩個值組成，x表示所屬x行，y表示所屬于y列，而按照我們既定的思維，同行同列的石子屬于一個集合，那么關鍵就在于(x,y)作為橋梁溝通了x行和y列，使得行集合與列集合合并成一個集合了（它們兩個集合可以取得只剩下一個石子），所以需要合并的是行號和列號
-
這個stones陣列存盤的是二維空間的坐標，而并查集是在一維進行操作的，好比說0行0列都是0，怎么區分？這里用一個樸素的方法，由于x，y的取值范圍為0~10^4，那么將其中一個軸+10001或者減去10001就能保證二維的資料映射到一維進行區分，就是x映射為x+10001，用映射的值去和y進行并查集操作
-
最后我們統計一個所有的不相交子集的個數（好像也叫做：極大連通子圖個數，連通分量），用石子數減去集合數就是最多可以移除的石子數
Java解法，其實是偽裝成Java的c++，由于還不怎么熟悉Java的一些集合框架，這題直接開了大的空間
class Solution {
int parent[] = new int[20005];
int vis[] = new int[20005];
public int removeStones(int[][] stones) {
int ans = 0;
for (int i = 0; i < 20005; i++){
parent[i] = i;
vis[i] = 0;
}
for (int[] stone : stones) {
//(x,y)是一個坐標，而第x行所有點在一個集合，第y列
//所有點在一個集合，(x,y)的存在就使得x行集合與y列
//集合可以合并為一個集合，因為它們構成了一個連通圖
//配合+10001操作，并查集可以從二維轉化為一維，從而
//實作編號為x+10001的行集合與編號為y的列集合的合并
union(stone[0] + 10001, stone[1]);
vis[stone[0] + 10001] = 1;
vis[stone[1]] = 1;
}
for(int i = 0; i < 20005; i++) {
if(vis[i] == 1 && parent[i] == i) ans++;
}
return stones.length - ans;
}
public void union(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx != fy) parent[fy] = fx;
}
public int find(int x) {
while (parent[x] != x) x = parent[x];
return x;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/250025.html
標籤：Java
上一篇：[翻譯]正則引擎的幾種分類