莺时

东边日出西边雨,道是无晴却有晴

Open Source, Open Mind,
Open Sight, Open Future!
  menu
18 文章
3692 浏览
0 当前访客
ღゝ◡╹)ノ❤️

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

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

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

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

题目链接

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

解题思路

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

暴力思路

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

优化搜索

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

scala代码

 1import scala.collection.mutable._
 2import scala.language.postfixOps
 3
 4/**
 5 * 描述:
 6 * ${DESCRIPTION}
 7 *
 8 * @author ludengke
 9 * @create 2020-09-01 19:03
10 */
11object Solution3 extends App {
12  def findRedundantDirectedConnection(edges: Array[Array[Int]]): Array[Int] = {
13    for(i <- 0 to edges.length-1 reverse ){
14      if(isTree(edges,i)){
15        return edges(i)
16      }
17    }
18    Array()
19  }
20
21  def isTree(edges: Array[Array[Int]],index: Int): Boolean = {
22    //arr中标识节点的根节点.
23    val arr = ArrayBuffer[Int](0)
24    //初始化并查集基础数组,每个节点的父节点都是自己
25    for (i <- 1 to edges.map(_.max).max) {
26      arr += i
27    }
28    //遍历数组,计算点之前的父子关系,写入并查集
29    for(i <- 0 to edges.length-1 if i!=index ){
30      var tmp = edges(i)(0)
31      //查找父节点是自己的节点(查找当前节点的曾....祖父节点),这样的节点没有根节点
32      //这里没有采用路径压缩,路径压缩需要找到结果后递归修改arr内容,在不考虑速度的情况下,可以不压缩
33      //有兴趣:可以使用路径压缩,把这块单独抽象成一个递归函数
34      while(arr(tmp) != tmp){
35        tmp = arr(tmp)
36      }
37      //如果edges(i)是一个二维数组,0位是父节点,1位是子节点,如果找到的根节点是自己,证明成环,铁定不行
38      if(edges(i)(1) == tmp){
39        return false
40      }
41      //设置arr根节点
42      arr(edges(i)(1)) = tmp
43    }
44    //有且仅有一个根节点才能满足需求.
45    var sum = 0
46    for(i <- 1 until arr.length){
47      if(i == arr(i)){
48        sum += 1
49      }
50    }
51    sum == 1
52  }
53  println(findRedundantDirectedConnection(Array(Array(1,2),Array(1,3),Array(2,3))).mkString(","))
54  println(findRedundantDirectedConnection(Array(Array(1,2),Array(2,3),Array(3,4),Array(4,1),Array(1,5))).mkString(","))
55  println(findRedundantDirectedConnection(Array(Array(2,1),Array(3,1),Array(4,2),Array(1,4))).mkString(","))
56}

算法 or 数据结构

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

标题:Leetcode每日抑题(685. 冗余连接 II)
作者:ludengke95
地址:http://xvhi.ludengke95.xyz/articles/2020/09/17/1600324956879.html