Python算法题集_图论(课程表)

🕗 发布于 2024-02-23 17:29 python 算法 leetcode 力扣图论

Python算法题集_课程表

题207：课程表
1. 示例说明
2. 题目解析
3. 代码展开
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 <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同

2. 题目解析

- 题意分解

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

- 优化思路

通常优化：减少循环层次
通常优化：增加分支，减少计算集
通常优化：采用内置算法来提升计算速度
分析题目特点，分析最优解
1. 如果一个课程已经检测没有出现环路，则前置课程检测到此课程就不用继续检测下去，减少计算量
2. 可以研究迭代法实现科目检测

- 测量工具

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

3. 代码展开

1) 标准求解【循环+递归+全算】

循环遍历课程，递归检测环路，能算尽算，不出所料，功能测试就已超时

页面功能测试，未能通关，超时失败 在这里插入图片描述

import CheckFuncPerf as cfp

class 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 True
         result = True
         for course in pres:
             if course in visited:
                 return False
             result &= dfs_checkring(visited + [course], list_graph[course])
         return result
     return all(dfs_checkring([i], pres) for i, pres in enumerate(list_graph))

print(f'prerequisites 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 执行结果 = True

2) 改进版一【循环+递归+缓存】

循环遍历课程，递归检测环路，缓存已经计算的课程环路结果

页面功能测试，勉强通过，超过11% 在这里插入图片描述

import CheckFuncPerf as cfp

class 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] * numCourses
     def dfs_checkring(visited, pres):
         if not pres:
             return True
         result = True
         for course in pres:
             if course in visited:
                 return False
             if learned[course] > 0:
                 continue
             learned[course] = 1
             result &= dfs_checkring(visited + [course], list_graph[course])
         return result
     for iIdx, pres in enumerate(list_graph):
         if learned[iIdx] > 0:
             continue
         result = dfs_checkring([iIdx], pres)
         if not result:
             return False
         learned[iIdx] = 1
     return True

print(f'prerequisites 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 执行结果 = True

3) 改进版二【循环+递归+缓存+反向计算】

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

页面功能测试，性能良好，超过88% 在这里插入图片描述

import CheckFuncPerf as cfp

class Solution:
 def canFinish_ext2(self, numCourses, prerequisites):
     def dfs_checkring(iIdx, list_graph, ringflags):
         if ringflags[iIdx] == -1:
             return True
         if ringflags[iIdx] == 1:
             return False
         ringflags[iIdx] = 1
         for jIdx in list_graph[iIdx]:
             if not dfs_checkring(jIdx, list_graph, ringflags):
                 return False
         ringflags[iIdx] = -1
         return True
     list_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 False
     return True

print(f'prerequisites 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 执行结果 = True

4) 改进版三【迭代剥离+计数器检测】

特殊的迭代思路

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

页面功能测试，马马虎虎，超过55% 在这里插入图片描述

import CheckFuncPerf as cfp

class Solution:
 def canFinish_ext3(self, numCourses, prerequisites):
     from collections import deque, defaultdict
     deque_graph = defaultdict(list)
     learned = [0] * numCourses
     for course, visited in prerequisites:
         deque_graph[visited].append(course)
         learned[course] += 1
     queue = deque([x for x in range(numCourses) if learned[x] == 0])
     processed_courses = 0
     while queue:
         visited = queue.popleft()
         processed_courses += 1
         for course in deque_graph[visited]:
             learned[course] -= 1
             if learned[course] == 0:
                 queue.append(course)
     return processed_courses >= numCourses

print(f'prerequisites 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 执行结果 = True

4. 最优算法

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

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

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

inumCourses = 50000
aSolution = Solution()
testcase_big = open(r'testcase/hot53_big5W.txt', mode='r', encoding='utf-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(f'prerequisites 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 执行结果 = True

5. 相关资源

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

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

may the odds be ever in your favor ~

原文地址：https://blog.csdn.net/weixin_36928396/article/details/136258434

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：单片机_no target connected问题解决方法
下一篇：Spring Cloud原理详解

@Autowired 和 @Resource思考（注入redisTemplate时发现一些奇怪的现象）
@Autowired 和 @Resource思考（注入redisTemplate时发现一些奇怪的现象）
阅读更多2024-11-16
25浙江省考-28天学行测-Day5 & Day6-判断推理（中）
1、另有他因2、因果倒置3、否定此因4、根本原因5、三圈质疑1、排除他因2、四圈支持1、无论据有结论2、有论据有结论3、质疑论证过程4、严谨逻辑关系5、比例类论证1、解释说明2、增加论据3、断点
阅读更多2024-11-16
Rust 入门指南（零）：安装及 Cargo 管理器
系列第 0 篇，简单介绍了 Rust 的基本安装和配置流程，以及如何通过 Cargo 创建和管理项目。
阅读更多2024-11-16
Centos使用人大金仓ksql
Centos使用人大金仓ksql
阅读更多2024-11-16
多模态大模型简介
多模态大模型是机器学习领域的一个新兴趋势，它结合了文本、图像、音频等多种数据模态，以实现更全面和深入的信息理解和处理。这种模型能够处理跨模态任务，如图像标注、视觉问答、文本到图像的生成等，是人工智能领
阅读更多2024-11-16
javaScript交互补充2（动画函数封装）
如果多个元素都使用这个动画函数，每次都要var 声明定时器，我们可以给不同元素使用不同的定时器（自己用自己的定时器）核心原理：利用js是一门动态语言，可以很方便的给当前对象添加属性。缓动动画就是让元素
阅读更多2024-11-16
【鸿蒙开发】第十五章 H5与端侧交互、Cookies以及Web调试
Web组件支持在应用拦截到页面请求后自定义响应请求能力。开发者通过接口来实现自定义资源请求响应。自定义请求能力可以用于开发者自定义Web页面响应、自定义文件资源响应等场景。Web网页上发起资源加载请求
阅读更多2024-11-16
javaScript交互补充（元素的三大系列）
使用client系列的相关属性来获取元素可视区的相关信息，可以动态的得到该元素的边框大小，元素大小等。返回自身包括padding，内容区宽度，不含边框，返回数值不带单位。返回自身包括padding，内
阅读更多2024-11-16
django 过滤器的执行
默认情况下，会执行，特别是如果在中配置了它，或者没有禁用它。禁用过滤器：可以通过在APIView中设置来禁用过滤器，避免执行。手动调用过滤器：如果需要，你可以在视图中手动调用来过滤查询集。自定义过滤器
阅读更多2024-11-16
在Ubuntu 24.04 LTS上安装飞桨PaddleX
首先，请运行“ubuntu-drivers devices”命令列出当前可用的硬件设备，确保Ubuntu 24.04.1 LTS已发现安装在桌面计算机中的英伟达显卡，如下图所示。是基于飞桨框架构建的一
阅读更多2024-11-16