[Swift]LeetCode207. 课程表 | Course Schedule_app

概述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: @H_301_6@There are a total of n courses you have to take,labeled from 0 to n-1.

@H_301_6@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]

@H_301_6@Given the total number of courses and a List of prerequisite pairs,is it possible for you to finish all courses?

@H_301_6@Example 1:

input: 2,[[1,0]] Output: trueExplanation: There are a total of 2 courses to take.              To take course 1 you should have finished course 0. So it is possible.

@H_301_6@Example 2:

input: 2,0],[0,1]]Output: falseExplanation: 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.

@H_301_6@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. @H_301_6@现在你总共有 n 门课需要选，记为 0 到 n-1。

@H_301_6@在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

@H_301_6@给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

@H_301_6@示例 1:

输入: 2,0]] 输出: true解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

@H_301_6@示例 2:

输入: 2,1]]输出: false解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成?课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

@H_301_6@说明:

输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。你可以假定输入的先决条件中没有重复的边。 @H_301_6@提示:

这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。 @H_301_6@拓扑排序也可以通过 BFS 完成。

@H_301_6@104ms

 1 class Solution { 2     func canFinish(_ numCourses: Int,_ prerequisites: [[Int]]) -> Bool { 3  4         var graph = Array(repeating: Array(repeating: 0,count: 0),count: numCourses) 5         var courses = Array(repeating: 0,count: numCourses) 6         for a in prerequisites { 7             graph[a[1]].append(a[0]) 8             courses[a[0]] += 1 9         }10         var q = [Int]()11         for (i,num) in courses.enumerated() {12             if num == 0 { q.append(i) } 13         }14         while !q.isEmpty {15             var t = q.removeLast()16             for a in graph[t]{17                 courses[a] -= 118                 if courses[a] == 0 { q.append(a)}19             }20         }21 22         for a in courses {23          //   if a != 0 { return false }24         }25         return courses.filter{ $0 != 0 }.count == 026     }27 }

@H_301_6@108ms

 1 class Solution { 2     var visited = [Bool]() 3     var onPath = [Bool]() 4     var has = false 5      6     func canFinish(_ numCourses: Int,_ prerequisites: [[Int]]) -> Bool { 7         var g = [Node]() 8         for i in strIDe(from: 0,to: numCourses,by: 1) { 9             g.append(Node(label: i,adj: [Node]()))10         }11         12         for pre in prerequisites {13             let from = pre[0]14             let to = pre[1]15             16             g[from].adj.append(g[to])17         }18         19         visited = Array(repeating: false,count: g.count) 20         onPath = Array(repeating: false,count: g.count) 21         has = false22         23         return !hasCycles(g)24     }25     26     27     func hasCycles(_ g: [Node]) -> Bool {28         if g.isEmpty {29             return true30         }31         32         for n in g {33             if !visited[n.label] && !has {34                 dfs(n)35             }36 37         }38         39         return has40     }41     42     func dfs(_ node: Node) {43         if has {44             return        45         }46         47         visited[node.label] = true48         onPath[node.label] = true49         50         for adj in node.adj {51             if !visited[adj.label] {52                 dfs(adj)53             } else {54                 if onPath[adj.label] {55                     has = true56                 }57             }58         }59         60         onPath[node.label] = false61     }62 63     class Node {64         let label: Int65         var adj: [Node]66     67         init(label: Int,adj: [Node]) {68             self.label = label69             self.adj = adj70         }71     }72 }

@H_301_6@116ms

 1 class Solution { 2     func canFinish(_ total: Int,_ nums: [[Int]]) -> Bool { 3         var dict: [Int: [Int]] = [:] 4         var prev: [Int] = Array(repeating: 0,count: total) 5         for num in nums { 6             prev[num[0]] += 1 7             dict[num[1],default: []].append(num[0]) 8         } 9         var count = 010         var queue: [Int] = []11         for (index,num) in prev.enumerated() {12             if num == 0 {13                 queue.append(index)14             }15         }16         while queue.isEmpty == false {17             let num = queue.removeFirst()18             count += 119             if let courses = dict[num] {20                 for course in courses {21                     prev[course] -= 122                     if prev[course] == 0 {23                         queue.append(course)24                     }25                 }26             }27         }28         return count == total29     }30 }

@H_301_6@116ms

 1 class Solution { 2     func canFinish(_ numCourses: Int,_ prerequisites: [[Int]]) -> Bool { 3         var graph = [[Int]](repeating: [Int](),count: numCourses) 4         var indegrees = [Int](repeating: 0,count: numCourses) 5         for prerequisite in prerequisites { 6             graph[prerequisite.last!].append(prerequisite.first!) 7             indegrees[prerequisite.first!] += 1 8         } 9         var queue = [Int]()10         for i in 0..<numCourses {11             if indegrees[i] == 0 {12                 queue.append(i)13             }14         }15         var sortednodes = [Int]()16         while !queue.isEmpty {17             let node = queue.removeFirst()18             sortednodes.append(node)19             let followingNodes = graph[node]20             for followingNode in followingNodes {21                 indegrees[followingNode] -= 122                 if indegrees[followingNode] == 0 {23                     queue.append(followingNode)24                 }25             }26         }27         return sortednodes.count == numCourses28     }29 }

@H_301_6@132ms

 1 class Solution { 2     func canFinish(_ total: Int,num) in prev.enumerated() {12             if num == 0 {13                 queue.append(index)14             }15         }16         while queue.isEmpty == false {17             let num = queue.removeFirst()18             count += 119             if let courses = dict[num] {20                 for course in courses {21                     prev[course] -= 122                     if prev[course] == 0 {23                         queue.append(course)24                     }25                 }26             }27         }28         return count == total29     }30 }

@H_301_6@160ms

 1 class linkedListNode<Element> { 2     var val: Element 3     var next: linkedListNode? 4     init(_ val: Element,_ next: linkedListNode? = nil) { 5         self.val = val 6         self.next = next 7     } 8 } 9 10 public struct linkedList<Element> {11     private var head: linkedListNode<Element>? = nil12     private var tail: linkedListNode<Element>? = nil13     14     public mutating func append(_ element: Element) {15         guard head != nil else {16             head = linkedListNode(element)17             tail = head18             return19         }20         tail?.next = linkedListNode(element)21         tail = tail?.next22     }23     24     public mutating func popFirst() -> Element? {25         let popped = head26         head = head?.next27         if head == nil {28             tail = nil29         }30         return popped?.val31     }32     33     public var first: Element? {34         return head?.val35     }36 }37 38 public struct Queue<Element> {39     private var linkedList = linkedList<Element>()40     public mutating func enqueue(_ element: Element) {41         linkedList.append(element)42     }43     44     public mutating func dequeue() -> Element? {45         return linkedList.popFirst()46     }47     48     public var isEmpty: Bool {49         return linkedList.first == nil50     }51 }52 53 54 class Solution {55     func canFinish(_ numCourses: Int,_ prerequisites: [[Int]]) -> Bool {56         var IDependOn = Array(repeating: 0,count: numCourses)57         var dependsOnMe = Array(repeating: [Int](),count: numCourses)58         for courseDependency in prerequisites {59             dependsOnMe[courseDependency[1]].append(courseDependency[0])60             IDependOn[courseDependency[0]] += 161         }62         var q = Queue<Int>()63         for i in 0..<numCourses {64             if IDependOn[i] == 0 {65                 q.enqueue(i)66             }67         }68         while !q.isEmpty {69             let next = q.dequeue()!70             for course in dependsOnMe[next] {71                 if IDependOn[course] == 1 {72                     q.enqueue(course)73                 }74                 IDependOn[course] -= 175             }76         }77         for i in 0..<numCourses {78             if IDependOn[i] > 0 {79                 return false80             }81         }82         return true83     }84 }

@H_301_6@168ms

 1 class Solution { 2     func canFinish(_ numCourses: Int,_ prerequisites: [[Int]]) -> Bool { 3         // number of dependencIEs the course has 4         var dependencIEs: [Int] = [Int](repeating: 0,count: numCourses) 5         // List of courses dependent on this course 6         var dependents: [Int: [Int]] = [:] 7          8         // create graph 9         for prereq in prerequisites {10             let dep = prereq[0]11             let course = prereq[1]12             dependencIEs[course] += 113             if dependents[dep] == nil {14                 dependents[dep] = []15             }16             dependents[dep]!.append(course)17         }18         19         var count = 020         var queue: [Int] = []21         for i in 0..<numCourses {22             if dependencIEs[i] == 0 {23                 queue.append(i)24             }25         }26         27         while !queue.isEmpty {28             let course = queue.removeFirst()29             count += 130             if let dependents = dependents[course] {31                 for dep in dependents {32                     dependencIEs[dep] -= 133                     if dependencIEs[dep] == 0 {34                         queue.append(dep)35                     }36                 }37             }38         }39         40         return count == numCourses41     }42 }

@H_301_6@212ms

 1 class Solution { 2     func canFinish(_ numCourses: Int,_ prerequisites: [[Int]]) -> Bool { 3         guard numCourses > 0 else { 4             return true 5         } 6         guard prerequisites.count > 0 else { 7             return true 8         } 9         10         var target = numCourses11         var graph = [Int:[Int]]()12         13         for p in prerequisites {14             graph[p[0]] = graph[p[0],default:[Int]()] + [p[1]]15         }16         17         var visited = [Int: Bool]()18         19         func dfs(node: Int,curVisited:[Int: Bool]) -> Bool {20             guard curVisited[node] == nil else {21                 return false22             }23             guard visited[node] == nil else {24                 return true25             }26             visited[node] = true27             var curVisited = curVisited28             curVisited[node] = true29             guard let neighbors = graph[node] else  {30                 return true31             }32             for n in neighbors {33                 if dfs(node:n,curVisited:curVisited) == false {34                     return false35                 }36             }37             return true38         }39         for i in 0..<numCourses {40             if !dfs(node: i,curVisited: [Int:Bool]()) {41                 return false42             }43         }44         return true45     }46 }

@H_301_6@1104ms

 1 class Solution { 2     func canFinish(_ numCourses: Int,_ prerequisites: [[Int]]) -> Bool { 3         var nodes = prerequisites.reduce(into: [Int: Set<Int>]()) { 4             $0[$1.first!,default: Set<Int>()].insert($1.last!) 5             if $0[$1.last!] == nil { 6                 $0[$1.last!] = Set<Int>() 7             } 8         } 9         var sortednodes = [Int](),noIncomingNodes = nodes.filter { $0.value.count == 0 }.map { $0.key }10         while !noIncomingNodes.isEmpty {11             let sortednode = noIncomingNodes.removeFirst()12             nodes.removeValue(forKey: sortednode)13             sortednodes.append(sortednode)14             for node in nodes where node.value.contains(sortednode) {15                 var prerequisite = node.value16                 prerequisite.remove(sortednode)17                 if prerequisite.isEmpty {18                     noIncomingNodes.append(node.key)19                 } else {20                     nodes[node.key] = prerequisite21                 }22             }23         }24         return nodes.count == 025     }26 }