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.
A:
就是top logical sort (CLIS上的经典代码)
class Solution { public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { vector<int> status(numCourses, 0);// 0 as no-visited, 1 as visiting, 2 visited vector<vector<int>> A(numCourses, vector<int>()); for(auto M : prerequisites) A[M[0]].push_back(M[1]); for(int i =0;i<numCourses;++i) if(status[i]==0 && not dfs(A, status, i)) return false; return true; } private: bool dfs( vector<vector<int>>& A, vector<int>& S, int i) { S[i]=1;//gray out the color for(auto k : A[i]) { if(S[k]==1) return false; if(S[k]==0 && not dfs(A,S, k)) return false; } S[i]=2; // mark it black return true; } };
-------------old---------每次traversal的同时,还可以在限制条件里 删去已经满足的课程 ----------
public class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { Set<Integer> set = new HashSet(); Map<Integer, List<Integer>> map = new HashMap(); for(int i =0; i<numCourses; i++) // initialize map.put(i,new LinkedList<Integer>()); for(int j =0; j<prerequisites.length;j++) // build the set map.get(prerequisites[j][0]).add(prerequisites[j][1]); boolean foundOne = true; while( !map.isEmpty() && foundOne){ foundOne = false; for(int key : map.keySet()){ boolean allTaken = true; List constrainList = map.get(key); for(int k = 0;k< constrainList.size();k++) // k is the constrain class if( !set.contains(constrainList.get(k))){ // get the pre-requirement for class key allTaken = false; break; }else{ // this constrain class (k) is already found constrainList.remove(k); // delete this constrains k--; } if(allTaken){ foundOne = true; set.add(key); map.remove(key); break; } } } return map.isEmpty(); } }注意,这里,最后一个break没有加的时候,仍然会超时。
Mistakes:
1: 当 input 为1 [] 的时候, 陷入了死循环。 原因在于忘记找到可以先上的课后,把它放到set里的同时, 还要 map.remove()了
2: 第一遍解法的时候,如果 最后一个break没有加的时候,仍然会超时。 按理说不应该呀???
No comments:
Post a Comment