题意分解-

本题是计算是否会出现无法学习的课程这种课程的特点是前置课程出现环路比如A课程的前置课程B的前置课程为A课程本题必须进行课程遍历每个课程都需要检测是否出现环路基本的设计思路是循环递归循环遍历课程递归检测环路

优化思路

如果一个课程已经检测没有出现环路则前置课程检测到此课程就不用继续检测下去减少计算量

测量工具

本地化测试说明LeetCode网站测试运行时数据波动很大【可把页面视为功能测试】因此需要本地化测试解决数据波动问题CheckFuncPerf本地化函数用时和内存占用测试模块已上传到CSDN地址Python算法题集_检测函数用时和内存占用的模块本题超时测试用例较难生成已经保存为文本文件本次测试结果详见章节【最优算法】测试用例文件包含在【相关资源】中

代码展开

prerequisites:list_graph[a].append(b)def

pres):if

enumerate(list_graph))print(fprerequisites

count

cfp.getTimeMemoryStr(Solution.canFinish_base,

aSolution,

prerequisites:list_graph[a].append(b)learned

[0]

cfp.getTimeMemoryStr(Solution.canFinish_base,

aSolution,

循环遍历课程递归检测环路但是检测环路修改为从前置科目开始计算此科目的后置科目是否出现环路

import

prerequisites:list_graph[b].append(a)for

iIdx

cfp.getTimeMemoryStr(Solution.canFinish_ext2,

aSolution,

首先必须存在没有任何前置的科目否则第一门科目都没有办法学习直接返回False由此可建立没有前置科目的队列迭代没有前置科目的队列逐步剥离此科目后置科目的计数器如果后置科目的前置计数器清零则作为无前置科目放入队列迭代完毕后检测有效科目数量是否达标

import

prerequisites:deque_graph[visited].append(course)learned[course]

1queue

queue.popleft()processed_courses

1for

deque_graph[visited]:learned[course]

1if

cfp.getTimeMemoryStr(Solution.canFinish_ext3,

aSolution,

根据本地日志分析最优算法为第2种方式【循环递归缓存】canFinish_ext1

由于四段代码思路一致主要是使用的数据结构不同因此经验推出以下结论

在作为队列使用时【先进先出】deque性能远远高于list迭代器循环优于循环中进行异常检测下标循环和枚举循环性能基本一致

inumCourses

open(rtestcase/hot53_big5W.txt,

moder,

2:check_pre.append([int(tmpcurpre[0]),

int(tmpcurpre[1])])

cfp.getTimeMemoryStr(Solution.canFinish_base,

aSolution,

cfp.getTimeMemoryStr(Solution.canFinish_ext1,

aSolution,

cfp.getTimeMemoryStr(Solution.canFinish_ext2,

aSolution,

cfp.getTimeMemoryStr(Solution.canFinish_ext3,

aSolution,

本文代码已上传到CSDN地址Python算法题源代码_LeetCode(力扣)_课程表

一日练一日功一日不练十日空