LeetCode上移除最多的同行或同列石头，记录下解题思路
又是查并集，无语子......
题目的含义是最后每行每列上面只能有1个石头。假如传入removeStones([[0,1],[1,2],[1,3],[3,3],[2,3],[0,2]])数组。可以根据题意和传入的数组构建如下的图
以[0,1]为起点，可以连通所有的元素，这些元素就都可以删除掉，这些元素的特点就是在同行同列，对应在数据上的结果就是数组的两个数有一个相同
所以整体思路是：
- 创建传入数组长度的节点
- 需要两层循环，内层是外层当前数据之后以后的所有数据
- 开始循环之后只要判断当前
i数据，和i后面所有数据是否存在同行同列的关系 - 如果存在就设置
j数据的parent是i - 双重循环结束之后，节点数组
nodes中当前元素的parent不是本身的元素，就是我们需要删除的数据
class node {
constructor (i) {
// 创建的节点都把自己的父亲先设为自己
this.parent = this
// 添加val元素是为了更方便的观察
this.val = i
}
}
var removeStones = function(stones) {
// 保存传入数组长度
let len = stones.length
let nodes = new Array(len).fill(0).map((x,i) => new node(i))
// 返回结果
let res = 0
// 查找传入元素的parent函数
let find = function (x) {
// 如果这个元素的parent不是本身，那就再往上查找，直到为本身的时候就返回
if (x !== x.parent)
return find(x.parent)
return x
}
// 遍历整个数组
for(let i = 0;i<len;i++) {
// 获取第i个数据的位置信息
let [x,y] = stones[i]
for(let j = i+1; j<len;j++) {
let [z,w] = stones[j]
// 遍历i之后的所有数据和第i个数据的关系
if(x===z || y===w) {
// 如果这两个点在同一排或者同一列
// 那么就把j的parent设为i
find(nodes[j]).parent = find(nodes[i])
}
}
}
// 这样输出的nodes数组，里面父元素不是本身的人就是可连通的，那么就是可删除的
nodes.map((x,i) => {
if (x.parent !== nodes[i]) {
res++
}
})
return res
}
