947.Most-Stones-Removed-with-Same-Row-or-Column

947. Most Stones Removed with Same Row or Column

题目地址

题目描述

On a 2D plane, we place stones at some integer coordinate points. Each coordinate point may have at most one stone.
​
Now, a move consists of removing a stone that shares a column or row with another stone on the grid.
​
What is the largest possible number of moves we can make?
​
Example 1:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
​
Example 2:
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
​
Example 3:
Input: stones = [[0,0]]
Output: 0
​
Note:
1 <= stones.length <= 1000
0 <= stones[i][j] < 10000

代码

Approach #2 Union-Find

Time O(N log N) Space O(N)
class Solution {
public int removeStones(int[][] stones) {
int N = stones.length;
DSU dsu = new DSU(2000);
​
for (int[] stone: stones) {
dsu.union(stone[0], stone[1] + 10000);
}
​
Set<Integer> seen = new HashSet();
for (int[] stone: stones) {
seen.add(dsu.find(stone[0]));
}
​
return N - seen.size();
}
}
​
class DSU {
int[] parent;
public DSU(int N) {
parent = new int[N];
for (int i = 0; i < N; i++) {
parent[i] = i;
}
}
​
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
​
public void union(int x, int y) {
parent[find(x)] = find(y);
}
}

Appraoch #3 DFS number of islands

class Solution {
// Ans = # of stones - # of islands
public int removeStones(int[][] stones) {
Set<int[]> visited = new HashSet();
int numOfIslands = 0;
for (int[] s1: stones) {
if (!visited.contains(s1)) {
dfs(s1, visited, stones);
numOfIslands++;
}
}
return stones.length - numOfIslands;
}
​
private void dfs(int[] s1, Set<int[]> visited, int[][] stones) {
visited.add(s1);
for (int[] s2: stones) {
if (!visited.contains(s2)) {
// stone with same row or column. group them into island
if (s1[0] == s2[0] || s1[1] == s2[1]) {
dfs(s2, visited, stones);
}
}
}
}
}

Approach #4 BFS

Find connected components, with some specific connected component, the remove count is Num of elements - 1
class Solution {
public int removeStones(int[][] stones) {
int N = stones.length;
int[] visited = new int[N];
int ret = 0;
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < N; i++) {
if (visited[i] == 0) {
q.add(i);
}
int tmp = 0;
while (!q.isEmpty()) {
Integer pos = q.poll();
if (visited[pos] == 1) continue;
int x = stones[pos][0];
int y = stones[pos][1];
tmp += 1;
visited[pos] = 1;
for (int j = 0; j < N; j++) {
if (visited[j] == 0 && (stones[j][0] == x || stones[j][1] == y)) {
q.add(j);
}
}
}
ret += (tmp != 0 ? (tmp - 1) : 0);
}
return ret;
}
}

Approach #1 DFS

Time: O(N^2) && Space: O(N^2)
class Solution {
public int removeStones(int[][] stones) {
int N = stones.length;
// graph[i][0] = the length of the 'list' graph[i][1:]
int[][] graph = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
graph[i][++graph[i][0]] = j; // ??
graph[j][++graph[j][0]] = i; // ??
}
}
}
​
int ans = 0;
boolean[] seen = new boolean[N];
for (int i = 0; i < N; i++) {
if (!seen[i]) {
Stack<Integer> stack = new Stack();
stack.push(i);
seen[i] = true;
ans--;
while (!stack.isEmpty()) {
int node = stack.pop();
ans++;
for (int k = 1; k <= graph[node][0]; k++) {
int nei = graph[node][k];
if (!seen[nei]) {
stack.push(nei);
seen[nei] = true;
}
}
}
}
}
​
return ans;
}
}