210. Course Schedule II

和上一题没啥区别，只不过要记录顺序。

一开始Queue里的是out degree是0 的，从哪个开始都一样，也可以一下子都拿出来。

以后每找到一个，就加到RES里，最后看情况返还就行了。。

public int[] findOrder(int numCourses, int[][] prerequisites){

		int[] map = new int[numCourses];
		int[] res = new int[numCourses];
		int num = 0;


		for(int n = 0;n < prerequisites.length;n++){
			map[prerequisites[n][0]]++;
		}

		Queue<Integer> myQue = new LinkedList<Integer>();

		for(int n = 0; n < map.length;n++){
			if(map[n] == 0){
				myQue.add(n);
				res[num++] = n;

			}
		}

		while(!myQue.isEmpty()){
			int temp = myQue.poll();
			for(int n = 0; n < prerequisites.length;n++){
				if(temp == prerequisites[n][1]){
					map[prerequisites[n][0]]--;
					if(map[prerequisites[n][0]] == 0){
						myQue.add(prerequisites[n][0]);
						res[num++] = prerequisites[n][0];
					}
				}
			}	
		}

		if(num == numCourses) return res;
		else return new int[0];
	}

---

---

---

二刷。

跟另一道完全一样的。。
实际上用map<Integer,List>比较好，int[]省事，但是必须保证课号跟课程数量完全一致。。

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) 
    {
        int[] res = new int[numCourses];
        
        int[] courses = new int[numCourses];
        
        for(int[] i: prerequisites) courses[i[0]]++;
    
        
        Queue<Integer> q = new LinkedList<Integer>();
    
        int index = 0;
        for(int i = 0; i < courses.length;i++)
        {
            if(courses[i] == 0)
            {
                q.add(i);
                res[index++] = i;
            }
            
        }
        

        
        while(!q.isEmpty())
        {
            int tempCourse = q.poll();
            for(int i = 0; i < prerequisites.length;i++)
            {
                if(prerequisites[i][1] == tempCourse)
                {
                    courses[prerequisites[i][0]]--;
                    if(courses[prerequisites[i][0]] == 0)
                    {
                        q.add(prerequisites[i][0]);
                        res[index++] = prerequisites[i][0];
                    }
                    
                }
            }
        }
        
        if(index == numCourses) return res;
        else return new int[0];
        
        
        
    }
}

---

---

---

三刷。

还是拓扑排序，找环，通过in-degree和out-degree.

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res = new int[numCourses];
        int[] pre = new int[numCourses];
        
        for (int[] pair: prerequisites) {
            pre[pair[0]]++;
        }
        
        Queue<Integer> q = new LinkedList<>();
        int index = 0;
        for (int i = 0; i < numCourses; i++) {
            if (pre[i] == 0) {
                q.offer(i);
                res[index++] = i;
            }
        }
        
        while (!q.isEmpty()) {
            int temp = q.poll();
            for (int[] pair: prerequisites) {
                if (pair[1] == temp) {
                    if (--pre[pair[0]] == 0) {
                        q.offer(pair[0]);
                        res[index++] = pair[0];
                    }
                }
            }
        }
        
        if (index == numCourses) {
            return res;
        } else {
            return new int[0];
        }
    }
}

据说Amazon有类似的题，要用MAP，那用MAP试一下。int[]属于比较投机取巧的办法，正规情况课号应该是个别的类。

With map:

似乎麻烦一点。。要把所有课都先加到MAP里。

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res = new int[numCourses];
        
        // courseID,# of in-degrees
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            map.put(i, 0);
        }
        for (int[] pair: prerequisites) {
            map.put(pair[0],map.get(pair[0]) + 1);
        }
        
        Queue<Integer> q = new LinkedList<>();
        int index = 0;
        for (int i = 0; i < numCourses; i++) {
            if (map.get(i) == 0) {
                q.offer(i);
                res[index++] = i;
            }
        }
        
        while (!q.isEmpty()) {
            int temp = q.poll();
            for (int[] pair: prerequisites) {
                if (pair[1] == temp) {
                    map.put(pair[0], map.get(pair[0])-1);
                    if (map.get(pair[0]) == 0) {
                        res[index++] = pair[0];
                        q.offer(pair[0]);
                    }
                }
            }
        }
        
        if (index == numCourses) {
            return res;
        } else {
            return new int[0];
        }
    }
}