Leetcode 每日抑题 (685. 冗余连接 II)

今天开启 LeetCode 的每日抑题系列 , LeetCode 会每天随机一道题作为签到题.我也是菜鸡,如果今天没 A 掉,那只能证明我离大神又进了一步.

或许有兴趣的小朋友就问了:"你用 scala 刷题 ? scala 不适合呀"

"scala 刷题对于我来说只是熟悉 scala 基本操作 , 或许没几天 , 我就换 golang? JavaScript? "

题目链接

解题思路

题目说的有点绕,我简化一下就是: 查找有向图的多余边(去掉这条边可以使有向图变成一个连通图 , 并且只有一个根节点 , 根节点就是入度为 0 的点 , 说白了就是树)

暴力思路

循环遍历删除每一条边 :
    判断删除后的图是否满足要求,通过遍历找到根节点
        使用dfs找到所有能够到达的点,判断与给出的全部点是否有遗漏(计算集合差集)

优化搜索

循环遍历删除每一条边 :
    判断删除后的图是否满足要求,使用并查集查询根节点,是否仅有一个

scala 代码

import scala.collection.mutable._
import scala.language.postfixOps

/**
 * 描述:
 * ${DESCRIPTION}
 *
 * @author ludengke
 * @create 2020-09-01 19:03
 */
object Solution3 extends App {
  def findRedundantDirectedConnection(edges: Array[Array[Int]]): Array[Int] = {
    for(i <- 0 to edges.length-1 reverse ){
      if(isTree(edges,i)){
        return edges(i)
      }
    }
    Array()
  }

  def isTree(edges: Array[Array[Int]],index: Int): Boolean = {
    //arr中标识节点的根节点.
    val arr = ArrayBuffer[Int](0)
    //初始化并查集基础数组,每个节点的父节点都是自己
    for (i <- 1 to edges.map(_.max).max) {
      arr += i
    }
    //遍历数组,计算点之前的父子关系,写入并查集
    for(i <- 0 to edges.length-1 if i!=index ){
      var tmp = edges(i)(0)
      //查找父节点是自己的节点(查找当前节点的曾....祖父节点),这样的节点没有根节点
      //这里没有采用路径压缩,路径压缩需要找到结果后递归修改arr内容,在不考虑速度的情况下,可以不压缩
      //有兴趣:可以使用路径压缩,把这块单独抽象成一个递归函数
      while(arr(tmp) != tmp){
        tmp = arr(tmp)
      }
      //如果edges(i)是一个二维数组,0位是父节点,1位是子节点,如果找到的根节点是自己,证明成环,铁定不行
      if(edges(i)(1) == tmp){
        return false
      }
      //设置arr根节点
      arr(edges(i)(1)) = tmp
    }
    //有且仅有一个根节点才能满足需求.
    var sum = 0
    for(i <- 1 until arr.length){
      if(i == arr(i)){
        sum += 1
      }
    }
    sum == 1
  }
  println(findRedundantDirectedConnection(Array(Array(1,2),Array(1,3),Array(2,3))).mkString(","))
  println(findRedundantDirectedConnection(Array(Array(1,2),Array(2,3),Array(3,4),Array(4,1),Array(1,5))).mkString(","))
  println(findRedundantDirectedConnection(Array(Array(2,1),Array(3,1),Array(4,2),Array(1,4))).mkString(","))
}

算法 or 数据结构

1. 算法学习笔记(1) : 并查集
2. 图论: 连通图 , 生成树