首页 > 代码库 > LeetCode-Course Schedule
LeetCode-Course Schedule
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.
click to show more hints.
Solution:
1 public class Solution { 2 public boolean canFinish(int numCourses, int[][] prerequisites) { 3 if (numCourses <= 1) 4 return true; 5 6 int[] visited = new int[numCourses]; 7 HashMap<Integer, List<Integer>> childMap = new HashMap<Integer, List<Integer>>(); 8 for (int[] pair : prerequisites) { 9 int course1 = pair[0], course2 = pair[1];10 if (childMap.containsKey(course1)) {11 childMap.get(course1).add(course2);12 } else {13 List<Integer> childList = new ArrayList<Integer>();14 childList.add(course2);15 childMap.put(course1, childList);16 }17 }18 19 20 for (int i=0;i<numCourses;i++)21 if (visited[i]==0){22 if (!traverse(visited,i,childMap)) return false;23 }24 25 return true;26 }27 28 public boolean traverse(int[] visited, int curNode, HashMap<Integer,List<Integer>> childMap){29 visited[curNode] = 1;30 if (childMap.containsKey(curNode)){31 List<Integer> childs = childMap.get(curNode);32 for (int child : childs){33 if (visited[child]==1) return false;34 if (visited[child]==2) continue;35 if (!traverse(visited,child,childMap)) return false;36 }37 }38 visited[curNode] = 2;39 return true;40 }41 42 }
LeetCode-Course Schedule