LeetCode 207. Course Schedule
Problem
LeetCode 207. Course Schedule
1. 题目简述
一共有n门课程需要修，分别是从0到n-1。有些课程需要进行先修课程，我们以数组的形式给出，例如：[0, 1]，就是说如果要修课，必须要上过1课。
现在给出numCourses门课程，和一个prerequisites数组，问是否能有一种修课方式，能够使得孙俪修完n门课程。
2. 算法思路
参考解法：花花酱LeetCode
也是一道经典老题目了，拓扑排序的经典问题，这里这道题我们使用BFS，下面这道类似的题目我们来使用DFS，体会一下差别。。LeetCode 210. Course Schedule II
BFS
其实所谓的prerequesites数组就是一个有向图，我们需要做的是在这个有向图中寻找是否存在环，如果存在环，则说明不可能存在一个拓扑排序；如果不存在环，则说明存在拓扑排序。
那么我们如何去查找环呢？两种做法，DFS和BFS，这里我们使用BFS吧。
BFS寻找拓扑排序的思路如下：
1. 统计整张图所有vertex的入度（indegree）；
2. 找出入度为0的点，放入一个queue或者stack中，无所谓；
3. pop或者poll出一个节点作为当前节点，然后将该节点所指向的节点的入度更改，然后将新的入度为0的顶点添加到栈顶或者队列后；
4. 重复2和3的操作，直至stack或者queue为空，如果已经遍历完所有节点，那么我们pop的顺序就是一种拓扑序。
这里只是找是否存在，所以没必要存当前的拓扑序，代码如下：
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
|
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
ArrayList<Integer>[] graph = new ArrayList[numCourses];
for (int i = 0; i < graph.length; i++) {
graph[i] = new ArrayList();
}
int[] indegree = new int[numCourses];
for (int[] prerequisite: prerequisites) {
indegree[prerequisite[0]]++;
graph[prerequisite[1]].add(prerequisite[0]);
}
Queue<Integer> zeroIndegrees = new LinkedList();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
zeroIndegrees.add(i);
}
}
List<Integer> topoSort = new ArrayList();
while (!zeroIndegrees.isEmpty()) {
int temp = zeroIndegrees.poll();
topoSort.add(temp);
for (int vertex : graph[temp]) {
indegree[vertex]--;
if (indegree[vertex] == 0) {
zeroIndegrees.add(vertex);
}
}
}
return (topoSort.size() == numCourses);
}
}
|
DFS
对于DFS而言，其实也有多种DFS的方式，例如 DFS + 回溯，我们可以每次从不同节点开始访问，每个节点有两种状态，访问和未访问。然后从0到n-1进行DFS遍历，每次退出的时候将节点重置为false。为什么要这样做呢？因为如果我们不将其重置为false，DFS到某节点若是已访问的状态，我们不知道它是在当前DFS的访问路径中还是说已经完全访问完毕的状态，这样做会导致大量的重复计算，如下实例，可以自行画图查看一下。
n = 4
prerequisites = [[1, 0], [1, 3], [2, 1]]
时间复杂度：O(E+ V^2)；E是构建图的时间，V ^ 2是因为最坏情况下是一条线性的课程依赖关系，所以最坏是V ^ 2的复杂度。
空间复杂度：O(V+ E)；构建图是O(V + E)，isVisited变量是O(V)，最坏情况下我们需要调用V层栈来储存我们递归函数，因此整体是O(3V + E)，也就是O(v + E)。
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
| class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
ArrayList<Integer>[] graph = new ArrayList[numCourses];
boolean[] isVisited = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList();
}
for (int[] prerequisite: prerequisites) {
graph[prerequisite[1]].add(prerequisite[0]);
}
for (int i = 0; i < numCourses; i++) {
if (backtrack(graph, isVisited, i)) {
return false;
}
}
return true;
}
private boolean backtrack(ArrayList<Integer>[] graph, boolean[] isVisited, int vertex) {
if (isVisited[vertex]) {
return true;
} else {
isVisited[vertex] = true;
for (int next : graph[vertex]) {
if (backtrack(graph, isVisited, next)) {
return true;
}
}
isVisited[vertex] = false;
return false;
}
}
}
|
DFS优化
看到上面的解，我们发现会有很多重复的计算，我们真的需要通过回溯来重置状态么？其实并不是这样，只要我们加一个visiting的状态即可，和unvisited分开，如果发现访问的节点是visiting状态，则说明有环，退出；若是visited，说明完全没问题，当前节点记录后直接返回；unvisited的话就正常DFS，将节点设为visiting再继续。最终结束的时候将此节点设为visited。
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
| class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
ArrayList<Integer>[] graph = new ArrayList[numCourses];
int[] isVisited = new int[numCourses];
Arrays.fill(isVisited, -1);
for (int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList();
}
for (int[] prerequisite: prerequisites) {
graph[prerequisite[1]].add(prerequisite[0]);
}
for (int i = 0; i < numCourses; i++) {
if (dfs(graph, isVisited, i)) {
return false;
}
}
return true;
}
private boolean dfs(ArrayList<Integer>[] graph, int[] isVisited, int vertex) {
if (isVisited[vertex] == 1) {
return false;
} else if (isVisited[vertex] == 0) {
return true;
} else {
isVisited[vertex] = 0;
for (int next : graph[vertex]) {
if (dfs(graph, isVisited, next)) {
return true;
}
}
isVisited[vertex] = 1;
return false;
}
}
}
|
