哈尔滨模板建站推荐,网站关键词百度指数,公众平台号,七彩发光字生成器Python算法题集_课程表 题207#xff1a;课程表1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【循环递归全算】2) 改进版一【循环递归缓存】3) 改进版二【循环递归缓存反向计算】4) 改进版三【迭代剥离计数器检测】 4. 最优算法5. 相关资源 本… Python算法题集_课程表 题207课程表1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【循环递归全算】2) 改进版一【循环递归缓存】3) 改进版二【循环递归缓存反向计算】4) 改进版三【迭代剥离计数器检测】 4. 最优算法5. 相关资源 本文为Python算法题集之一的代码示例
题207课程表
1. 示例说明
你这个学期必须选修 numCourses 门课程记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出其中 prerequisites[i] [ai, bi] 表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如先修课程对 [0, 1] 表示想要学习课程 0 你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习如果可以返回 true 否则返回 false 。
示例 1
输入numCourses 2, prerequisites [[1,0]]
输出true
解释总共有 2 门课程。学习课程 1 之前你需要完成课程 0 。这是可能的。示例 2
输入numCourses 2, prerequisites [[1,0],[0,1]]
输出false
解释总共有 2 门课程。学习课程 1 之前你需要先完成课程 0 并且学习课程 0 之前你还应先完成课程 1 。这是不可能的。提示
1 numCourses 20000 prerequisites.length 5000prerequisites[i].length 20 ai, bi numCoursesprerequisites[i] 中的所有课程对 互不相同 2. 题目解析
- 题意分解
本题是计算是否会出现无法学习的课程这种课程的特点是前置课程出现环路比如A课程的前置课程B的前置课程为A课程本题必须进行课程遍历每个课程都需要检测是否出现环路基本的设计思路是循环递归循环遍历课程递归检测环路
- 优化思路 通常优化减少循环层次 通常优化增加分支减少计算集 通常优化采用内置算法来提升计算速度 分析题目特点分析最优解 如果一个课程已经检测没有出现环路则前置课程检测到此课程就不用继续检测下去减少计算量 可以研究迭代法实现科目检测 - 测量工具
本地化测试说明LeetCode网站测试运行时数据波动很大【可把页面视为功能测试】因此需要本地化测试解决数据波动问题CheckFuncPerf本地化函数用时和内存占用测试模块已上传到CSDN地址Python算法题集_检测函数用时和内存占用的模块本题超时测试用例较难生成已经保存为文本文件本次测试结果详见章节【最优算法】测试用例文件包含在【相关资源】中 3. 代码展开
1) 标准求解【循环递归全算】
循环遍历课程递归检测环路能算尽算不出所料功能测试就已超时
页面功能测试未能通关超时失败
import CheckFuncPerf as cfpclass Solution:def canFinish_base(self, numCourses, prerequisites):list_graph [[] for x in range(numCourses)]for a, b in prerequisites:list_graph[a].append(b)def dfs_checkring(visited, pres):if not pres:return Trueresult Truefor course in pres:if course in visited:return Falseresult dfs_checkring(visited [course], list_graph[course])return resultreturn all(dfs_checkring([i], pres) for i, pres in enumerate(list_graph))print(fprerequisites count of the Courses {len(check_prerequisites)})
result cfp.getTimeMemoryStr(Solution.canFinish_base, aSolution, 50000, check_prerequisites)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
prerequisites count of the Courses 49999
函数 canFinish_base 的运行时间为 50813.51 ms内存使用量为 7264.00 KB 执行结果 True2) 改进版一【循环递归缓存】
循环遍历课程递归检测环路缓存已经计算的课程环路结果
页面功能测试勉强通过超过11%
import CheckFuncPerf as cfpclass Solution:def canFinish_ext1(self, numCourses: int, prerequisites):list_graph [[] for x in range(numCourses)]for a, b in prerequisites:list_graph[a].append(b)learned [0] * numCoursesdef dfs_checkring(visited, pres):if not pres:return Trueresult Truefor course in pres:if course in visited:return Falseif learned[course] 0:continuelearned[course] 1result dfs_checkring(visited [course], list_graph[course])return resultfor iIdx, pres in enumerate(list_graph):if learned[iIdx] 0:continueresult dfs_checkring([iIdx], pres)if not result:return Falselearned[iIdx] 1return Trueprint(fprerequisites count of the Courses {len(check_prerequisites)})
result cfp.getTimeMemoryStr(Solution.canFinish_base, aSolution, 50000, check_prerequisites)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
prerequisites count of the Courses 49999
函数 canFinish_ext1 的运行时间为 66.02 ms内存使用量为 6112.00 KB 执行结果 True3) 改进版二【循环递归缓存反向计算】
循环遍历课程递归检测环路但是检测环路修改为从前置科目开始计算此科目的后置科目是否出现环路
页面功能测试性能良好超过88%
import CheckFuncPerf as cfpclass Solution:def canFinish_ext2(self, numCourses, prerequisites):def dfs_checkring(iIdx, list_graph, ringflags):if ringflags[iIdx] -1:return Trueif ringflags[iIdx] 1:return Falseringflags[iIdx] 1for jIdx in list_graph[iIdx]:if not dfs_checkring(jIdx, list_graph, ringflags):return Falseringflags[iIdx] -1return Truelist_graph [[] for x in range(numCourses) ]list_flags [0 for x in range(numCourses)]for a, b in prerequisites:list_graph[b].append(a)for iIdx in range(numCourses):if not dfs_checkring(iIdx, list_graph, list_flags):return Falsereturn Trueprint(fprerequisites count of the Courses {len(check_prerequisites)})
result cfp.getTimeMemoryStr(Solution.canFinish_ext2, aSolution, 50000, check_prerequisites)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
prerequisites count of the Courses 49999
函数 canFinish_ext2 的运行时间为 80.01 ms内存使用量为 520.00 KB 执行结果 True4) 改进版三【迭代剥离计数器检测】
特殊的迭代思路
首先必须存在没有任何前置的科目否则第一门科目都没有办法学习直接返回False由此可建立没有前置科目的队列迭代没有前置科目的队列逐步剥离此科目后置科目的计数器如果后置科目的前置计数器清零则作为无前置科目放入队列迭代完毕后检测有效科目数量是否达标
页面功能测试马马虎虎超过55%
import CheckFuncPerf as cfpclass Solution:def canFinish_ext3(self, numCourses, prerequisites):from collections import deque, defaultdictdeque_graph defaultdict(list)learned [0] * numCoursesfor course, visited in prerequisites:deque_graph[visited].append(course)learned[course] 1queue deque([x for x in range(numCourses) if learned[x] 0])processed_courses 0while queue:visited queue.popleft()processed_courses 1for course in deque_graph[visited]:learned[course] - 1if learned[course] 0:queue.append(course)return processed_courses numCoursesprint(fprerequisites count of the Courses {len(check_prerequisites)})
result cfp.getTimeMemoryStr(Solution.canFinish_ext3, aSolution, 50000, check_prerequisites)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
prerequisites count of the Courses 49999
函数 canFinish_ext3 的运行时间为 84.02 ms内存使用量为 584.00 KB 执行结果 True4. 最优算法
根据本地日志分析最优算法为第2种方式【循环递归缓存】canFinish_ext1
由于四段代码思路一致主要是使用的数据结构不同因此经验推出以下结论
在作为队列使用时【先进先出】deque性能远远高于list迭代器循环优于循环中进行异常检测下标循环和枚举循环性能基本一致
inumCourses 50000
aSolution Solution()
testcase_big open(rtestcase/hot53_big5W.txt, moder, encodingutf-8).read()
testcase_big testcase_big.replace([, )
tmpItems testcase_big.split(])
check_pre []
for aItem in tmpItems:tmpcurpre aItem.split(,)if len(tmpcurpre) 2:check_pre.append([int(tmpcurpre[0]), int(tmpcurpre[1])])
check_prerequisites check_pre
print(fprerequisites count of the Courses {len(check_prerequisites)})
result cfp.getTimeMemoryStr(Solution.canFinish_base, aSolution, inumCourses, check_prerequisites)
print(result[msg], 执行结果 {}.format(result[result]))
result cfp.getTimeMemoryStr(Solution.canFinish_ext1, aSolution, inumCourses, check_prerequisites)
print(result[msg], 执行结果 {}.format(result[result]))
result cfp.getTimeMemoryStr(Solution.canFinish_ext2, aSolution, inumCourses, check_prerequisites)
print(result[msg], 执行结果 {}.format(result[result]))
result cfp.getTimeMemoryStr(Solution.canFinish_ext3, aSolution, inumCourses, check_prerequisites)
print(result[msg], 执行结果 {}.format(result[result]))# 算法本地速度实测比较
prerequisites count of the Courses 49999
函数 canFinish_base 的运行时间为 50813.51 ms内存使用量为 7264.00 KB 执行结果 True
函数 canFinish_ext1 的运行时间为 66.02 ms内存使用量为 6112.00 KB 执行结果 True
函数 canFinish_ext2 的运行时间为 80.01 ms内存使用量为 520.00 KB 执行结果 True
函数 canFinish_ext3 的运行时间为 84.02 ms内存使用量为 584.00 KB 执行结果 True5. 相关资源
本文代码已上传到CSDN地址Python算法题源代码_LeetCode(力扣)_课程表
一日练一日功一日不练十日空
may the odds be ever in your favor ~
