207. Course Schedule

Nino 发布于2019-08-14 14:17 / 1443人阅读

摘要：题目解答这是一个有向图问题，所以先建图，然后再扫。同时记录一共存了多少课程在里，这些课都是可以上的课。如果当两个点在同时访问的时候，那么构成死循环，返回。扫完所有的点都没问题，才返回。这里总是忘记，当中时，才否则继续循环

题目：
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.

解答：
这是一个有向图问题，所以先建图，然后再扫。
BFS:
每一层都是找出当前不需要prerequisite的课程，即等级为0的课程，当扫到这门课里，把其他需要这门课作为prerequisite的课降一个等级，直到其等级为0时，把它存到queue中作为其他课程可用的prerequisite课。同时记录一共存了多少课程在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:
这里把每个点分三种状态：0-没访问，1-正在访问，2-访问结束。每一个点都扫透了，确定这个点跟其他点不会构成deadlock，那么把这个点跟其所有的子结都标成2-访问结束。如果当两个点在同时访问的时候，那么构成死循环，返回false。扫完所有的点都没问题，才返回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;
            //这里总是忘记，当dfs中case return false时，才return false, 否则继续循环
            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;
}

海外云主机 GPU服务器 Course v207 Schedule node-schedule

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64924.html

[LeetCode] 207. Course Schedule

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 ...

ephererid 2019-08-15 17:47 评论0 收藏0
[Leetcode] Course Schedule 课程计划

Course Schedule I 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 e...

Amio 2019-08-14 12:40 评论0 收藏0
210. Course Schedule II

摘要：建立入度组成，把原来输入的无规律，转换成另一种表示图的方法。找到为零的点，放到里，也就是我们图的入口。对于它的也就是指向的。如果这些的入度也变成，也就变成了新的入口，加入到里，重复返回结果。这里题目有可能没有预修课，可以直接上任意课程。 Some courses may have prerequisites, for example to take course 0 you have ...

lbool 2019-08-16 10:36 评论0 收藏0
【LC总结】图、拓扑排序 (Course Schedule I, II/Alien Dictiona

Course Schedule 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, whi...

gaara 2019-08-14 15:54 评论0 收藏0
[LeetCode] 210. Course Schedule II

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...

zhkai 2019-08-19 11:12 评论0 收藏0