拓扑排序
拓扑排序适合于求解相关联的依赖状态,比如0依赖于1,2; 2 依赖于3
这样就类似于BFS的模版,用一个queue来维持;然后把各个链接用图的形式连接起来,从入度为0的点开始,遍历每一个字节点也就是每一个出度;同时对应的入度-1, 如果对应的节点入度为0,证明该节点的依赖关系已经被计算过,从而加入Queue进行下一步操作
题目
模版
1 | outdegree = [[] for _ in range(numCourses)] |
207. Course Schedule
1 | class Solution(object): |
210. Course Schedule II
区别就是输出list
1 | class Solution(object): |
802. Find Eventual Safe States
也是一道可以用这种方法做的题,就是经过拓扑排序后出度为0的点输出出来就好。
1 | class Solution(object): |
444. Sequence Reconstruction
这道题有两个点,一个是入度为0的只能有一个;二是如何控制只有一个数字的list-虽说对结果没啥影响,不过还要处理这么一个case[1],[[1],[1],[1]] 挺无聊的
1 | class Solution(object): |
269. Alien Dictionary
Hard 难度,一方面是构建dictionary的时候很繁琐.
每次判断完后要del掉outdegree所对应pop出来的元素,直到没有出度,也就是全部遍历完了才成功。因为order的长度没有给出,所以不能用len(order) == len(origin) 来判断
1 | class Solution(object): |