資訊專(zhuān)欄INFORMATION COLUMN
Course Schedule I
There are a total of n courses you have to take, labeled from 0 to n - 1.拓?fù)渑判?/b> 復(fù)雜度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:
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.
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: The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
時(shí)間 O(N) 空間 O(N)
思路先修課問(wèn)題本質(zhì)上是一個(gè)有向圖，如果這個(gè)圖無(wú)環(huán)，我們可以根據(jù)拓?fù)渑判虮闅v到所有節(jié)點(diǎn)，如果有環(huán)則拓?fù)渑判驘o(wú)法完成，遍歷到的節(jié)點(diǎn)將少于總節(jié)點(diǎn)數(shù)，因?yàn)橛械墓?jié)點(diǎn)是孤島。這題我們先根據(jù)邊的關(guān)系，建一個(gè)圖，并計(jì)算每個(gè)節(jié)點(diǎn)的入度，這里用的是數(shù)組來(lái)建圖。然后從入度為0的節(jié)點(diǎn)，也就是入口開(kāi)始廣度優(yōu)先搜索，按照拓?fù)渑判虻捻樞虮闅v，最后看遍歷過(guò)的節(jié)點(diǎn)數(shù)和總節(jié)點(diǎn)數(shù)的關(guān)系就行了。拓?fù)渑判虻氖褂梅椒▍⒁?jiàn)外文字典。
代碼public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
ArrayList[] graph = new ArrayList[numCourses];
int[] indegree = new int[numCourses];
// 先初始化圖，每個(gè)賦一個(gè)空列表
for(int i = 0; i < numCourses; i++){
graph[i] = new ArrayList();
}
// 根據(jù)邊建立圖，并計(jì)算入度
for(int i = 0; i < prerequisites.length; i++){
graph[prerequisites[i][1]].add(prerequisites[i][0]);
indegree[prerequisites[i][0]]++;
}
// 找到有向圖的入口
Queue queue = new LinkedList();
for(int i = 0; i < indegree.length; i++){
if(indegree[i] == 0){
queue.add(i);
}
}
// 按照拓?fù)渑判虻捻樞颍M(jìn)行廣度優(yōu)先搜索
int cnt = 0;
while(!queue.isEmpty()){
Integer curr = queue.poll();
cnt++;
ArrayList nexts = graph[curr];
for(int i = 0; i < nexts.size(); i++){
int next = nexts.get(i);
indegree[next]--;
if(indegree[next] == 0){
queue.offer(next);
}
}
}
return cnt == numCourses;
}
}
2018/10
func canFinish(numCourses int, prerequisites [][]int) bool {
graph := make(map[int][]int)
indegree := make([]int, numCourses)
// build the graph, count the indegree for each course
for _, prerequisite := range prerequisites {
course1 := prerequisite[0]
course2 := prerequisite[1]
if graph[course2] != nil {
graph[course2] = append(graph[course2], course1)
} else {
graph[course2] = []int{course1}
}
indegree[course1]++
}
// find out those with 0 indegree as roots of the graph
var queue []int
for i, degree := range indegree {
if degree == 0 {
queue = append(queue, i)
}
}
// traverse the graph from each root, decrement the indegree for each leaf
count := 0
for len(queue) > 0 {
curr := queue[0]
queue = queue[1:]
count++
for _, course := range graph[curr] {
indegree[course]--
// once a node"s indegree is 0, it becomes a root too
if indegree[course] == 0 {
queue = append(queue, course)
}
}
}
// if all nodes have been the root before, we traversed the entire graph
return count == numCourses
}
Course Schedule II
There are a total of n courses you have to take, labeled from 0 to n - 1.拓?fù)渑判?/b> 復(fù)雜度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:
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]
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].
時(shí)間 O(N) 空間 O(N)
思路和I不同的是，這題要返回路徑。其實(shí)也沒(méi)有什么不同的，不過(guò)是多加一個(gè)數(shù)組，記錄廣度優(yōu)先搜索的遍歷順序就行了。
注意當(dāng)沒(méi)有先修課的時(shí)候，隨便返回一個(gè)順序就行了，所以初始化的時(shí)候就初始化為升序序列，方便后面直接返回。
代碼public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] res = new int[numCourses];
ArrayList[] graph = new ArrayList[numCourses];
int[] indegree = new int[numCourses];
for(int i = 0; i < prerequisites.length; i++){
if(graph[prerequisites[i][1]] == null){
graph[prerequisites[i][1]] = new ArrayList();
}
graph[prerequisites[i][1]].add(prerequisites[i][0]);
indegree[prerequisites[i][0]]++;
}
Queue queue = new LinkedList();
for(int i = 0; i < indegree.length; i++){
if(indegree[i] == 0){
queue.add(i);
}
}
// 用idx記錄輸出數(shù)組的下標(biāo)
int idx = 0;
while(!queue.isEmpty()){
Integer curr = queue.poll();
res[idx++] = curr;
if(graph[curr] == null) continue;
for(Integer next : graph[curr]){
if(--indegree[next] == 0){
queue.offer(next);
}
}
}
// 如果有環(huán)則返回空數(shù)組
return idx != numCourses ? new int[0] : res;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/64634.html
摘要：建立入度組成，把原來(lái)輸入的無(wú)規(guī)律，轉(zhuǎn)換成另一種表示圖的方法。找到為零的點(diǎn)，放到里，也就是我們圖的入口。對(duì)于它的也就是指向的。如果這些的入度也變成，也就變成了新的入口，加入到里，重復(fù)返回結(jié)果。這里題目有可能沒(méi)有預(yù)修課，可以直接上任意課程。 Some courses may have prerequisites, for example to take course 0 you have ...
Problem 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...
Problem 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 a...
Problem 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 ...
摘要：題目解答這是一個(gè)有向圖問(wèn)題，所以先建圖，然后再掃。同時(shí)記錄一共存了多少課程在里，這些課都是可以上的課。如果當(dāng)兩個(gè)點(diǎn)在同時(shí)訪(fǎng)問(wèn)的時(shí)候，那么構(gòu)成死循環(huán)，返回。掃完所有的點(diǎn)都沒(méi)問(wèn)題，才返回。這里總是忘記，當(dāng)中時(shí)，才否則繼續(xù)循環(huán) 題目：There are a total of n courses you have to take, labeled from 0 to n - 1. Some c...
閱讀 2598·2023-04-25 21:41
閱讀 1726·2021-09-22 15:17
閱讀 2015·2021-09-22 10:02
閱讀 2508·2021-09-10 11:21
閱讀 2664·2019-08-30 15:53
閱讀 1077·2019-08-30 15:44
閱讀 999·2019-08-30 13:46
閱讀 1286·2019-08-29 18:36
