注意起始位置。。 有的是从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
}
网友评论