美文网首页
剑指 Offer II 115. 重建序列

剑指 Offer II 115. 重建序列

作者: 邦_ | 来源:发表于2022-08-29 10:04 被阅读0次

注意起始位置。。 有的是从0开始。有的是从 1开始
边的构造。。注意是否是只有两个。。注意是否会有重复的边
有重复的边的话。会造成入度统计出错。所以要用Set避免重复累加
然后这道题的关键点在于 每次找到的入度为0的点是否只有一个 如果只有一个的话。那么最后的结果唯一,这点很难想到

func sequenceReconstruction(_ nums: [Int], _ sequences: [[Int]]) -> Bool {
       
        let len = nums.count
        //构建图,因为sequences里面有像这样的。。 [[1,2],[1,3],[1,2,3]]
        var edges = Array.init(repeating: Set<Int>(), count: len + 1)
        var indeg = Array.init(repeating: 0, count: len + 1)
        for info in sequences {
            
            let tempLen = info.count
            for i in 1..<tempLen {
                if !edges[info[i - 1]].contains(info[i]){
                    edges[info[i - 1]].insert(info[i])
                    indeg[info[i]] += 1
                }
            }
        }
        var tempArray = [Int]()
        //根据题意是从1开始的
        //寻找入度为0的节点
        for i in 1...len {
            
            if indeg[i] == 0 {
                tempArray.append(i)
            }
            
        }
        
        while !tempArray.isEmpty {
            if tempArray.count > 1 {
                return false
            }
            let v = tempArray.removeLast()
            //相邻点的入度减少1
            for nextV in edges[v]{
                indeg[nextV] -= 1
                if indeg[nextV] == 0 {
                    tempArray.append(nextV)
                }
            }
        }
        return true
      
    }





相关文章

网友评论

      本文标题:剑指 Offer II 115. 重建序列

      本文链接:https://www.haomeiwen.com/subject/wezrgrtx.html