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

 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 <= 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) 标准求解【循环+递归+全算】

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

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

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

特殊的迭代思路

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

页面功能测试，马马虎虎，超过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

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

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/413207.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

单片机精进之路-5矩阵键盘扫描

单片机精进之路-5矩阵键盘扫描

如下图&#xff0c;先在p3口输出0xfe&#xff0c;再读取p3口的电平&#xff0c;如果没有按键按下&#xff0c;temp & 0xf0还是0xf0&#xff0c;如果又第一个键按下&#xff0c;temp & 0xf0还是0xee&#xff0c;其他按键由此类推可得。 //4*4键盘检测程序,按下键后相应…
阅读更多...
Java SpringBoot 创建项目工程输出 Hello World

Java SpringBoot 创建项目工程输出 Hello World

Java SpringBoot 创建项目工程输出 Hello World 1、新建项目 2、创建 controller 3、编写 Hello World 代码 package com.zhong.demo01.controller;import org.springframework.web.bind.annotation.RequestMapping; import org.springframework.web.bind.annotation.Res…
阅读更多...
Jmeter学习系列之八：控制器Controllers 的入门介绍

Jmeter学习系列之八：控制器Controllers 的入门介绍

一、Controllers 简介 Jmeter有两种类型的控制器&#xff1a;Samplers&#xff08;取样器&#xff09;和Logical Controllers&#xff08;逻辑控制器&#xff09;&#xff1b;它们驱动着测试的进行取样器&#xff1a;让jmeter发送请求到服务器以及接收服务器的响应数据逻辑控制…
阅读更多...
Redis高可用三主三从集群部署（三种方式部署/18个节点的大集群）

Redis高可用三主三从集群部署（三种方式部署/18个节点的大集群）

文章目录 &#x1f50a;博主介绍&#x1f964;本文内容使用宝塔面板搭建集群规划配置验证 使用docker搭建使用脚本搭建规划防火墙端口配置脚本redis.conf配置文件执行过程 &#x1f4e2;文章总结&#x1f4e5;博主目标 &#x1f50a;博主介绍 &#x1f31f;我是廖志伟&#xff…
阅读更多...
常用的制造企业网络优化方案

常用的制造企业网络优化方案

在制造业企业不断加速转型的情况下&#xff0c;企业内部数据传输面临了更高的要求。在企业的多站点内部网络互联互通方面&#xff0c;常见的组网网络优化方案有多种选择&#xff0c;每种都有其独特的优势。以下是其中VPN、MPLS、SD-WAN三种主要的组网方案&#xff1a; 1. VPN&a…
阅读更多...
热闹元宵进行中，如何利用VR全景展示民宿品牌形象？

热闹元宵进行中，如何利用VR全景展示民宿品牌形象？

错峰出游闹元宵&#xff0c;元宵节恰逢周末&#xff0c;而且还是春节假期返工之后的首个休息日&#xff0c;不少人都想通过短途度假来缓解“节后综合征”。两位数的特价机票、打折的各种酒店让你实现“旅行自由”&#xff0c;那么如何知道特价酒店服务好不好呢&#xff1f;先别…
阅读更多...
某电力铁塔安全监测预警系统案例分享

某电力铁塔安全监测预警系统案例分享

项目概述 电力铁塔是承载电力供应的重要设施&#xff0c;它的安全性需要得到可靠的保障。但是铁塔一般安装在户外&#xff0c;分布广泛&#xff0c;且有很多安装在偏远地区&#xff0c;容易受到自然、人力的影响和破环。因此需要使用辅助的方法实时监控铁塔的安全状态&#xff…
阅读更多...
【algorithm】算法基础课---排序算法（附笔记 | 建议收藏）

【algorithm】算法基础课---排序算法（附笔记 | 建议收藏）

&#x1f680;write in front&#x1f680; &#x1f4dd;个人主页&#xff1a;认真写博客的夏目浅石. &#x1f381;欢迎各位→点赞&#x1f44d; 收藏⭐️ 留言&#x1f4dd; &#x1f4e3;系列专栏&#xff1a;AcWing算法学习笔记 &#x1f4ac;总结&#xff1a;希望你看完…
阅读更多...
移动端学习：如何把exe转换成apk

移动端学习：如何把exe转换成apk

exe转换成apk是怎么实现的呢？-电脑端-一门科技将exe文件转换成apk文件是一个比较常见的需求，尤其是对于一些开发者和用户来说。但是，这个过程并不是简单的复制和粘贴。在本文中，我们将介绍exe转换成apk的原理和详细介绍。首先，我们需要了解什么https://www.yimenapp.net/k…
阅读更多...
YOLOv9图像标注和格式转换

YOLOv9图像标注和格式转换

一、软件安装 labelimg安装&#xff08;anaconda&#xff09; 方法一、 pip install labelImg 方法二、 pip install PyQt5 -i https://pypi.tuna.tsinghua.edu.cn/simple/ pip install pyqt5-tools -i https://pypi.tuna.tsinghua.edu.cn/simple/ pip install lxml -i ht…
阅读更多...
【软件测试】--功能测试2--常用设计测试用例方法

