未分類

Course Schedule II

BreadthFirstSearch, DepthFirstSearch, Go, Graph, LeetCode, TopologicalSort

Course Schedule II

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, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

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 the correct course order is [0,1]

1
4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

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.

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

Default:

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

解答思路:

建議可以先參考先前Course Schedule的解法，解說較為詳細，基本上概念完全一樣，只是將先前題的程式碼稍做修改而已，如果能判斷是否能將課程全數修完，要列出合理的修課順序就不會太困難。

先將課程與擋修課程的關係整理成一份圖表，並計算各個課程共有多少門前置課程，接著從無前置的基本課程開始先修，每當發現某課程的前置課程完成就將其前置課程的總數-1，直到該課程的前置數為0就可當作基本課程來處理，最後只要判斷修課數與總課程數是否相同再回傳修課的順序即可。

程式碼解說:

這邊只解說與先前題目程式碼的相異之處，原本只是計算已修課程數，現在要改為修課的課程順序，所以每次從隊列取出課程時就將其值放入修課順序的陣列之中，待隊列遍歷完畢判斷修課數(修課順序的陣列長度)與總課程數是否相同，如果不同就回傳空的陣列，否則才回傳整個修課順序的陣列

1
2
3
4
5
6
7
8
9
10
11
12
...
var take []int
for queue != nil {
	pre = queue.Val
	take = append(take, pre)
	...
	queue = queue.Next
}
if len(take) != numCourses {
	return []int{}
}
return take

完整程式碼:

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
49
50
51
type Node struct {
	Val  int
	Next *Node
}
func findOrder(numCourses int, prerequisites [][]int) []int {
	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 = append(take, pre)
		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
	}
	if len(take) != numCourses {
		return []int{}
	}
	return take
}

總結:

建議可以先參考先前Course Schedule的解法，解說較為詳細，基本上概念完全一樣，先將課程與擋修課程的關係整理成一份圖表，並計算各個課程共有多少門前置課程，接著從無前置的基本課程開始先修，每當發現某課程的前置課程完成就將其前置課程的總數-1，直到該課程的前置數為0就可當作基本課程來處理，最後只要判斷修課數與總課程數是否相同再回傳修課的順序即可。

分享到