当前位置: 首页 > news >正文

【力扣热题100】207. 课程表 python 拓扑排序

【力扣热题100】207. 课程表 python 拓扑排序

  • 写在最前面
  • 207. 课程表
    • 解决方案:判断是否可以完成所有课程的学习
      • 方法:拓扑排序
      • 实现步骤
      • Python 实现
      • 性能分析
      • 结论

写在最前面

刷一道力扣热题100吧
难度中等

https://leetcode.cn/problems/course-schedule/?envType=study-plan-v2&envId=top-100-liked

在这里插入图片描述

207. 课程表

你这个学期必须选修 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] 中的所有课程对 互不相同

解决方案:判断是否可以完成所有课程的学习

本问题涉及到一个常见的图论问题,即检测有向图中是否存在循环。在这个场景中,课程可以被视为图的节点,而先修课程的要求可以被视为有向边。

我们的目标是:检查这个有向图是否包含一个循环。如果存在循环,意味着有些课程的先修要求彼此相互依赖,从而导致无法完成所有课程。

方法:拓扑排序

为了解决这个问题,我们可以使用拓扑排序。拓扑排序是一种对有向无环图(DAG)的顶点的线性排序,使得对于任何来自顶点 u 到顶点 v 的有向边,u 在排序中都出现在 v 之前。

如果我们在进行拓扑排序的过程中发现无法完成排序(即图中存在循环),那么就意味着无法完成所有课程的学习。

实现步骤

  1. 构建图:首先,我们需要构建图的表示。通常,这可以通过邻接表来实现。
  2. 计算入度:对于图中的每个节点(课程),计算进入该节点的边的数量,即该课程的先修课程数量。
  3. 初始化队列:创建一个队列,用于存放所有入度为0的节点(没有先修课程的课程)。
  4. 进行拓扑排序
    • 从队列中移除一个节点(课程),并将其添加到拓扑排序的结果中。
    • 遍历从该节点出发的所有边,将与之相连的节点的入度减1。
    • 如果某个相邻节点的入度变为0,则将其加入队列。
  5. 检查是否可以完成排序:如果排序的结果包含所有的课程,则返回 true;否则,返回 false。

Python 实现

下面是问题的 Python 实现,使用了拓扑排序的方法:

from collections import dequeclass Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:# 构建图的邻接表表示和入度数组adj_list = [[] for _ in range(numCourses)]indegree = [0] * numCoursesfor dest, src in prerequisites:adj_list[src].append(dest)indegree[dest] += 1# 初始化队列queue = deque([i for i in range(numCourses) if indegree[i] == 0])visited = 0# 拓扑排序while queue:course = queue.popleft()visited += 1for next_course in adj_list[course]:indegree[next_course] -= 1if indegree[next_course] == 0:queue.append(next_course)# 检查是否所有课程都被访问过return visited == numCourses

性能分析

  • 时间复杂度:O(N + P),其中 N 是课程数量,P 是先修课程对的数量。
  • 空间复杂度:O(N + P),用于存储图的邻接表和入度数组。

结论

使用拓扑排序,我们可以高效地确定是否可能完成所有课程的学习。

这种方法在计算机科学的许多领域,如任务调度、数据处理等,都有广泛的应用。

相关文章:

【力扣热题100】207. 课程表 python 拓扑排序

【力扣热题100】207. 课程表 python 拓扑排序 写在最前面207. 课程表解决方案&#xff1a;判断是否可以完成所有课程的学习方法&#xff1a;拓扑排序实现步骤Python 实现性能分析结论 写在最前面 刷一道力扣热题100吧 难度中等 https://leetcode.cn/problems/course-schedule…...

【滑动窗口】LeetCode2953:统计完全子字符串

作者推荐 [二分查找]LeetCode2040:两个有序数组的第 K 小乘积 本题其它解法 【离散差分】LeetCode2953:统计完全子字符串 题目 给你一个字符串 word 和一个整数 k 。 如果 word 的一个子字符串 s 满足以下条件&#xff0c;我们称它是 完全字符串&#xff1a; s 中每个字符…...

