2021/01/15 每日一题 移除最多的同行或同列石头

LeetCode上移除最多的同行或同列石头，记录下解题思路

又是查并集，无语子......

题目的含义是最后每行每列上面只能有1个石头。假如传入removeStones([[0,1],[1,2],[1,3],[3,3],[2,3],[0,2]])数组。可以根据题意和传入的数组构建如下的图

所以整体思路是：

1. 创建传入数组长度的节点
2. 需要两层循环，内层是外层当前数据之后以后的所有数据
3. 开始循环之后只要判断当前i数据，和i后面所有数据是否存在同行同列的关系
4. 如果存在就设置j数据的parent是i
5. 双重循环结束之后，节点数组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
 }