947.移除最多的同行或同列石头

链接：947.移除最多的同行或同列石头
难度：Medium
标签：深度优先搜索、并查集、图、哈希表
简介：n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。

题解 1 - typescript

• 编辑时间：2021-01-15
• 执行用时：108ms
• 内存消耗：45.4MB
• 编程语言：typescript
• 解法介绍：并查集。

function removeStones(stones: number[][]): number {
  const arr: number[] = [];
  const n = stones.length;
  let count = 0;
  const find = (x: number) => {
    if (arr[x] === undefined) {
      arr[x] = x;
      count++;
    }
    if (x !== arr[x]) {
      arr[x] = find(arr[x]);
    }
    return arr[x];
  };
  const union = (u: number, v: number) => {
    const x = find(u);
    const y = find(v);
    if (x !== y) {
      arr[x] = y;
      count--;
    }
  };
  stones.forEach(([x, y]) => union(x + 10000, y));
  return n - count;
}

题解 2 - typescript

• 编辑时间：2021-05-01
• 执行用时：208ms
• 内存消耗：44.1MB
• 编程语言：typescript
• 解法介绍：并查集。

class UnionFind {
  elements: number[];
  constructor(public size: number) {
    this.elements = new Array(size).fill(0).map((_, i) => i);
  }
  same(v1: number, v2: number): boolean {
    return this.find(v1) === this.find(v2);
  }
  find(v: number): number {
    return v === this.elements[v] ? v : (this.elements[v] = this.find(this.elements[v]));
  }
  union(v1: number, v2: number): void {
    const e1 = this.find(v1);
    const e2 = this.find(v2);
    if (e1 !== e2) {
      this.elements[e1] = e2;
      this.size--;
    }
  }
}
function removeStones(stones: number[][]): number {
  const len = stones.length;
  const uf = new UnionFind(len);
  const findIndex = (stone: number[]): number[] => {
    const ans: number[] = [];
    for (let i = 0; i < len; i++) {
      const s = stones[i];
      if (s !== stone && (s[0] === stone[0] || s[1] === stone[1])) {
        ans.push(i);
      }
    }
    return ans;
  };
  for (let i = 0; i < len; i++) {
    const stone = stones[i];
    findIndex(stone).forEach(v => uf.union(i, v));
  }
  const cache: Record<number, number> = {};
  for (let i = 0, l = uf.elements.length; i < l; i++) {
    const index = uf.find(i);
    cache[index] = (cache[index] ?? 0) + 1;
  }
  return Object.values(cache).reduce((total, cur) => (total += cur - 1), 0);
}