课程表II

题目描述

https://leetcode.cn/problems/course-schedule-ii

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前必须先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回任意一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3：

输入：numCourses = 1, prerequisites = []
输出：[0]

提示：

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
所有[ai, bi] 互不相同

思路：哈希表缓存依赖关系

将没有前置课程的课程先拿出来，一次加入列表，在加入的过程中，更新剩余需求这个课程的课程，删除依赖条件。使用哈希表，有环的情况未能判断。

csharp

public class Solution {

	Dictionary<int,IList<int>> dict = new Dictionary<int,IList<int>>();

    public int[] FindOrder(int numCourses, int[][] prerequisites) {    
    	//初始化课程列表
    	for(int i=0;i<numCourses;i++){
    		dict.Add(i,new List<int>());
    	}
    	//加入依赖
    	for(int i=0; i<prerequisites.Length; i++){
    		dict[prerequisites[i][0]].Add(prerequisites[i][1]);
    	}
    	List<int> result = new List<int>();
        //debug
     //    for(int i=0;i<numCourses;i++){
    	// 	Console.WriteLine("dict[{0}] count={1}",i,dict[i].Count);
    	// }

    	while(dict.Count > 0){
            int readyCount = 0;
    		foreach(int key in dict.Keys){
    			//删除没有依赖的
    			if(dict[key].Count == 0){
    				result.Add(key);
    				dict.Remove(key);

                    //删除其他对key有依赖的
                    foreach(int key2 in dict.Keys){
                        if(dict[key2].Contains(key)){
                            dict[key2].Remove(key);	
                        }
                    }
                    readyCount++;
    			}
    		}

            if(readyCount == 0){ //如果key存在，没有无依赖的课程，说明有环
                break;
            }
    	}

    	if(result.Count != numCourses){ //如果所有课程没有全学完，说明不符合题意，输出空数组
    		result = new List<int>();
    	}

    	return result.ToArray();

    }
}

思路：拓扑排序 BFS

将课程按照依赖组织好，然后一次从依赖为0的课程还是学习，学习的过程中，消除其他课程的依赖。当发现其他课程依赖为0的时候，加入queue继续学习。
直到结束，看是否学完整个课程。

csharp

public class Solution {
    //思路：将依赖课程整理，从依赖为0的课程开始学习,学习之后消除其他课程的依赖
    public int[] FindOrder(int numCourses, int[][] prerequisites) {
        List<IList<int>> edges = new List<IList<int>>();
        //创建课程依赖的容器
        for(int i=0; i<numCourses; i++){
            edges.Add(new List<int>());
        }
        for(int i=0; i<prerequisites.Length; i++){
            edges[prerequisites[i][0]].Add(prerequisites[i][1]);
        }
        //遍历取得依赖为0的课程
        List<int> result = new List<int>();
        Queue<int> queue = new Queue<int>();
        for(int i=0; i<edges.Count; i++){
            if(edges[i].Count == 0){
                queue.Enqueue(i);
            }
        }
        //展开
        while(queue.Count > 0){
            int index = queue.Dequeue();
            result.Add(index);
            //消除其他课程的依赖
            for(int i=0; i<edges.Count; i++){
                if(edges[i].Contains(index)){
                    edges[i].Remove(index);
                    if(edges[i].Count == 0){
                        queue.Enqueue(i);
                    }
                }
            }
        }
        //判断是否学习完
        if(result.Count == numCourses){
            return result.ToArray();
        }
        else{
            return new int[]{};
        }
    }
}

课程表II #

题目描述 #

思路：哈希表缓存依赖关系 #

思路：拓扑排序 BFS #

课程表II

题目描述

思路：哈希表缓存依赖关系

思路：拓扑排序 BFS