未分類

Course Schedule

BreadthFirstSearch, DepthFirstSearch, Go, Graph, LeetCode, TopologicalSort

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就可當作基本課程來處理，最後只要判斷修課數與總課程數是否相同即可，至於那些互斥的課程(彼此為前置)則會因為所有的基本課程都完成仍無法修課而被略過，導致修課數無法到達總課程數而判斷無法完成整個課表。

分享到