CourseSchedule I II 课程规划 I II Java 实现

I & II 课程规划 I& II Java 实现

课程规划，也是上面的经典题型了，包含原题和衍生题一共有4道，今天我们先看看I和II吧。

当我们看到这种有前提条件的东西的时候，我们多半都可以将其化为有向图来理解，这样就可以通过图的遍历来处理这个问题了。而这一道题其实一看就知道本质就是再有向图中进行环的检测。

我们利用一个二维数组来记录有向图，然后利用一个一维数组来记录当前节点的状态，-1为有冲突，1为访问过，0为没有访问过。然后对当前的节点进行dfs，如果出现冲突则返回false，如果没有false则再最后返回true，让我们看看java的实现吧。

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {List<List<Integer>> graph = new ArrayList<>();for(int i = 0; i < numCourses;i++){graph.add(new ArrayList<>());}for(int i = 0; i < prerequisites.length;i++){int course = prerequisites[i][0];int prerequisite  = prerequisites[i][1];graph.get(course).add(prerequisite);}int[] visited = new int[numCourses];for(int i = 0; i < numCourses;i++){if(!dfs(i,graph,visited)) return false;}return true;}private boolean dfs(int curr,List<List<Integer>> graph, int[] visited){if(visited[curr] == -1)return false;if(visited[curr] == 1)return true;visited[curr] = -1;for(int next : graph.get(curr)){if(!dfs(next,graph,visited))return false;}visited[curr] = 1;return true;}
}

解决了第一题再让我们来看看第二题

第二题就是在第一题的基础上作出了衍生，在第一题中我们只需要检测在有向图中是否存在环，而第二题则需要返回有向图的一个拓扑。思路其实也是非常相似的，我们首先统计有向图中每一个节点的入度，把当前入度为0的节点放入队列中和返回的结果中，然后对栈中的每一个节点进行dfs，将其导向的节点的入度减去1，如果为0则放入队列和返回的结果中。最后查看当前的结果中的元素数是否符合我们需要返回的元素数，如果相同则返回当前结果，如果不同则返回一个空集。

class Solution {public int[] findOrder(int numCourses, int[][] prerequisites) {int len = prerequisites.length;List<List<Integer>> graph = new ArrayList<>();int[] inDegree = new int[numCourses];for(int i = 0; i < numCourses;i++){graph.add(new ArrayList<>());}for(int i = 0;i < len;i++){int course = prerequisites[i][0];int prerequisite  = prerequisites[i][1];graph.get(prerequisite).add(course);inDegree[course]++;}Queue<Integer> queue = new LinkedList<>();for(int i = 0; i < numCourses;i++){if(inDegree[i]== 0){queue.offer(i);}}int numOfResult = queue.size();int[] result = new int[numCourses];int j = 0;while(!queue.isEmpty()){int c = queue.poll();result[j++] = c;for(int i : graph.get(c)){inDegree[i]--;if(inDegree[i] == 0) queue.offer(i);}}if(j == numCourses){return result;}return new int[0];}
}

注意此处的图的建立顺序和第一题是不一样的，第一题是根据当前的课程寻找前置课程，而第二题则是根据前置课程来添加当前课程的有向图。

这样我们就可以很好的解决 的前两题了。