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 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(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 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(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 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(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 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(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 ~

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

蓝桥杯算法赛 第 6 场 小白入门赛 解题报告 | 珂学家 | 简单场 + 元宵节日快乐

蓝桥杯算法赛 第 6 场 小白入门赛 解题报告 | 珂学家 | 简单场 + 元宵节日快乐

前言 整体评价 因为适逢元宵节&#xff0c;所以这场以娱乐为主。 A. 元宵节快乐 题型: 签到 节日快乐&#xff0c;出题人也说出来自己的心愿, 祝大家AK快乐! import java.util.Scanner;public class Main {public static void main(String[] args) {System.out.println(&qu…
阅读更多...
现代化数据架构升级：毫末智行自动驾驶如何应对年增20PB的数据规模挑战？

现代化数据架构升级：毫末智行自动驾驶如何应对年增20PB的数据规模挑战？

毫末智行是一家致力于自动驾驶的人工智能技术公司&#xff0c;其前身是长城汽车智能驾驶前瞻分部&#xff0c;以零事故、零拥堵、自由出行和高效物流为目标&#xff0c;助力合作伙伴重塑和全面升级整个社会的出行及物流方式。 在自动驾驶领域中&#xff0c;是什么原因让毫末智行…
阅读更多...
Unity3D 使用 Proto

Unity3D 使用 Proto

一. 下载与安装 这里下载Google Protobuff下载 1. 源码用来编译CSharp 相关配置 2. win64 用于编译 proto 文件 二. 编译 1. 使用VS 打开 2. 点击最上面菜单栏 工具>NuGet 包管理器>管理解决方案的NuGet 管理包 版本一定要选择咱们一开始下载的对应版本否则不兼容&am…
阅读更多...
linux中的权限

linux中的权限

Linux 的权限 在了解Linux的权限之前&#xff0c;我们需要知道Linux的构成&#xff0c;Linux分为三个部分&#xff0c;内核、外部程序、以及用户。 内核&#xff1a; 内核一般是指Linux的操作系统&#xff0c;用来执行用户发送的指令 或者 拒绝执行用户发布指令时而发出的报…
阅读更多...
Elasticsearch 创建index库 timeout

Elasticsearch 创建index库 timeout

问题概述 使用 python 客户端 代码进行创建&#xff0c;【之前成功创建&#xff0c;但是现在出现报错&#xff0c;报错代码es_connection.client.indices.create】 def create_vector_index(dataset_index_name,vector_query_field,query_field):es_connection get_collentio…
阅读更多...
高并发Server的基石：reactor反应堆模式

高并发Server的基石：reactor反应堆模式

业务开发同学只关心业务处理流程。但是我们开发的程序都是运行服务端server上&#xff0c;服务端server接收到IO请求后&#xff0c;是如何处理请求并最终进入业务流程的呢&#xff1f;这里不得不提到reactor反应堆模型。reactor反应堆模型来源于大师Doug Lea在 《Sacalable io …
阅读更多...
python Matplotlib Tkinter--＞导出pdf报表

python Matplotlib Tkinter--＞导出pdf报表

环境 python:python-3.12.0-amd64 包: matplotlib 3.8.2 reportlab 4.0.9 import matplotlib.pyplot as plt from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg, NavigationToolbar2Tk import tkinter as tk import tkinter.messagebox as messagebox impor…
阅读更多...
11-pytorch-使用自己的数据集测试

11-pytorch-使用自己的数据集测试

b站小土堆pytorch教程学习笔记 import torch import torchvision from PIL import Image from torch import nnimg_path ../imgs/dog.png imageImage.open(img_path) print(image) # imageimage.convert(RGB)transformtorchvision.transforms.Compose([torchvision.transforms.…
阅读更多...
设计模式（六）代理模式

设计模式（六）代理模式

相关文章设计模式系列 1.代理模式简介 代理模式介绍 代理模式也叫委托模式&#xff0c;是结构型设计模式的一种。在现实生活中我们用到类似代理模式的场景有很多&#xff0c;比如代购、代理上网、打官司等。 定义 为其他对象提供一种代理以控制这个对象的访问。 代理模式…
阅读更多...
Nginx——安装和反向代理

Nginx——安装和反向代理

Nginx安装与应用 1.1 Nginx介绍 Nginx 是一个高性能的HTTP和反向代理服务器,特点是占有内存少&#xff0c;并发能力强 Nginx可以作为静态页面的web服务器&#xff0c;同时还支持CGI协议的动态语言&#xff0c;比如perl、php等。但是不支持java。Java程序只能通过与tomcat配合…
阅读更多...
云原生之容器编排实践-ruoyi-cloud项目部署到K8S：MySQL8

云原生之容器编排实践-ruoyi-cloud项目部署到K8S：MySQL8

背景 前面搭建好了 Kubernetes 集群与私有镜像仓库&#xff0c;终于要进入服务编排的实践环节了。本系列拿 ruoyi-cloud 项目进行练手&#xff0c;按照 MySQL &#xff0c; Nacos &#xff0c; Redis &#xff0c; Nginx &#xff0c; Gateway &#xff0c; Auth &#xff0c;…
阅读更多...
AMRT3D数字孪生引擎详解

AMRT3D数字孪生引擎详解

AMRT 3D数字孪生引擎介绍 AMRT3D引擎是一款融合了眸瑞科技的AMRT格式与轻量化处理技术为基础&#xff0c;以降本增效为目标&#xff0c;支持多端发布的一站式纯国产自研的CS架构项目开发引擎。 引擎包括场景搭建、UI拼搭、零代码交互事件、光影特效组件、GIS/BIM组件、实时数据…
阅读更多...
跨越千年医学对话：用AI技术解锁中医古籍知识，构建能够精准问答的智能语言模型，成就专业级古籍解读助手（LLAMA）

跨越千年医学对话：用AI技术解锁中医古籍知识，构建能够精准问答的智能语言模型，成就专业级古籍解读助手（LLAMA）

跨越千年医学对话&#xff1a;用AI技术解锁中医古籍知识&#xff0c;构建能够精准问答的智能语言模型&#xff0c;成就专业级古籍解读助手&#xff08;LLAMA&#xff09; 介绍&#xff1a;首先在 Ziya-LLaMA-13B-V1基线模型的基础上加入中医教材、中医各类网站数据等语料库&am…
阅读更多...
科技云报道：黑马Groq单挑英伟达，AI芯片要变天？

科技云报道：黑马Groq单挑英伟达，AI芯片要变天？

科技云报道原创。 近一周来&#xff0c;大模型领域重磅产品接连推出&#xff1a;OpenAI发布“文字生视频”大模型Sora&#xff1b;Meta发布视频预测大模型 V-JEPA&#xff1b;谷歌发布大模型 Gemini 1.5 Pro&#xff0c;更毫无预兆地发布了开源模型Gemma… 难怪网友们感叹&am…
阅读更多...
vue3 + vite + ts 中使用less文件全局变量

vue3 + vite + ts 中使用less文件全局变量

文章目录 安装依赖新建css变量文件全局引入css变量文件使用css变量 一、安装依赖 npm install less less-loader --save-dev 二、新建CSS变量文件 (1) :在根目录下的src文件中 src-> asset -> css ->glibal.less // glibal.less :root{--public_background_font_Col…
阅读更多...
基于YOLOv8深度学习+Pyqt5的电动车头盔佩戴检测系统

基于YOLOv8深度学习+Pyqt5的电动车头盔佩戴检测系统

wx供重浩&#xff1a;创享日记 对话框发送&#xff1a;225头盔 获取完整源码源文件已标注的数据集&#xff08;1463张&#xff09;源码各文件说明配置跑通说明文档 若需要一对一远程操作在你电脑跑通&#xff0c;有偿59yuan 效果展示 基于YOLOv8深度学习PyQT5的电动车头盔佩戴检…
阅读更多...
C语言第三十一弹---自定义类型：结构体(下)

C语言第三十一弹---自定义类型：结构体(下)

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 目录 1、结构体内存对齐 1.1、为什么存在内存对齐? 1.2、修改默认对齐数 2、结构体传参 3、结构体实现位段 3.1、什么是位段 3.2、位段的内存分配 3.3、…
阅读更多...
论文精读--GPT3

论文精读--GPT3

不像GPT2一样追求zero-shot&#xff0c;而换成了few-shot Abstract Recent work has demonstrated substantial gains on many NLP tasks and benchmarks by pre-training on a large corpus of text followed by fine-tuning on a specific task. While typically task-agnos…
阅读更多...
EMQX Enterprise 5.5 发布：新增 Elasticsearch 数据集成

EMQX Enterprise 5.5 发布：新增 Elasticsearch 数据集成

EMQX Enterprise 5.5.0 版本已正式发布&#xff01; 在这个版本中&#xff0c;我们引入了一系列新的功能和改进&#xff0c;包括对 Elasticsearch 的集成、Apache IoTDB 和 OpenTSDB 数据集成优化、授权缓存支持排除主题等功能。此外&#xff0c;新版本还进行了多项改进以及 B…
阅读更多...
多模态表征—CLIP及中文版Chinese-CLIP：理论讲解、代码微调与论文阅读

多模态表征—CLIP及中文版Chinese-CLIP：理论讲解、代码微调与论文阅读

我之前一直在使用CLIP/Chinese-CLIP&#xff0c;但并未进行过系统的疏导。这次正好可以详细解释一下。相比于CLIP模型&#xff0c;Chinese-CLIP更适合我们的应用和微调&#xff0c;因为原始的CLIP模型只支持英文&#xff0c;对于我们的中文应用来说不够友好。Chinese-CLIP很好地…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023