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

news/2024/7/15 18:14:18 标签: python, 算法, leetcode, 力扣, 图论, 课程表

 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：

python">输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

python">输入：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. 题目解析

- 题意分解

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

- 优化思路

  1. 通常优化：减少循环层次

  2. 通常优化：增加分支，减少计算集

  3. 通常优化：采用内置算法来提升计算速度

  4. 分析题目特点，分析最优解

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

    2. 可以研究迭代法实现科目检测

- 测量工具

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

3. 代码展开

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

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

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

python">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%在这里插入图片描述

python">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%在这里插入图片描述

python">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) 改进版三【迭代剥离+计数器检测】

特殊的迭代思路

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

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

python">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

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

  1. 在作为队列使用时【先进先出】，deque性能远远高于list
  2. 迭代器循环优于循环中进行异常检测
  3. 下标循环和枚举循环性能基本一致
python">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 ~


http://www.niftyadmin.cn/n/5389201.html

相关文章

OGG-00918 映射中缺少键列 id.

OGG-00918 映射中缺少键列 id.

2024-02-23 14:54:49 INFO OGG-02756 从线索文件获取了表 GISTAR.PXPH_PON_ROUTE 的定义。. The following columns did not default because of type mismatches: id OGG-00918 映射中缺少键列 id. 目标端有字段ID&#xff0c;由于mysql自增&#xff0c;所以只能是b…
阅读更多...
使用和管理jupyter notebook， anaconda环境下在jupyter使用自己创建的虚拟环境，怎么删除jupyter其他内核

使用和管理jupyter notebook， anaconda环境下在jupyter使用自己创建的虚拟环境，怎么删除jupyter其他内核

引言&#xff1a;我有GPU&#xff0c;之前也下载了cuda&#xff0c;但是在jupyter中不能使用gpu&#xff0c;原因是我下载的cuda在另一个虚拟环境pytorch中&#xff0c;但是pytorch这个虚拟环境没有加到jupyter的内核中&#xff0c;怎么在jupyter使用自己创建的虚拟环境看二.an…
阅读更多...
HarmonyOS—代码Code Linter检查

HarmonyOS—代码Code Linter检查

Code Linter代码检查 Code-Linter针对ArkTS/TS代码进行最佳实践、编程规范方面的检查&#xff0c;目前还会检查ArkTS语法规则。开发者可根据扫描结果中告警提示手工修复代码缺陷&#xff0c;或者执行一键式自动修复&#xff0c;在代码开发阶段&#xff0c;确保代码质量。 检查…
阅读更多...
雨云GPU云服务器搭建SD(Stable Diffusion)的教程，搭建自己的AI绘画网站，AIGC

雨云GPU云服务器搭建SD(Stable Diffusion)的教程，搭建自己的AI绘画网站，AIGC

雨云GPU云服务器搭建Stable Diffusion的教程&#xff0c;搭建自己的AI图片生成网站&#xff0c;AIGC Stable Diffusion是什么 Stable Diffusion是一种基于潜在扩散模型&#xff08;Latent Diffusion Models&#xff09;的文本到图像生成模型&#xff0c;由CompVis、Stability…
阅读更多...
【每日前端面经】2023-02-23

【每日前端面经】2023-02-23

题目来源: 牛客 企业级开发整体流程有哪些 项目启动需求调研->需求文档系统设计->设计文档程序开发->开发文档BUG测试->测试文档验收维护 遇到技术难题怎么办 分析可能出现的原因查找搜索引擎寻问文心一言等对话模型打断点&#xff0c;寻找问题复现再一次归纳分…
阅读更多...
Eureka：微服务中的服务注册与发现机制

Eureka：微服务中的服务注册与发现机制

引言 在微服务架构中&#xff0c;由于服务数量巨大并且各个服务的实例可能会频繁上下线&#xff0c;因此服务注册和发现机制至关重要。 那么&#xff0c;有什么工具或技术可以帮助我们解决这个问题呢&#xff1f; 答案就是Eureka。 一、Eureka简介 Eureka是Netflix公司开源的…
阅读更多...
Qt应用软件【协议篇】QtHttpServer三方库的编译、安装、使用示例

Qt应用软件【协议篇】QtHttpServer三方库的编译、安装、使用示例

文章目录 1.Qt HTTP Server 简介2.主要功能和使用场景3.限制和安全性4.使用模块5.代码下载、编译与安装6.QtHttpServer代码示例1.Qt HTTP Server 简介 Qt HTTP Server 是一个轻量级的 HTTP 服务器，它允许在Qt应用程序中构建HTTP服务器功能。这个库主要用于将应用程序功能通过…
阅读更多...
康威生命游戏

康威生命游戏

康威生命游戏 康威生命游戏(Conway’s Game of Life)是康威发明的细胞自动机。 生命游戏有几个简单的规则&#xff1a; 细胞有两种状态&#xff0c;存活或死亡&#xff0c;每个细胞以自身为中心与周围的八格细胞互动。 对于存活的细胞&#xff1a; 当周围的细胞过少(<2)或…
阅读更多...
最新文章

Copyright @ 2022~2023