【软件测试】--功能测试2--常用设计测试用例方法

一、解决穷举场景 重点&#xff1a;使用等价类划分法 1.1 等价类划分法 重点&#xff1a;有效等价和单个无效等价各取1个即可。 步骤&#xff1a;1、明确需求2、确定有效和无效等价3、根据有效和无效造数据编写用例 1.2 案例&#xff08;qq合法验证&#xff09; 需求&#xff…
阅读更多...
将仓库A中的部分提交迁移到仓库B中

将仓库A中的部分提交迁移到仓库B中

结论&#xff1a; 使用git format-patchgit am即可实现 使用场景&#xff1a; 例如仓库A这里有5个提交记录&#xff0c;commitid1, commitid2, commitid3, commitid4&#xff0c;commitid5 仓库B想用仓库A中提交的代码&#xff0c;手动改比较慢&#xff0c;当改动较多的时候…
阅读更多...
省市区街道/乡镇四级联动vue3

省市区街道/乡镇四级联动vue3

最近优化了一个省.市.区/县、乡镇/街道的四级联动组件&#xff0c;技术栈是element vue3记录一下。 本来是这样的三级联动&#xff1a; 这个三级联动很简单&#xff0c;直接利用el-select组件把地区值带进去就行了&#xff0c;现在要优化成省.市.区/县、乡镇/街道的四级联动&…
阅读更多...
数据隐私安全趋势

数据隐私安全趋势

在当今社交媒体和开源开发的世界中&#xff0c;共享似乎已成为社会常态。毕竟&#xff0c;我们都被教导分享就是关怀。这不仅适用于个人&#xff0c;也适用于公司&#xff1a;无论是有意在社交媒体帐户和公司网站上&#xff0c;还是无意中通过员工的行为&#xff0c;公司可能会…
阅读更多...
P1450 [HAOI2008] 硬币购物 dp 容斥 —— s - c[i]*(d[i]+1)怎么理解

P1450 [HAOI2008] 硬币购物 dp 容斥 —— s - c[i]*(d[i]+1)怎么理解

[HAOI2008] 硬币购物 - 洛谷 看了洛谷许多题解&#xff0c;一开始理解不了为什么是 s - c[i]*(d[i]1)&#xff0c;为什么要1呢&#xff1f; 其实是dp理解的不好。 这里的意思就是该枚硬币先超过限制&#xff0c;接下来剩下的背包也要填满&#xff0c;4种硬币随便组合的情况数…
阅读更多...
【CMU 15-445】Lecture 15: Concurrency Control Theory 学习笔记

【CMU 15-445】Lecture 15: Concurrency Control Theory 学习笔记

Concurrency Control Theory DefinitionsACID: AtomicityACID: ConsistencyACID: IsolationACID: Durability 本节课主要介绍事务的概念和特性。 Definitions 事务是一组数据库操作&#xff08;比如SQL语句&#xff09;的集合&#xff0c;进一步可以抽象为对某些数据对象的读写…
阅读更多...
10W 音频功率放大电路芯片TDA2003，可用于汽车收音机及收录机中作音频功率放大器，内部具有短路保护和过热保护等功能

10W 音频功率放大电路芯片TDA2003，可用于汽车收音机及收录机中作音频功率放大器，内部具有短路保护和过热保护等功能

TDA2003 用于汽车收音机及收录机中作音频功率放大器。 采用 TO220B5 封装形式。 主要特点&#xff1a; ⚫ 内部具有短路保护和过热保护。内部具有地线开路、电源极性接 反和负载泄放电压反冲等保护电路。 ⚫ 输出电流大。 ⚫ 负载电阻可低至 1.6 。 …
阅读更多...
matlab批量替换txt文本文件的特定行的内容

matlab批量替换txt文本文件的特定行的内容

1.下图所示&#xff0c;我想要替换第14行。 2.运行代码后&#xff0c;第14行已经更改为需要的内容。 clc,clear; %%----------------------需要更改的地方------------------------------------ % 设置要操作的文本文件路径&#xff0c;替换为你自己的文件路径 path D:\paper_…
阅读更多...
基于面结构光的高反射物体重建方法(相位偏折术)

基于面结构光的高反射物体重建方法(相位偏折术)

Elon Musk曾表示&#xff0c;“在实现全自动驾驶的过程中&#xff0c;三维重建技术是不可或缺的一环。” Facebook的创始人Mark Zuckerberg也指出&#xff0c;“元宇宙时代的来临将更加依赖于高度精细的三维空间表达。” 这些业界巨擘的言论无疑为三维重建的未来发展注入了强大…
阅读更多...
java 数据结构栈和队列

java 数据结构栈和队列

目录 栈(Stack) 栈的使用 栈的模拟实现 栈的应用场景 队列(Queue) 队列的使用 队列模拟实现 循环队列 双端队列 用队列实现栈 用栈实现队列 栈(Stack) 什么是栈&#xff1f; 栈 &#xff1a;一种特殊的线性表&#xff0c;其 只允许在固定的一端进行插入和删除元素操…
阅读更多...
最新文章

Copyright @ 2022~2023