[B] [C] [D]

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:

Stones = [[0,0],[0,2],[1,1],[2,0],[2,2]] 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

Example 3:

Input: stones = [[0,0]] Output: 0 Explanation: [0,0] is the only stone on the plane, so it cannot be removed.Copy the code

Tip:

  • 1 <= stones.length <= 1000
  • 0 <= xi, yi <= 104
  • There are no two stones on the same coordinate point

Their thinking

In this case, it is like a game of poker. When there is more than one stone in a row or row, all but the last stone can be deleted. And this process can be recursive, so we can put stones in the same row or column into a set, such a set, only need to keep one stone. In this way, the number of stones that can be removed can be obtained. Because it is necessary to merge sets frequently in the process and obtain the set where the stone is located, the problem can be solved with the help of and refer to the set. If you do not understand and search set, you can see my article data structure – and search set, the paper introduces the concept of and search set, application scenarios and handwritten implementation of the whole process.

The demo

Code implementation

This. size = Array(n).fill(1); This. list = Array(n); for(let i = 0; i<n; i++){ this.list[i] = i; Find (x){if(this.list[x] === x) return x; Const root = this.find(this.list[x]) // Mount the current node as the root node, this.list[x] = root; return root; } merge(rootA,rootB){merge(rootA,rootB){ If (this.size[rootA]>this.size[rootB]){this.list[rootB] = rootA; Size [rootA] += this.size[rootB]}else{// If (rootA = rootB) {this.list[rootA] = rootB; Size [rootB] += this.size[rootA]}} var removeStones = function(stones) {const len = stones.length, Unionset = new unionset (len); // let res = 0; for(let i = 0; i<len-1; i++){ for(let j = i+1; j<len; J++) {if (featuring [I] [0] = = = featuring [j] [0] | | featuring [I] [1] = = = featuring [j] [1]) {/ / to get root node of the two elements in the collection const rootA = Find (I),rootB = unionset. Find (j) // If (rootA! ==rootB){ res++; Unionset. Merge (rootA,rootB)}}}} };Copy the code

At this point we are done with Leetcode-947 – removing the most stones in a row or row

If you have any questions or suggestions, please leave a comment!