base64转PDF

今天做皖事通的对接&#xff0c;下载电子证照后发现回传的是base64&#xff0c;调试确认是个麻烦事&#xff0c;网上搜了一下没有base64转PDF的在线预览功能&#xff0c;只能自己写个调试工具了&#xff0c;以下是通过纯JS方式写的代码&#xff0c;可直接拿去使用&#xff1a; …...

clip-path,css裁剪函数

https://www.cnblogs.com/dzyany/p/13985939.html clip-path - CSS&#xff1a;层叠样式表 | MDN 我们看下这个例子 polygon里有四个值分别代表这四个点相对于原图左上方的偏移量。 裁剪个五角星...

第二证券:食品饮料板块拉升,乳业股亮眼,西部牧业“20cm”涨停

证券时报网讯&#xff0c;食物饮料板块5日盘中拉升走高&#xff0c;乳业股体现活跃&#xff0c;到发稿&#xff0c;骑士乳业涨超27%&#xff0c;西部牧业“20cm”涨停&#xff0c;阳光乳业亦涨停。 其它个股方面&#xff0c;盖世食物涨超20%&#xff0c;润普食物涨超18%&#…...

React 好用的工具库

1、html-react-parser HTML 到 React 解析器&#xff0c;适用于服务器 &#xff08;Node.js&#xff09; 和客户端&#xff08;浏览器&#xff09;&#xff0c;适用于React节点修改过滤等需求 解析器将 HTML 字符串转换为一个或多个 React 元素。可以将一个元素替换为另一个元素…...

C++面试宝典第2题:逆序输出整数

题目 写一个方法&#xff0c;将一个整数逆序打印输出到控制台。注意&#xff1a;当输入的数字含有结尾的0时&#xff0c;输出不应带有前导的0。比如&#xff1a;123的逆序输出为321&#xff0c;8600的逆序输出为68&#xff0c;-609的逆序输出为-906。 解析 这道题本身并没有什么…...

Twincat功能块使用经验总结

控制全局变量&#xff1a; //轴控制指令 bi_Power: BOOL; //使能 bi_Reset: BOOL; //复位 bi_Stop: BOOL; //停止 bi_JogForward: BOOL; //正向点动 bi_JogBackwards: BOOL; //反向点动 bi_MoveAdditive: BOOL; //增量位…...

香港服务器时间不准,差8小时

解决方案1 1、timedatectl查看系统时间 2、查看系统时区 ls /usr/share/zoneinfo 3、删除当前系统所处时区 rm /etc/localtime 4、创建软链接&#xff0c;以替换当前的时区信息 ln -s /usr/share/zoneinfo/Universal /etc/localtime 解决方案2 手动设置硬件时钟 1、设置系…...

C++ 抽象类和接口 详解

目录 0 引言1 抽象类2 接口2.1 Java与C接口的区别 &#x1f64b;‍♂️ 作者&#xff1a;海码007&#x1f4dc; 专栏&#xff1a;C专栏&#x1f4a5; 标题&#xff1a;C 抽象类和接口 详解❣️ 寄语&#xff1a;书到用时方恨少&#xff0c;事非经过不知难&#xff01;&#x1f…...

【Linux】awk 使用

awk 输出 // 打印所有列 $ awk {print $0} file // 打印第一列 $ awk {print $1} file // 打印第一和第三列 $ awk {print $1, $3} file // 打印第三列和第一列&#xff0c;注意先后顺序 $ cat file | awk {print $3, $1} …...

LeetCode力扣每日一题(Java):9、回文数

一、题目 二、解题思路 1、我的思路 当x<0时&#xff0c;x一定不是回文数&#xff0c;直接返回false 当x>0且x<10时&#xff0c;x一定是回文数&#xff0c;直接返回true x>10时&#xff0c;先将x转为字符串。将数字转成字符串方法挺多的&#xff0c;以下是&…...

