class Solution {
public:
int removeStones(vector<vector<int>>& stones) {
}
};
947. 移除最多的同行或同列石头
n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。
给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。
示例 1：
输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] 输出：5 解释：一种移除 5 块石头的方法如下所示： 1. 移除石头 [2,2] ，因为它和 [2,1] 同行。 2. 移除石头 [2,1] ，因为它和 [0,1] 同列。 3. 移除石头 [1,2] ，因为它和 [1,0] 同行。 4. 移除石头 [1,0] ，因为它和 [0,0] 同列。 5. 移除石头 [0,1] ，因为它和 [0,0] 同行。 石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。
示例 2：
输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]] 输出：3 解释：一种移除 3 块石头的方法如下所示： 1. 移除石头 [2,2] ，因为它和 [2,0] 同行。 2. 移除石头 [2,0] ，因为它和 [0,0] 同列。 3. 移除石头 [0,2] ，因为它和 [0,0] 同行。 石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。
示例 3：
输入：stones = [[0,0]] 输出：0 解释：[0,0] 是平面上唯一一块石头，所以不可以移除它。
提示：
1 <= stones.length <= 10000 <= xi, yi <= 104原站题解
golang 解法, 执行用时: 24 ms, 内存消耗: 6.6 MB, 提交时间: 2022-12-04 13:57:06
func removeStones(stones [][]int) int {
fa, rank := map[int]int{}, map[int]int{}
var find func(int) int
find = func(x int) int {
if _, has := fa[x]; !has {
fa[x], rank[x] = x, 1
}
if fa[x] != x {
fa[x] = find(fa[x])
}
return fa[x]
}
union := func(x, y int) {
fx, fy := find(x), find(y)
if fx == fy {
return
}
if rank[fx] < rank[fy] {
fx, fy = fy, fx
}
rank[fx] += rank[fy]
fa[fy] = fx
}
for _, p := range stones {
union(p[0], p[1]+10001)
}
ans := len(stones)
for x, fx := range fa {
if x == fx {
ans--
}
}
return ans
}
javascript 解法, 执行用时: 92 ms, 内存消耗: 48.5 MB, 提交时间: 2022-12-04 13:56:45
/**
* @param {number[][]} stones
* @return {number}
*/
var removeStones = function(stones) {
const dsu = new DisjointSetUnion();
for (const [x, y] of stones) {
dsu.unionSet(x, y + 10001);
}
return stones.length - dsu.numberOfConnectedComponent();
};
class DisjointSetUnion {
constructor() {
this.f = new Map();
this.rank = new Map();
}
find (x) {
if (!this.f.has(x)) {
this.f.set(x, x);
this.rank.set(x, 1);
return x;
}
if (this.f.get(x) === x) {
return x;
}
this.f.set(x, this.find(this.f.get(x)));
return this.f.get(x);
}
unionSet (x, y) {
let fx = this.find(x), fy = this.find(y);
if (fx && fy) {
}
if (fx === fy) {
return;
}
if (this.rank.get(fx) < this.rank.get(fy)) {
[fx, fy] = [fy, fx];
}
this.rank.set(fx, this.rank.get(fy) + this.rank.get(fx));
this.f.set(fy, fx);
}
numberOfConnectedComponent () {
let sum = 0;
for (const [x, fa] of this.f.entries()) {
if (x === fa) {
sum++;
}
}
return sum;
}
}
python3 解法, 执行用时: 60 ms, 内存消耗: 15.4 MB, 提交时间: 2022-12-04 13:56:28
class DisjointSetUnion:
def __init__(self):
self.f = dict()
self.rank = dict()
def find(self, x: int) -> int:
if x not in self.f:
self.f[x] = x
self.rank[x] = 1
return x
if self.f[x] == x:
return x
self.f[x] = self.find(self.f[x])
return self.f[x]
def unionSet(self, x: int, y: int):
fx, fy = self.find(x), self.find(y)
if fx == fy:
return
if self.rank[fx] < self.rank[fy]:
fx, fy = fy, fx
self.rank[fx] += self.rank[fy]
self.f[fy] = fx
def numberOfConnectedComponent(self) -> int:
return sum(1 for x, fa in self.f.items() if x == fa)
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
dsu = DisjointSetUnion()
for x, y in stones:
dsu.unionSet(x, y + 10001)
return len(stones) - dsu.numberOfConnectedComponent()
python3 解法, 执行用时: 64 ms, 内存消耗: 17.2 MB, 提交时间: 2022-12-04 13:56:11
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
n = len(stones)
edge = collections.defaultdict(list)
rec = collections.defaultdict(list)
for i, (x, y) in enumerate(stones):
rec[x].append(i)
rec[y + 10001].append(i)
for vec in rec.values():
k = len(vec)
for i in range(1, k):
edge[vec[i - 1]].append(vec[i])
edge[vec[i]].append(vec[i - 1])
def dfs(x: int):
vis.add(x)
for y in edge[x]:
if y not in vis:
dfs(y)
vis = set()
num = 0
for i in range(n):
if i not in vis:
num += 1
dfs(i)
return n - num
golang 解法, 执行用时: 20 ms, 内存消耗: 6.8 MB, 提交时间: 2022-12-04 13:55:53
func removeStones(stones [][]int) int {
n := len(stones)
rowCol := map[int][]int{}
for i, p := range stones {
x, y := p[0], p[1]+10001
rowCol[x] = append(rowCol[x], i)
rowCol[y] = append(rowCol[y], i)
}
graph := make([][]int, n)
for _, id := range rowCol {
for i := 1; i < len(id); i++ {
v, w := id[i-1], id[i]
graph[v] = append(graph[v], w)
graph[w] = append(graph[w], v)
}
}
vis := make([]bool, n)
var dfs func(int)
dfs = func(v int) {
vis[v] = true
for _, w := range graph[v] {
if !vis[w] {
dfs(w)
}
}
}
cnt := 0
for i, v := range vis {
if !v {
cnt++
dfs(i)
}
}
return n - cnt
}
javascript 解法, 执行用时: 128 ms, 内存消耗: 50.8 MB, 提交时间: 2022-12-04 13:55:36
/**
* @param {number[][]} stones
* @return {number}
*/
var removeStones = function(stones) {
const n = stones.length;
const edge = {};
const rec = {};
for (const [i, [x, y]] of stones.entries()) {
rec[x] ? rec[x].push(i) : rec[x] = [i];
rec[y + 10001] ? rec[y + 10001].push(i) : rec[y + 10001] = [i];
}
for (const vec of Object.values(rec)) {
const k = vec.length;
for (let i = 1; i < k; i++) {
edge[vec[i - 1]] ? edge[vec[i - 1]].push(vec[i]) : edge[vec[i - 1]] = [vec[i]];
edge[vec[i]] ? edge[vec[i]].push(vec[i - 1]) : edge[vec[i]] = [vec[i - 1]];
}
}
const vis = new Set();
let num = 0;
for (let i = 0; i < n; i++) {
if (!vis.has(i)) {
num++;
dfs(i, vis, edge);
}
}
return n - num;
};
const dfs = (x, vis, edge) => {
vis.add(x);
if (edge[x]){
for (const y of edge[x]) {
if (!vis.has(y)) {
dfs(y, vis, edge);
}
}
}
}
python3 解法, 执行用时: 1032 ms, 内存消耗: 17.4 MB, 提交时间: 2022-12-04 13:55:17
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
n = len(stones)
edge = collections.defaultdict(list)
for i, (x1, y1) in enumerate(stones):
for j, (x2, y2) in enumerate(stones):
if x1 == x2 or y1 == y2:
edge[i].append(j)
def dfs(x: int):
vis.add(x)
for y in edge[x]:
if y not in vis:
dfs(y)
vis = set()
num = 0
for i in range(n):
if i not in vis:
num += 1
dfs(i)
return n - num