Python面试宝典第32题:课程表
题目
你这个学期必须选修numCourses门课程,记为0到numCourses - 1。在选修某些课程之前,需要一些先修课程。先修课程按数组prerequisites给出,其中prerequisites[i] = [ai, bi],表示如果要学习课程ai,则必须先学习课程bi。比如:先修课程对[0, 1]表示想要学习课程0,你需要先完成课程1。
请你判断是否可能完成所有课程的学习?如果可以,返回true。否则,返回false。
备注:prerequisites[i]中的所有课程对互不相同。
示例 1:
输入:numCourses = 2, prerequisites = [[1,0]]
输出:true
解释:总共有2门课程。学习课程1之前,你需要完成课程0。
这是可能的。
示例 2:
输入:numCourses = 2, prerequisites = [[1,0], [0,1]]
输出:false
解释:总共有2门课程。学习课程1之前,你需要先完成课程0;并且学习课程0之前,还应先完成课程1。
这是不可能的。

深度优先搜索算法
这个问题描述了一个典型的图论问题,涉及到课程之间的依赖关系。要判断是否有可能完成所有课程的学习,我们需要检查是否存在环。如果有环存在,则意味着某些课程之间形成了一个闭环依赖,从而无法完成所有课程的学习。
深度优先搜索算法(DFS)是解决本问题的一种有效方法,可用于检测图中是否存在环。其基本思想为:使用DFS来遍历图中的所有节点,在遍历过程中,我们需要标记正在访问的节点,以检测环的存在;如果在访问过程中遇到一个已经在访问路径上的节点,那么就找到了一个环。如果所有节点都能被访问且没有环,则表示可以完成所有课程的学习。使用深度优先搜索算法求解本题的主要步骤如下。
1、构建一个邻接表来表示图结构。
2、对于每个节点,执行DFS并跟踪正在访问的节点。
3、如果在访问过程中,遇到已经存在于当前路径上的节点,则存在环。
4、如果所有节点都被访问过且没有发现环,则返回true。否则,返回false。
根据上面的算法步骤,我们可以得出下面的示例代码。
def course_schedule_by_dfs(numCourses, prerequisites):def dfs(course, visiting):if visiting[course]:return Falseif visited[course]:return True# 标记当前节点正在访问visiting[course] = Truefor next_course in graph[course]:if not dfs(next_course, visiting):return False# 结束访问visiting[course] = False# 标记当前节点已被访问visited[course] = Truereturn True# 构建邻接表graph = [[] for _ in range(numCourses)]# 标记每个节点是否被访问过visited = [False] * numCourses# 标记每个节点是否正在访问visiting = [False] * numCourses# 填充邻接表for course, prereq in prerequisites:graph[prereq].append(course)# 对于每个节点执行DFSfor course in range(numCourses):if not dfs(course, visiting):return Falsereturn TruenumCourses = 2
prerequisites = [[1, 0]]
print(course_schedule_by_dfs(numCourses, prerequisites))numCourses = 2
prerequisites = [[1, 0], [0, 1]]
print(course_schedule_by_dfs(numCourses, prerequisites))
拓扑排序法
拓扑排序法是针对有向无环图 (DAG) 的一种排序方法,它将图中的所有顶点按照某种顺序排列,使得对于每条有向边u → v,顶点u在顶点v之前出现。如果一个图可以进行拓扑排序,则说明该图没有环。如果在排序过程中发现某个顶点的入度永远不能变为 0,则说明存在环。使用拓扑排序法求解本题的主要步骤如下。
1、构建一个邻接表来表示图结构。
2、计算每个节点的入度,即有多少条边指向该节点。
3、将所有入度为0的节点加入队列。
4、从队列中取出节点,将其添加到结果列表中,并减少其相邻节点的入度。
5、将入度变为0的节点加入队列。
6、重复步骤4和5,直到队列为空。
7、如果所有节点都被处理,则不存在环。否则,存在环。
根据上面的算法步骤,我们可以得出下面的示例代码。
from collections import dequedef course_schedule_by_topsort(numCourses, prerequisites):# 构建邻接表graph = [[] for _ in range(numCourses)]# 计算每个节点的入度indegrees = [0] * numCourses# 填充邻接表并计算入度for course, prereq in prerequisites:graph[prereq].append(course)indegrees[course] += 1# 创建队列,将所有入度为0的节点加入队列queue = deque([node for node in range(numCourses) if indegrees[node] == 0])# 存储已完成的课程completed_courses = []# 处理队列中的节点while queue:prereq = queue.popleft()completed_courses.append(prereq)for course in graph[prereq]:indegrees[course] -= 1if indegrees[course] == 0:queue.append(course)# 如果所有课程都被完成,则返回Truereturn len(completed_courses) == numCoursesnumCourses = 2
prerequisites = [[1, 0]]
print(course_schedule_by_topsort(numCourses, prerequisites))numCourses = 2
prerequisites = [[1, 0], [0, 1]]
print(course_schedule_by_topsort(numCourses, prerequisites))
总结
使用深度优先搜索算法求解本题的时间复杂度为O(V + E)。其中,V是顶点的数量(课程总数),E是边的数量(先修课程对的数量),每个顶点和每条边都会被访问一次。最坏情况下,递归栈的深度可以达到 V,因此空间复杂度为O(V)。深度优先搜索算法的优点是实现相对简单,但对于大规模数据集,递归可能导致栈溢出。
拓扑排序法的时间复杂度也为O(V + E),最坏情况下的空间复杂度为O(V + E),因为其需要额外的空间来存储邻接表和队列。拓扑排序法的优点是实现较为直观,易于理解,但实现稍微复杂一些,需要额外的入度计数和队列操作。
相关文章:
Python面试宝典第32题:课程表
题目 你这个学期必须选修numCourses门课程,记为0到numCourses - 1。在选修某些课程之前,需要一些先修课程。先修课程按数组prerequisites给出,其中prerequisites[i] [ai, bi],表示如果要学习课程ai,则必须先学习课程b…...
简单介绍BTC的Layer2项目RGB
这里写自定义目录标题 介绍(历史背景,项目成员)核心技术组成部分一次性密封条(single-use-seals)客户端验证(client-side validation) 总结 注:该内容不构成投资建议,有些…...
跨境电商卖家必看:搭建安全稳定测评自养号环境系统
对于卖家而言,测评作为一种低成本、高回报的推广策略,对于提升产品流量、转化率、优化关键词质量分及增强链接权重等方面均发挥着积极作用。以下是自养号优势及测评环境搭建技术要点 一、搭建安全稳定的测评环境系统 核心要点: 硬件参数去…...
如何对open62541.h/open62541.c的UA_Client进行状态(在线/掉线)监控
文章目录 背景解决方案注意事项 背景 目前在利用open62541.h/open62541.c编写了一个与PLC进行OPCUA通讯的上位机程序。 上位机这边会定时对PLC的某个opcua变量进行写操作。但是假如PLC离线或者说拔掉网线,上位机就会直接崩溃死机,并且报如下的错误&…...
高等数学 第九讲 一元函数积分学的应用
1. 一元函数积分学的应用 文章目录 1. 一元函数积分学的应用1. 几何应用1.1 用定积分表达和计算平面图形的面积1.2 用定积分表达和计算旋转体的体积1.2.1 微分法1.2.2 二重积分法1.2.3 古尔丁定理1.2.4 旋转体的体积公式总结 1.3 用定积分表达和计算函数的平均数1.4 其他几何应…...
django如何更新数据库字段并与数据库保持同步?
关键步骤: 第一步: 执行:python manage.py makemigrations 你的项目名称第二步:它会提示你选1还是2,这里因为添加字段,所以选1第三步:出现>>>这个,直接输入这个第四步&am…...
jenkins插件 SSH Publishers
Jenkins 是一个开源的自动化服务器,常用于持续集成和持续交付 (CI/CD)。以下是一些与 Jenkins 相关的 SSH 发布者及其功能: SSH 插件: 功能: 允许 Jenkins 通过 SSH 执行远程命令。用户可以配置 SSH 服务器,使用 SSH 密钥进行身份…...
Kafka Client客户端操作详解
文章目录 基础客户端版本消息生产者消息消费者踩坑 客户端属性分析消费者分组消费机制生产者拦截器消息序列化消息分区路由机制生产者消息缓存机制发送应答机制生产者消息幂等性生产者消息事务 客户端流程总结 基础客户端版本 导入依赖 <properties><project.build.…...
【HarmonyOS NEXT星河版开发学习】小型测试案例15-博客列表
个人主页→VON 收录专栏→鸿蒙开发小型案例总结 基础语法部分会发布于github 和 gitee上面(暂未发布) 前言 该案例主要是ForEach渲染的练习,ForEach可以基于数组的个数,渲染组件个数(简化代码) 在…...
go-zero中统一返回前端数据格式的几种方式
方式一、直接定义一个成功和失败的方法,在代码里面修改(对代码有侵入,每次都要修改代码) 1、封装一个统一返回的方法 package utilsimport ("github.com/zeromicro/go-zero/rest/httpx""net/http" )type Body struct {Code int json:"code…...
【向量数据库】Ubuntu编译安装FAISS
参考官方的安装指导:https://github.com/facebookresearch/faiss/blob/main/INSTALL.md,不需要安装的可以跳过 ~$ wget https://github.com/facebookresearch/faiss/archive/refs/tags/v1.8.0.tar.gz ~$ tar -zxvf v1.8.0.tar.gz ~$ cd faiss-1.8.0 ~$ …...
制造知识普及(九)--企业内部物料编码(IPN)与制造商物料编码(MPN)
在日常的物料管理业务逻辑中,一物一码是物料管理的基本的业务规则,不管物料从产品开发还是仓库管理,甚至成本核算,都要遵循这个原则,才能保证产品数据的准确性,才具备唯一追溯的可行性。大部分企业都是这种…...
【整数规划】+【0—1规划】解决优化类问题(Matlab代码)
目录 文章目录 前言 一、整数规划 分类: 二、典例讲解 1.背包问题 2.指派问题 总结 前言 如果觉得本篇文章还不错的话,给作者点个赞鼓励一下吧😁😁😁 在规划问题中,有些最优解可能是分数或小数&am…...
Linux下如何使用Curl进行网络请求
在Linux系统上,Curl是一个非常强大的网络请求工具,可以用于发送各种类型的HTTP请求,并获取响应结果。它支持常见的HTTP方法,如GET、POST、PUT、DELETE等,还支持HTTPS、FTP等不同协议。Curl提供了丰富的参数选项&#x…...
PostgreSQL 触发器
PostgreSQL 触发器 PostgreSQL触发器是一种强大的数据库对象,它可以在特定的数据库事件发生时自动执行预定义的操作。这些事件可以是插入、更新或删除表中的行。触发器通常用于强制复杂的业务规则、提供审计跟踪、数据同步以及实现复杂的约束。 触发器的基本概念 …...
LeetCode——3131.找出与数组相加的整数I
通过万岁!!! 题目:给你两个数组nums1和nums2,然后让你找一个数,使得nums1的数加上这个数以后得到的数组nums1’与nums2是相同的。注意这里只要元素相同就好了,不一定顺序相同。思路:…...
【SpringMVC】详细了解SpringMVC中WEB-INF 目录资源,视图解析器和静态资源放行的使用。
目录 1. 回顾SpringMVC请求转发和重定向 2. WEB-INF资源目录 3. 视图解析器 4. 静态资源放行 1. 回顾SpringMVC请求转发和重定向 概念:在一个项目中功能非常多,也就意味着有非常多的Servlet,不同的Servlet的职不 同 ,而用户发起…...
如何学好uni-app
学习uni-app需要掌握以下技能: 1. 前端基础:熟悉HTML、CSS和JavaScript等前端开发技术,了解基本的前端框架如Vue.js。 2. Vue.js:因为uni-app是基于Vue.js构建的,所以需要对Vue.js有深入的理解。可以先通过官方文档或者…...
C++ QT使用stackwidget实现页面切换(含源码)
C++ QT使用stackwidget实现页面切换(含源码) 0.前言1.UI布局1.1使用stackwidget2.代码方式添加页面实现页面切换3.源码4.最终效果0.前言 在QT中一个界面中如何实现页面的切换,而不是新弹出的窗口,这里采用的stackwidget,以层叠widget的方式选定页面索引从而实现页面切换。…...
打工人上班适合用的蓝牙耳机推荐?几款开放式耳机推荐
日常工作的话,我还是比较推荐开放式蓝牙耳机的,它特别适合那些需要在长时间工作中保持专注和舒适度的环境,那开放式耳机其实还有一些主要的优点: 减少耳朵疲劳:由于开放式耳机不需要紧密贴合耳朵,因此可以…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
