lintcode615- Course Schedule- medium

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?

Example

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

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

 

算法：先求拓扑序（BFS），如果课程内部有循环依赖（也即不合法），那拓扑序里元素个数会比总元素少。以此为判据

数据结构：本题特殊，用int而非特殊对象表示课程名，所以可以直接用数组代替之前的map来表示Indegree和edges关系，直接用课程名作为数组idx来索引。

int[] indegree, List[] edges(里面每个元素都是List<Integer>), Queue<Integer> queue + Set<Integer>(BFS用)，List<Integer> order存拓扑序

细节：1.如果没有requisite，那不管多少课都true，而非仅一节课true。2.数据结构运用实现上int next = (int)edges[course].get(i);这里要强转一下，不知道为什么取出来是Object格式的 3.这题必须用int[] indegree, List[] edges来优化原来的Map结构，否则内存会爆炸。4.感受一下List[] 是足够存储边的关系的，比int[][]要更紧凑一点，去掉稀疏部分

 

public class Solution {
    /*
     * @param numCourses: a total of n courses
     * @param prerequisites: a list of prerequisite pairs
     * @return: true if can finish all courses or false
     */
     

    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // write your code here
        
        if (prerequisites == null || prerequisites.length == 0) {
            return true;
        }
        
        // indegree map
        int[] indegree = new int[numCourses];
        List[] edges = new ArrayList[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            indegree[i] = 0;
            edges[i] = new ArrayList<Integer>();
        }
        
        for (int i = 0; i < prerequisites.length; i++) {
            int c1 = prerequisites[i][0];
            int c2 = prerequisites[i][1];
            indegree[c1] ++;
            edges[c2].add(c1);
        }
        
        Queue<Integer> queue = new LinkedList<Integer>();
        Set<Integer> set = new HashSet<Integer>();
        List<Integer> order = new ArrayList<Integer>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
                set.add(i);
            }
        }
        while (!queue.isEmpty()) {
            int course = queue.poll();
            order.add(course);
            for(int i = 0; i < edges[course].size(); i++) {
                // 注意这里一定要加一个强制类型转换！edges[course].get(i)拿出来会是Object类型的，不能直接放到int容器里。
                int next = (int)edges[course].get(i);
                indegree[next] --;
                if (indegree[next] == 0) {
                    queue.offer(next);
                    set.add(next);
                }
            }
        }
        return numCourses == order.size();
    }
    
}

2.自己实现的内存爆炸的Map形式，输出正确但输入大的时候空间复杂度过高

public class Solution {
    /*
     * @param numCourses: a total of n courses
     * @param prerequisites: a list of prerequisite pairs
     * @return: true if can finish all courses or false
     */
     

    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // write your code here
        
        if (prerequisites == null || prerequisites.length == 0) {
            return true;
        }
        
        // indegree map
        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, Set<Integer>> leadMap = new HashMap<>();
        
        // req map
        for (int i = 0; i < numCourses; i++) {
            map.put(i, 0);
            leadMap.put(i, new HashSet<Integer>());
        }
        for (int i = 0; i < prerequisites.length; i++) {
            int c1 = prerequisites[i][0];
            int c2 = prerequisites[i][1];
            if (!leadMap.get(c2).contains(c1)) {
                leadMap.get(c2).add(c1);
                map.put(c1, map.get(c1) + 1);
            }
            
        }
        
        Queue<Integer> queue = new LinkedList<Integer>();
        Set<Integer> set = new HashSet<Integer>();
        List<Integer> order = new ArrayList<Integer>();
        for (int i = 0; i < numCourses; i++) {
            if (map.get(i) == 0) {
                queue.offer(i);
                set.add(i);
            }
        }
        while (!queue.isEmpty()) {
            int course = queue.poll();
            order.add(course);
            for (int next : leadMap.get(course)) {
                map.put(next, map.get(next) - 1);
                if (map.get(next) == 0) {
                    queue.offer(next);
                    set.add(next);
                }
            }
        }
        return numCourses == order.size();
    }
    
}