WPF前端实现人脸扫描动画效果

前言 本章实现的效果主要通过OpacityMask与LinearGradientBrush(径向渐变) 的组合应用来实现。最终实现效果如下: LinearGradientBrush线性渐变画刷 LinearGradientBrush其实很简单,我们只需要关注5个属性,使用这5个属性你就可以完成这个画刷几乎所有的变化。 属性介…...

更改AndroidStudio模拟器位置

C盘何等的珍贵&#xff0c;可是好多工具&#xff0c;软件非得默认安装在C盘。。导致C盘越来越紧张。。 在日常使用过程中&#xff0c;安装任何软件都会将其安装到非系统盘下&#xff0c;Android模拟器也不能例外。保护好C盘也是日常一个良好的习惯。 Android AVD默认路径&…...

Dash 协议介绍

<?xml version"1.0" encoding"utf-8"?> <MPD xmlns"urn:mpeg:dash:schema:mpd:2011" minBufferTime"PT1.5S" type"static" mediaPresentationDuration"PT0H1M0.3S" maxSegmentDuration"PT0H0M2.0…...

RabbitMQ的消息发送和接收机制

所有 MQ 产品从模型抽象上来说都是一样的过程&#xff1a; 消费者&#xff08;consumer&#xff09;订阅某个队列。生产者&#xff08;producer&#xff09;创建消息&#xff0c;然后发布到队列&#xff08;queue&#xff09;中&#xff0c;最后将消息发送到监听的消费者。 上…...

记录111

在两台 RHEL 8 服务器上搭建 PostgreSQL 和 pgpool-II 环境涉及到安装 PostgreSQL、配置流复制&#xff08;Streaming Replication&#xff09;以及安装和配置 pgpool-II。以下是详细的步骤&#xff1a; ### 准备工作 1. **获取服务器**&#xff1a;确保你有两台运行 RHEL 8 的…...

振动和震动的区别?

问题描述&#xff1a;振动和震动的区别&#xff1f; 问题解决&#xff1a; 震动&#xff08;Oscillation&#xff09;&#xff1a; 特点&#xff1a; 随机的、突发的、不经常的、无规律的运动。例子&#xff1a; 地壳震动、消息震动全国&#xff0c;强调的是运动的力度或幅度&…...

3DMM模型

目录 BFMBFM_200901_MorphableModel.matexp_pca.bintopology_info.npyexp_info.npy BFM BFM_2009 01_MorphableModel.mat from scipy.io import loadmat original_BFM loadmat("01_MorphableModel.mat") # dict_keys: [__header__, __version__, __globals__, # …...

Python 3 使用 write()、writelines() 函数写入文件

1 使用 write() 函数&#xff0c;将字符串&#xff08;或字节串&#xff0c;仅适用写入二进制文件中&#xff09;写入文件中。 with open(example.txt,w,encodingutf-8) as f:f.write(春夜喜雨\n)f.write(杜甫 [唐代]\n)f.write(好雨知时节&#xff0c;当春乃发生。\n)f.write(…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

【Android】Android 开发 ADB 常用指令

查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

Android屏幕刷新率与FPS(Frames Per Second) 120hz

Android屏幕刷新率与FPS(Frames Per Second) 120hz 屏幕刷新率是屏幕每秒钟刷新显示内容的次数&#xff0c;单位是赫兹&#xff08;Hz&#xff09;。 60Hz 屏幕&#xff1a;每秒刷新 60 次&#xff0c;每次刷新间隔约 16.67ms 90Hz 屏幕&#xff1a;每秒刷新 90 次&#xff0c;…...

ubuntu中安装conda的后遗症

缘由: 在编译rk3588的sdk时&#xff0c;遇到编译buildroot失败&#xff0c;提示如下&#xff1a; 提示缺失expect&#xff0c;但是实测相关工具是在的&#xff0c;如下显示&#xff1a; 然后查找借助各个ai工具&#xff0c;重新安装相关的工具&#xff0c;依然无解。 解决&am…...