Course Schedule II 08/04

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, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.Have you met this question in a real interview? Yes

Example

Given n = 2, prerequisites = [[1,0]] Return [0,1]

Given n = 4, prerequisites = [1,0],[2,0],[3,1],[3,2]] Return [0,1,2,3] or [0,2,1,3]

先通过hashmap建立有向图的映射，key是先修课
，value是要上的课，那么就会形成由先修课指向要上的课的有向图，那么现在要上
的课，可以看做是他图里的邻居，有in come edge的，然后建立统计他们income
edge的map，然后做bfs。

public class Solution {
    /*
     * @param numCourses: a total of n courses
     * @param prerequisites: a list of prerequisite pairs
     * @return: the course order
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // write your code here
        int[] res = new int[numCourses];
        
        if(prerequisites == null || numCourses == 0){
            return res;
        }
        
        HashMap<Integer, List<Integer>> map = buildGraph(numCourses,prerequisites);
        
        
        HashMap<Integer,Integer> degreeMap = new HashMap<>();
        
        for(int i = 0; i < numCourses; i++){
            for(Integer n : map.get(i)){
                if(degreeMap.containsKey(n)){
                    degreeMap.put(n,degreeMap.get(n)+1);
                }else{
                    degreeMap.put(n,1);
                }
            }
        }
        
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        
        for(int i = 0; i < numCourses; i++){
            if(!degreeMap.containsKey(i)){
                queue.offer(i);
                list.add(i);
            }
        }
        
        while(!queue.isEmpty()){
            int n = queue.poll();
            for(Integer k : map.get(n)){
                degreeMap.put(k,degreeMap.get(k)-1);
                if(degreeMap.get(k) == 0){
                    queue.offer(k);
                    list.add(k);
                }
            }
        }
        
        if(list.size()!= numCourses){
            return new int[0];
        }else{
            for(int i = 0; i < list.size();++i){
                res[i] = list.get(i);
            }
            
            return res;
        }
    }
    
    public HashMap<Integer,List<Integer>> buildGraph(int numCourses,int[][] prerequisites){
        
        
        HashMap<Integer,List<Integer>> map = new HashMap<>();
        
        for (int i = 0; i < numCourses ;i++ ){
            map.put(i,new ArrayList<>());
        } 
        
        for(int i = 0; i < prerequisites.length;++i){
            int cur = prerequisites[i][0];
            int pre = prerequisites[i][1];
            map.get(pre).add(cur);
        }
        
        return map;
        
    }
}

10/23/2018二刷

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res = new int[numCourses];
        
        for(int i = 0; i < numCourses; i++){
            res[i] = i;
        }
        
        if(numCourses == 0 || prerequisites == null || prerequisites.length == 0) return res;
        
        //key: pre, value: courses as pre to be the prerequ
        Map<Integer,List<Integer>> map = buildGraph(numCourses,prerequisites);
        
        
        Map<Integer,Integer> indegree = new HashMap<>();
        
        for(int pre : map.keySet()){
            for(int cur : map.get(pre)){
                indegree.put(cur,indegree.getOrDefault(cur,0)+1);
            }
        }
        
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        
        for(int i = 0; i < numCourses; i++){
            if(!indegree.containsKey(i)){
                queue.offer(i);
                set.add(i);
            }
        }
        
        int index = 0;
        
        while(!queue.isEmpty()){
            int item = queue.poll();
            res[index++] = item;
            
            for(int nei:map.get(item)){
                indegree.put(nei,indegree.get(nei)-1);
                
                if(indegree.get(nei) == 0){
                    queue.offer(nei);
                    set.add(nei);
                }
            }
        }
        
        return set.size() == numCourses ? res : new int[0];
        
    }
    
    public Map<Integer,List<Integer>> buildGraph(int numCourses,int[][] prerequisites){
        Map<Integer,List<Integer>> map = new HashMap<>();
        
        for(int i = 0; i < numCourses; i++){
            map.put(i,new ArrayList<>());
        }
        
        for(int i = 0; i < prerequisites.length;i++ ){
            for(int j = 0; j < prerequisites[0].length; j++){
                int pre = prerequisites[i][1];
                int cur = prerequisites[i][0];
                
                map.get(pre).add(cur);
            }
        }
        
        return map;
    }
}