947. Removal of the largest number of stones in the same row or row

The title

N stones are placed at integer coordinate points in a two-dimensional plane. There can be no more than one stone on each coordinate point.

A stone can be removed if there are other stones in the same row or row as a stone.

Stones [I] = [xi, yi]; stones[I] = [xi, yi];

Example 1

Input: featuring = [[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2]] output: 5: a way to remove the five stone is as follows: 1. Remove stone [2,2] as it walks with stone [2,1]. 2. Remove rock [2,1] as it is in the same column as [0,1]. 3. Remove stone [1,2] as it walks with [1,0]. 4. Remove the stone [1,0] as it is in the same column as [0,0]. 5. Remove the rock [0,1] as it runs with [0,0]. The stone [0,0] cannot be removed because it is not in line/column with another stone.Copy the code

Example 2

Input: featuring = [[0, 0], [0, 2], [1, 1], [2, 0], [2]] output: three explanations: a method of removing 3 stone is as follows: 1. Remove stone [2,2] as it walks with stone [2,0]. 2. Remove rock [2,0] as it is in the same column as [0,0]. 3. Remove the rock [0,2] as it runs with [0,0]. Stones [0,0] and [1,1] cannot be removed because they are not in line/column with another stone.Copy the code

Answer key

Check and set

  • For any rock, the coordinates are x,y
  • For any stone, whether other stones already exist on the X-axis or Y-axis of coordinates X and y
  • If other stones already exist, merge
  • Connect all the stones in the same row
  • The number of connected graphs obtained in the coordinate system is the minimum number of stones to be retained
  • Total number of stones – the minimum number of stones to be saved is the answer

code

var removeStones = function (stones) {
  let count = 0
  const map = new Map(a)for (let i = 0; i < stones.length; i++) {
    const [x, y] = stones[i]
    merge(x, y + 10001)}return stones.length - count

  function merge(x, y) {
    const rootX = find(x)
    const rootY = find(y)
    if (rootX === rootY) return
    map.set(rootX, rootY)
    count--
  }
  function find(n) {
    if (map.get(n) === undefined) {
      count++
      map.set(n, n)
    }
    if(n ! == map.get(n)) { map.set(n, find(map.get(n))) }return map.get(n)
  }
}

Copy the code