未分類

Course Schedule

Course Schedule

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?

For example:

1
2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

1
2, [[1,0],[0,1]]

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:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

  2. You may assume that there are no duplicate edges in the input prerequisites.

提示 解題應用
Graph 相鄰表製作

Default:

1
2
3
func canFinish(numCourses int, prerequisites [][]int) bool {
}

解答思路:

如果資料之間彼此的關係不僅僅只有上到下,也有可能出現下到上的情況甚至有一對多關係的時候,此時就不是Tree或LinkedList能表示,而是要用Graph(圖)像是本題的課程與擋修課程的關係,也就是說像在大學有些課程會被擋修,除非你完成前置的基本課程才能去修那門課,少數幾門課甚至有二個以上的前置要完成,要判斷是否能順利修完全數課程,只要先利用整理好的圖表得知課程的關係,並計算各個課程共有多少門前置課程,從無前置的基本課程開始先修,每當發現某課程的前置課程完成就將其前置課程的總數-1,直到該課程的前置數為0就可當作基本課程來處理,最後只要判斷修課數與總課程數是否相同即可,至於那些互斥的課程(彼此為前置)則會因為所有的基本課程都完成仍無法修課而被略過,導致修課數無法到達總課程數而判斷無法完成整個課表。

程式碼解說:

利用圖(Graph以二元陣列儲存)來表示課程與擋修課程的關係,因此一開始就初始化一個二元陣列來儲存所有的關係,接著還需要一個陣列來儲存各個課程共有多少前置課程,前置作業準備好就開始遍歷課程與擋修課程的關係,每次取出一個關係就將課程作為x軸,前置課程作為y軸來當作座標,在二元陣列對應的位置以1作為值表示其關係,並同時計算該課程有多少門前置課程再以另一陣列做統計

1
2
3
4
5
6
7
8
9
10
11
12
13
var pre int
var course int
schedule := make([][]int, numCourses)
for i, _ := range schedule {
schedule[i] = make([]int, numCourses)
}
degree := make([]int, numCourses)
for _, v := range prerequisites {
course = v[0]
pre = v[1]
schedule[course][pre] = 1
degree[course]++
}

接著遍歷剛才統計每門課程有多少門前置課程的陣列,如果該門課並沒有任何的限制(前置課程為0),表示其為基本課程可以先修,因此就將其放至隊列之中待後續處理,這邊隊列是以LinkedList做表示(有用頭節點來確保操作上的一致性),所以每次放入隊列都要當作節點來新增

1
2
3
4
5
6
7
8
9
10
11
12
13
14
type Node struct {
Val int
Next *Node
}
var newNode *Node
queue := &Node{}
rear := queue
for i, v := range degree {
if v == 0 {
newNode = &Node{i, nil}
rear.Next = newNode
rear = newNode
}
}

因為隊列的第一個節點是頭節點而非課程的資料,所以要先將隊列移到下一個節點才開始一一取出處理,如果隊列取出的節點存在,就將已修課程數+1,並將此課程當作前置課程帶入先前整理好的二元陣列課程關係,檢查是否有其它課程是以此課程作為前置課程,如果又剛好其為前置課程之一就將先前統計的前置課程總數-1,而如果發現前置課程總數變為0,該課程就可當作基本課程來處理放入隊列之中,最後待隊列的課程資料全數取出(表示能夠修的課都修完了),此時再檢查修課數與總課程數是否相同即可知道能否完成整個課表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var take int
queue = queue.Next
for queue != nil {
pre = queue.Val
take++
for course := 0; course < numCourses; course++ {
if schedule[course][pre] == 1 {
schedule[course][pre] = 0
degree[course]--
if degree[course] == 0 {
newNode = &Node{course, nil}
rear.Next = newNode
rear = newNode
}
}
}
queue = queue.Next
}
return take == numCourses

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
type Node struct {
Val int
Next *Node
}
func canFinish(numCourses int, prerequisites [][]int) bool {
var take int
var pre int
var course int
var newNode *Node
queue := &Node{}
rear := queue
schedule := make([][]int, numCourses)
degree := make([]int, numCourses)
for i, _ := range schedule {
schedule[i] = make([]int, numCourses)
}
for _, v := range prerequisites {
course = v[0]
pre = v[1]
schedule[course][pre] = 1
degree[course]++
}
for i, v := range degree {
if v == 0 {
newNode = &Node{i, nil}
rear.Next = newNode
rear = newNode
}
}
queue = queue.Next
for queue != nil {
pre = queue.Val
take++
for course := 0; course < numCourses; course++ {
if schedule[course][pre] == 1 {
schedule[course][pre] = 0
degree[course]--
if degree[course] == 0 {
newNode = &Node{course, nil}
rear.Next = newNode
rear = newNode
}
}
}
queue = queue.Next
}
return take == numCourses
}

總結:

有一課表包含n個課程,而部分課程之間存在著擋修的機制,要判斷是否能修完整個課表,只要先將課程與擋修課程的關係整理成一份圖表,並計算各個課程共有多少門前置課程,接著從無前置的基本課程開始先修,每當發現某課程的前置課程完成就將其前置課程的總數-1,直到該課程的前置數為0就可當作基本課程來處理,最後只要判斷修課數與總課程數是否相同即可,至於那些互斥的課程(彼此為前置)則會因為所有的基本課程都完成仍無法修課而被略過,導致修課數無法到達總課程數而判斷無法完成整個課表。

分享到