207. Course Schedule

Nino 發(fā)布于2019-08-14 14:17 / 1653人閱讀

摘要：題目解答這是一個(gè)有向圖問題，所以先建圖，然后再掃。同時(shí)記錄一共存了多少課程在里，這些課都是可以上的課。如果當(dāng)兩個(gè)點(diǎn)在同時(shí)訪問的時(shí)候，那么構(gòu)成死循環(huán)，返回。掃完所有的點(diǎ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 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.

解答：
這是一個(gè)有向圖問題，所以先建圖，然后再掃。
BFS:
每一層都是找出當(dāng)前不需要prerequisite的課程，即等級(jí)為0的課程，當(dāng)掃到這門課里，把其他需要這門課作為prerequisite的課降一個(gè)等級(jí)，直到其等級(jí)為0時(shí)，把它存到queue中作為其他課程可用的prerequisite課。同時(shí)記錄一共存了多少課程在queue里，這些課都是可以上的課。

public boolean canFinish(int numCourses, int[][] prerequisites) {
    if (numCourses <= 1) return true;
    if (prerequisites.length == 0 || prerequisites[0].length == 0) return true;
    
    ArrayList[] graph = new ArrayList[numCourses];
    int[] degree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) {
        graph[i] = new ArrayList();
    }
    for (int[] course : prerequisites) {
        degree[course[1]]++;
        graph[course[0]].add(course[1]);
    }
    
    //BFS
    Queue q = new LinkedList<>();
    int courseRemaining = numCourses;
    for (int i = 0; i < numCourses; i++) {
        if (degree[i] == 0) {
            q.offer(i);
            courseRemaining--;
        }
    }
    //Search one and get rid of this one for the all
    while(!q.isEmpty()) {
        int key = q.poll();
        for (int i = 0; i < graph[key].size(); i++) {
            int course = (int)graph[key].get(i);
            degree[course]--;
            if (degree[course] == 0) {
                q.offer(course);
                courseRemaining--;
            }
        }
    }
    
    return courseRemaining == 0;
}

DFS:
這里把每個(gè)點(diǎn)分三種狀態(tài)：0-沒訪問，1-正在訪問，2-訪問結(jié)束。每一個(gè)點(diǎn)都掃透了，確定這個(gè)點(diǎn)跟其他點(diǎn)不會(huì)構(gòu)成deadlock，那么把這個(gè)點(diǎn)跟其所有的子結(jié)都標(biāo)成2-訪問結(jié)束。如果當(dāng)兩個(gè)點(diǎn)在同時(shí)訪問的時(shí)候，那么構(gòu)成死循環(huán)，返回false。掃完所有的點(diǎn)都沒問題，才返回true。

public boolean DFS(ArrayList[] graph, int course, int[] visited) {
    //set 0 as not visited, 1 as visiting, 2 as visited
    visited[course] = 1;
    for (int i = 0; i < graph[course].size(); i++) {
        int curtCourse = (int)graph[course].get(i);
        if (visited[curtCourse] == 1) { //if curtCourse is visiting as well, it"s a circle
            return false;
        } else if (visited[curtCourse] == 0) { //if curtCourse hasn"t visited yet, go and visit
            visited[curtCourse] = 1;
            //這里總是忘記，當(dāng)dfs中case return false時(shí)，才return false, 否則繼續(xù)循環(huán)
            if(!DFS(graph, curtCourse, visited)) {
                return false;
            }
        }
    }
    visited[course] = 2;
    return true;
}

public boolean canFinish(int numCourses, int[][] prerequisites) {
    if (numCourses <= 1) return true;
    if (prerequisites.length == 0 || prerequisites[0].length == 0) return true;
    
    ArrayList[] graph = new ArrayList[numCourses];
    for (int i = 0; i < numCourses; i++) {
        graph[i] = new ArrayList();
    }
    for (int[] course : prerequisites) {
        graph[course[0]].add(course[1]);
    }
    //DFS
    int[] visited = new int[numCourses];
    for (int i = 0; i < numCourses; i++) {
        if (visited[i] == 2) continue;
        if (!DFS(graph, i, visited)) {
            return false;
        }
    }
    return true;
}