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
类似find number of islands。本题对小岛的定义是同行同列有相同的石头就是一个岛。一个小岛最多能被切割size -1次。所以只要遍历所有小岛就可以。
union find的做法。对小岛的查找只要row或col相同就属于一个岛
O(m * n) time
class Solution { public int removeStones(int[][] stones) { Map<Integer, Integer> rows = new HashMap<>(); Map<Integer, Integer> cols = new HashMap<>(); Map<Integer, Integer> ids = new HashMap<>(); Map<Integer, Integer> sizes = new HashMap<>(); int id = 0; for (int[] stone : stones) { int addi = 1; if (!rows.containsKey(stone[0])) { rows.put(stone[0], id); ids.put(id, id); sizes.put(id, addi); id++; addi = 0; } if (!cols.containsKey(stone[1])) { cols.put(stone[1], id); ids.put(id, id); sizes.put(id, addi); id++; addi = 0; } int rowRoot = findRoot(rows.get(stone[0]), ids); int colRoot = findRoot(cols.get(stone[1]), ids); if (rowRoot != colRoot) { if (sizes.get(colRoot) > sizes.get(rowRoot)) { ids.put(rowRoot, colRoot); sizes.put(colRoot, sizes.get(colRoot) + sizes.get(rowRoot) + addi); rows.put(stone[0], colRoot); cols.put(stone[1], colRoot); }else { ids.put(colRoot, rowRoot); sizes.put(rowRoot, sizes.get(colRoot) + sizes.get(rowRoot) + addi); rows.put(stone[0], rowRoot); cols.put(stone[1], rowRoot); } }else { sizes.put(rowRoot, sizes.get(rowRoot) + addi); } } int size = 0; Set<Integer> iddd = new HashSet<>(); for (int i : ids.values()) { iddd.add(findRoot(i, ids)); } for (int i : iddd) { size += sizes.get(i) - 1; } return size; } private int findRoot(int p, Map<Integer, Integer> ids) { while (ids.get(p) != p) { ids.put(p, ids.get(ids.get(p))); p = ids.get(p); } return p; } }
No comments:
Post a Comment