207. 课程表

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个课程，全部都要完成。因此课程的数量是无关的。需要考虑的是前置的限制之间是否冲突。前置的限制冲突，指的有向图的路径形成了环。

获得所有前置条件的序号
如果前置不为空
选取第一个条件
将第一个条件加入路径
在序号中删除该序号
不断地查找路径的前置顶点，如果该顶点以存在于路径，则为环，返回假
1. 否则将该点插入到路径的头
2. 继续查找前置顶点，直到没有前置顶点
不断地查找路径的后置顶点，如果该顶点以存在于路径，则为环，返回假
1. 否则将该顶点添加到路径的尾
2. 继续查找后置顶点，直到没有后置顶点

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]]))

上面的代码虽然通过了提交，但是算法其实存在问题。

bad_solution

示例：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. 找到之后。顶点数增加1。移除该顶点。以及该顶点与其它顶点的连线。
2. 回到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

肇鑫的技术博客

业精于勤，荒于嬉

错误的解答

正确的解答

相关