Problem
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
Solution 2: Union Find
Find all connected components (islands)
Ans = # of stones – # of islands
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
// Author: Huahua, running time: 16 ms class Solution { public: int removeStones(vector<vector<int>>& stones) { const int kSize = 10000; DSU dsu(kSize * 2); for (const auto& stone : stones) dsu.Union(stone[0], stone[1] + kSize); unordered_set<int> seen; for (const auto& stone : stones) seen.insert(dsu.Find(stone[0])); return stones.size() - seen.size(); } private: class DSU { public: DSU(int n): p_(n) { for (int i = 0 ; i < n; ++i) p_[i] = i; } void Union(int i, int j) { p_[Find(i)] = Find(j); } int Find(int i) { if (p_[i] != i) p_[i] = Find(p_[i]); return p_[i]; } private: vector<int> p_; }; }; |
Related Problems
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment