一个域名可以绑定几个网站,网站建设如何做账,网站改版升级总结,公司模板设计1. 题目
我们将石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
每次 move 操作都会移除一块所在行或者列上有其他石头存在的石头。
请你设计一个算法#xff0c;计算最多能执行多少次 move 操作#xff1f;
示例 1#xff1a;
输入#xf…1. 题目
我们将石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
每次 move 操作都会移除一块所在行或者列上有其他石头存在的石头。
请你设计一个算法计算最多能执行多少次 move 操作
示例 1
输入stones [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出5示例 2
输入stones [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出3示例 3
输入stones [[0,0]]
输出0提示
1 stones.length 1000
0 stones[i][j] 10000来源力扣LeetCode 链接https://leetcode-cn.com/problems/most-stones-removed-with-same-row-or-column 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考 数据结构–并查集Disjoint-Set
把行号、列号看成一个单元用并查集把每个点的行列merge最后查找都有点有几个单元点的个数减去单元个数就是能移走的石子
class dsu
{vectorint f;
public:dsu(int n){f.resize(n);for(int i 0; i n; i)f[i] i;}void merge(int a, int b){int fa find(a), fb find(b);f[fa] fb;}int find(int a){int origin a;while(f[a] ! a){a f[a];}return f[origin] a;}
};
class Solution {
public:int removeStones(vectorvectorint stones) {dsu u(20000);unordered_setint s;for(int i 0; i stones.size(); i)u.merge(stones[i][0], stones[i][1]10000);for(int i 0; i stones.size(); i)s.insert(u.find(stones[i][0]));return stones.size()-s.size();}
};60 ms 19.6 MB
