There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: 2, [[1,0]]
Output: true
Explanation:
There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: 2, [[1,0],[0,1]]
Output: false
Explanation:
There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
- The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
- You may assume that there are no duplicate edges in the input prerequisites.
错误的解答
因为是n个课程，全部都要完成。因此课程的数量是无关的。需要考虑的是前置的限制之间是否冲突。前置的限制冲突，指的有向图的路径形成了环。
- 获得所有前置条件的序号
- 如果前置不为空
- 选取第一个条件
- 将第一个条件加入路径
- 在序号中删除该序号
- 不断地查找路径的前置顶点，如果该顶点以存在于路径，则为环，返回假
- 否则将该点插入到路径的头
- 继续查找前置顶点，直到没有前置顶点
- 不断地查找路径的后置顶点，如果该顶点以存在于路径，则为环，返回假
- 否则将该顶点添加到路径的尾
- 继续查找后置顶点，直到没有后置顶点
class Solution {
func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
var availableIndexes = (0..<prerequisites.count).map {$0}
while !availableIndexes.isEmpty {
var path = [Int]()
let pre = prerequisites[availableIndexes[0]]
path.append(contentsOf: pre.reversed())
availableIndexes.removeFirst()
while let from = prePre(path, prerequisites: prerequisites, from: &availableIndexes) {
guard !path.contains(from) else {
// 如果前置条件成环，则整条路径不可用，因为缺乏前置条件
return false
}
path.insert(from, at: 0)
}
while let to = postPre(path, prerequisites: prerequisites, from: &availableIndexes) {
guard !path.contains(to) else {
// 如果后续为环，则之前的to对应值的顶点到路径末尾的内容不可用
return false
}
path.append(to)
}
}
return true
}
func prePre(_ path:[Int], prerequisites: [[Int]], from availableIndexes:inout [Int]) -> Int? {
let from = path[0]
for i in 0..<availableIndexes.count {
let a = availableIndexes[i]
let p = prerequisites[a]
if p[0] == from {
availableIndexes.remove(at: i)
return p[1]
}
}
return nil
}
func postPre(_ path:[Int], prerequisites: [[Int]], from availableIndexes:inout [Int]) -> Int? {
let to = path.last!
for i in 0..<availableIndexes.count {
let a = availableIndexes[i]
let p = prerequisites[a]
if to == p[1] {
availableIndexes.remove(at: i)
return p[0]
}
}
return nil
}
}
let s = Solution()
print(s.canFinish(3, [[1,0],[2,0],[0,2]]))
上面的代码虽然通过了提交，但是算法其实存在问题。
示例：5, [[1,0],[2,1],[3,2],[1,4],[4,2]]。图见上图，存在一个环。但是由于选取时，选择不是全部的向上顶点或向下顶点，而只是第一组，造成了环并没有被解析到的现象。算法会先获得路径[0,1,2,3],然后获得[1,4,2]。完美避开了环[1,2,4,1]。
要想解决这个问题，就不能只取一条一个向上顶点或向下顶点，而应该全部获取。
正确的解答
正确的解答使用的邻近链表的方法。(^表示无后继）
| 顶点Vertex | 入度InDegree | 出度链表OutDegree LinkedList |
|---|---|---|
| 0 | 0 | -> 1^ |
| 1 | 2 | -> 2 -> 4^ |
| 2 | 1 | -> 3 -> 4^ |
| 3 | 1 | ^ |
| 4 | 1 | -> 1^ |
- 从
numCourses生成最初的邻近链表。初始化顶点数为0。 - 根据限制条件
prerequisites设定邻近链表的属性 - 寻找临近链表的最初顶点，最初顶点即不依赖任何其它顶点的点。也就是入度为0的顶点。
- 找到之后。顶点数增加1。移除该顶点。以及该顶点与其它顶点的连线。
- 回到3
- 查看顶点数是否与
numCourses相当，如果不等，就是遇到了环，无法完成课表。
class Solution {
func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
var vertexNumber = 0
var vertices:Array<Vertex> = (0..<numCourses).map {
Vertex(value: $0, inDegree: 0, link: nil)
}
prerequisites.forEach { pre in
let to = pre[0]
let from = pre[1]
vertices[to].inDegree += 1
if let link = vertices[from].link {
link.append(LinkList(value: to))
} else {
vertices[from].link = LinkList(value: to)
}
}
while let vertex = getZeroInDegreeVertex(vertices) {
// print(vertex.value)
vertexNumber += 1
vertex.inDegree = -1
var link = vertex.link
while link != nil {
vertices[link!.value].inDegree -= 1
link = link?.next
}
}
return vertexNumber == numCourses
}
func getZeroInDegreeVertex(_ vertices:[Vertex]) -> Vertex? {
for v in vertices {
if v.inDegree == 0 {
return v
}
}
return nil
}
}
class Vertex {
let value:Int
var inDegree:Int
var link:LinkList<Int>? = nil
init(value:Int, inDegree:Int, link:LinkList<Int>?) {
self.value = value
self.inDegree = inDegree
self.link = link
}
}
class LinkList<T> {
let value:T
var next:LinkList<T>? = nil
init(value:T) {
self.value = value
}
func append(_ link:LinkList<T>) {
if self.next == nil {
self.next = link
} else {
var l = self.next
while l?.next != nil {
l = l?.next
}
l?.next = link
}
}
}
let s = Solution()
//print(s.canFinish(5, [[1,0],[2,1],[3,2],[1,4],[4,2]])) // false
print(s.canFinish(5, [[1,0],[2,1],[3,2],[4,1],[2,4]])) // true
//print(s.canFinish(2, [[1,0]])) // true
//print(s.canFinish(2, [[1,0],[0,1]])) // false
相关
asdfa
