Remove the most stones in a row or row

Subject to introduce

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. 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 will never be two stones on the same coordinate pointCopy the code

Thought analysis

Analysis of the question

The mistakes I’ve fallen into

You only need to keep one, and the first thing THAT comes to my mind is depth or breadth traversal, and it makes sense to start at one point and walk through all the points that one point can reach

If we build a graph, we need 10000*10000 memory, which is too sparse for less than 1000 data

For (int I =0; int I =0; i<10000; I++) go through it like this. To obtain we can use the adjacency matrix

Idea a breadth-first traversal

My final thought is this

The x-coordinate and y-coordinate linked list can be implemented using HashMap<Interger,HashSet< Interger >>, where the set can be deleted with continuous access to reduce repeated access

Idea two: Look up the set

Create a one-dimensional array containing the parent nodes of each stone

Then create two HashMaps to store points for rows and points for columns in three cases

  1. The ranks of stones that have never appeared, then are new stones that create a family of their own
  2. The row of the stone appears, so refer to the column as yourself, and then find that point through the row, and find the final node through getFather, and attach yourself to it
  3. If the row and column of the stone appear, with 2 first check whether the final node to which the row and column belong is a, yes, then it is ok, if not one, merge the two families
class Solution { int[] father; public int removeStones(int[][] stones) { father=new int[stones.length]; for (int i = 0; i < father.length; i++) { father[i]=-1; } HashMap<Integer,Integer>row=new HashMap<>(); HashMap<Integer,Integer>line=new HashMap<>(); for (int i = 0; i < stones.length; i++) { if(row.containsKey(stones[i][0])&&line.containsKey(stones[i][1])){ int num1=getFather(row.get(stones[i][0])); int num2=getFather(line.get(stones[i][1])); if(num1! =num2){ father[num1]=num2; } father[i]=num2; }else if(row.containsKey(stones[i][0])){ int num1=getFather(row.get(stones[i][0])); father[i]=num1; line.put(stones[i][1],i); }else if(line.containsKey(stones[i][1])){ int num2=getFather(line.get(stones[i][1])); father[i]=num2; row.put(stones[i][0],i); }else { row.put(stones[i][0],i); line.put(stones[i][1],i); } } int count=0; //System.out.println(Arrays.toString(father)); //System.out.println(row); //System.out.println(line); for (int i = 0; i < father.length; i++) { if(father[i]! =-1)count++; } return count; } public int getFather(Integer num){ if(father[num]==-1)return num; return getFather(father[num]); }}Copy the code