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

????? 东边日出西边雨,道是无晴却有晴 本文由博客端 http://106.12.51.176 主动推送

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

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

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

题目链接

题名 通过率 难度
冗余连接 II 40.7% 困难

解题思路

题目说的有点绕,我简化一下就是: 查找有向图的多余边(去掉这条边可以使有向图变成一个连通图 , 并且只有一个根节点 , 根节点就是入度为 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. 图论: 连通图 , 生成树
  • 每日抑题
    6 引用 • 3 回帖
  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    195 引用 • 74 回帖 • 1 关注
  • 连通图
    1 引用 • 3 回帖
1 操作
ludengke95 在 2020-09-17 16:15:36 更新了该帖

赞助商 我要投放

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • 88250

    请看 Solo 用户指南 FAQ。

    1 回复
  • 其他回帖
  • ludengke95
    作者

    谢大佬,启用了 lute-http,好了。

  • ludengke95
    作者

    @88250 大佬 , 不知道为啥,表格在社区就好好的 , 在我博客里面就是 md 源码 , 我更新 solo 镜像了。

    1 回复