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

力扣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] 中的所有课程对 互不相同

这道题说人话就算判断这个有向图有没有环路。

我们知道拓扑排序可以用来判断是否有环路,不过仅仅是判断环路也可以直接用dfs,不需要完全写出拓扑排序,毕竟拓扑排序相比dfs还是更复杂一些。

下面给出上述两种思路的代码

1.拓扑排序判断

我的拓扑排序的代码思路是参考王道书介绍的思路

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> graph(numCourses, vector<int>(numCourses));//邻接矩阵vector<int> indegree(numCourses, 0);//每个节点的入度for (int i = 0; i < prerequisites.size(); i++) {graph[prerequisites[i][1]][prerequisites[i][0]] = 1;//构造邻接矩阵indegree[prerequisites[i][0]]++;//修改该点的入度}stack<int> stk;//用栈或队列都可以for (int i = 0; i < numCourses; i++) {if (indegree[i] == 0)//入度为0的点入栈stk.push(i);}int cnt = 0;//记录节点的数量while (!stk.empty()) {int i = stk.top();stk.pop();//如果是正常的拓扑排序,这里就可以输出节点了,本题只要求判断环路cnt++;//出栈的节点入度都为0,cnt++for (int j = 0; j < numCourses; j++) {//遍历当前节点的临边if (graph[i][j] != 0) {graph[i][j] = 0;//删除这条有向边indegree[j]--;//相邻边的入度减1if (indegree[j] == 0)//如果临边入度为0,入栈stk.push(j);}}}return cnt == numCourses;//最终的判断条件,cnt不为n,则有环路//因为有环路的情况下环路上的节点的入度不可能为0,就不会入栈,所以最后cnt的值不为n}
};

下面用一张图作为示例:

一开始只有0的度为0,所以0入栈,出栈时会执行这一段代码

            for (int j = 0; j < numCourses; j++) {//遍历当前节点的临边if (graph[i][j] != 0) {graph[i][j] = 0;//删除这条有向边indegree[j]--;//相邻边的入度减1if (indegree[j] == 0)//如果临边入度为0,入栈stk.push(j);}}

那么就把从0开始的弧都删掉,并把弧所指向的节点的入度减1

这时候1和2的入度就为0了,入栈。然后2先出栈,把2->3这段弧也删掉

但是此时3的入度不为0,也就先不会入栈。然后1出栈,把1->3这段弧删掉

这时候3的入度也为0,3入栈。3再出栈,3出栈反正啥也不会做。

最终,4个节点全部入了栈,因此cnt==n成立,该图是无环有向图。

如果是有环图,可以自己试一下,最后图里会剩下环,因为环上所有节点的入度都不为0,因此不会入栈。

2.dfs


class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {graph=vector<vector<int>>(numCourses, vector<int>(numCourses));//邻接矩阵vis = vector<int>(numCourses, 0);//visit数组valid = true;//标记是否存在环路vector<int> indegree(numCourses, 0);for (int i = 0; i < prerequisites.size(); i++) {graph[prerequisites[i][1]][prerequisites[i][0]] = 1;}//以上和拓扑排序都是一样的步骤for (int i = 0; i < numCourses; i++) {dfs(i);}return valid;}
private:void dfs(int u) {if (!valid) return;//如果存在环路直接返回if (vis[u] == 1) { valid = false; return; }//如果当前节点正在遍历,则表明存在环路if (vis[u] == 2) return;//如果当前节点已经遍历完成,直接返回vis[u] = 1;//vis置为1,表示当前节点正在dfs中for (int v = 0; v < vis.size(); v++) {//遍历当前节点的临边if (graph[u][v] != 0) {dfs(v);if (!valid) return;//有环直接退出}}vis[u] = 2;//置为2,表示当前节点已经走过了}bool valid;vector<int> vis;vector<vector<int>> graph;
};

关键点在于vis数组的值有1和2的区分

画图解释,设1代表蓝色,2代表红色

从0出发,进行一次dfs,假设路径是0-1-3-4,那么最后1,3,4会变成红色,0还是蓝色

之后dfs会走2这条路

走到2后,会再次调用dfs(3),但是因为

if (vis[u] == 2) return;//如果当前节点已经遍历完成,直接返回

所以valid还是true;

如果是有环路的情况,从0出发进行一次dfs

走到2后会再次调用dfs(0),而

if (vis[u] == 1) { valid = false; return; }//如果当前节点正在遍历,则表明存在环路

所以有环路。

相关文章:

力扣207.课程表

你这个学期必须选修 numCourses 门课程&#xff0c;记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出&#xff0c;其中 prerequisites[i] [ai, bi] &#xff0c;表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如…...

十五届web模拟题整理

模拟赛一期 1.动态的Tab栏 请在 style.css 文件中补全代码。 当用户向下滚动的高度没有超过标题栏&#xff08;即 .heading 元素&#xff09;的高度时&#xff0c;保持 Tab 栏在其原有的位置。当滚动高度超过标题栏的高度时&#xff0c;固定显示 Tab 栏在网页顶部。 /* TODO…...

ubuntu20.04 安裝PX4 1.13

step1_install_depenences.sh #!/bin/bash #install gazebo 11 #install protobuf 3.19.6python3 -m pip install --upgrade pip python3 -m pip install --upgrade Pillow# 將 empy 的版本調整爲3.3.4 pip3 uninstall empy pip3 install empy3.3.4sudo apt-get update sudo ap…...

大型网站系统架构演化

大型网站质量属性优先级&#xff1a;高性能 高可用 可维护 应变 安全 一、单体架构 应用程序&#xff0c;数据库&#xff0c;文件等所有资源都在一台服务器上。 二、垂直架构 应用和数据分离&#xff0c;使用三台服务器&#xff1a;应用服务器、文件服务器、数据服务器 应用服…...

探索Java中的栈:Stack与Deque(ArrayDeque和LinkedList)

文章目录 1. 栈&#xff08;Stack&#xff09;1.1 定义方式1.2 特点1.3 栈的层次结构 2. 双端队列&#xff08;Deque&#xff09;2.1 定义方式及继承关系2.2 特点&#xff1a;2.3 ArrayDeque2.4 LinkedList2.5 Deque 的各种方法2.6 如何选择ArrayDeque和LinkedList 3. 如何选择…...

实践笔记-03 docker buildx 使用

docker buildx 使用 1.启用docker buildx2.启用 binfmt_misc3.从默认的构建器切换到多平台构建器3.1创建buildkitd.toml文件&#xff08;私有仓库是http没有证书的情况下&#xff0c;需要配置&#xff09;3.2创建构建器并使用新创建的构建器 4.构建多架构镜像并推送至harbor仓库…...

【数据结构与算法】之8道顺序表与链表典型编程题心决!

个人主页&#xff1a;秋风起&#xff0c;再归来~ 数据结构与算法 个人格言&#xff1a;悟已往之不谏&#xff0c;知来者犹可追 克心守己&#xff0c;律己则安&#xff01; 目录 1、顺序表 1.1 合并两个有序数组 1.2 原地移除数组中所有的元素va…...

Go 源码之旅-开篇

欢迎来到《Go 源码之旅》专栏&#xff01;在这个专栏中&#xff0c;我们将深入探索 Go 编程语言的内部数据结构的工作原理&#xff0c;一起踏上一段令人兴奋的源码之旅。 我们将一步步解析关键的数据结构底层工作原理以及一些常用框架的设计原理及其源码。 无论你是初学者还是…...

spring的事件推送

本质上是设计模式中的观察者模式。 一、什么是观察者模式 观察者模式是一种行为型设计模式&#xff0c;它定义了一种一对多的依赖关系&#xff0c;当一个对象的状态发生改变时&#xff0c;其所有依赖者都会收到通知并自动更新。 二、什么是spring的事件推送 在 Spring 的事…...

计算机网络—HTTPS协议详解:工作原理、安全性及应用实践

&#x1f3ac;慕斯主页&#xff1a;修仙—别有洞天 ♈️今日夜电波&#xff1a;ヒューマノイド—ずっと真夜中でいいのに。 1:03━━━━━━️&#x1f49f;──────── 5:06 &#x1f504; ◀️ ⏸…...

卫星遥感影像在农业方面的应用及评价

一、引言 随着科技的进步&#xff0c;卫星遥感技术在农业领域的应用越来越广泛。卫星遥感技术以其宏观、快速、准确的特点&#xff0c;为农业生产和管理提供了有力的技术支撑。本文将对卫星遥感在农业方面的应用进行详细介绍&#xff0c;并通过具体案例进行说明。 二、…...

docker pull镜像的时候指定arm平台

指定arm平台 x86平台下载arm平台的镜像包 以mysql镜像为例 docker pull --platform linux/arm64 mysqldocker images查看镜像信息 要查看Docker镜像的信息&#xff0c;可以使用docker inspect命令。这个命令会返回镜像的详细信息&#xff0c;包括其元数据和配置。 docker i…...

如何通过OceanBase V4.2 动态采样优化查询性能

OceanBase v4.2 推出了优化器动态采样的功能&#xff0c;在SQL运行过程中&#xff0c;该功能会收集需要的统计信息&#xff0c;协助优化器制定出更好的执行计划&#xff0c;进一步提升了查询性能。 影响查询性能的因素是什么&#xff1f;为何你的优化器效果不佳&#xff1f; …...

Vue3---基础1(认识,创建)

变化 相对于Vue2&#xff0c;Vue3的变化&#xff1a; 性能的提升 打包大小减少 41% 初次渲染快 55%&#xff0c;更新渲染快133% 内存减少54% 源码的升级 使用 proxy 代替 defineProperty 实现响应式 重写虚拟 DOM 的实现和 Tree-shaking TypeScript Vue3就可以更好的支持TypeSc…...

JAVA集合ArrayList

目录 ArrayList概述 add(element) 用法 add(index, element)用法 remove&#xff08;element&#xff09;用法 remove&#xff08;index&#xff09;用法 get(index)用法 set(index,element) 练习 test1 定义一个集合&#xff0c;添加字符串&#xff0c;并进行遍历&…...

Bitmap OOM

老机器Bitmap预读仍然OOM&#xff0c;无奈增加一段&#xff0c;终于不崩溃了。 if (Build.VERSION.SDK_INT < 21)size 2; 完整代码&#xff1a; Bitmap bitmap; try {//Log.e(Thread.currentThread().getStackTrace()[2] "", surl);URL url new URL(surl);…...

基于深度学习的人脸表情识别系统(PyQT+代码+训练数据集)

基于深度学习的人脸表情识别系统&#xff08;PyQT代码训练数据集&#xff09; 前言一、数据集1.1 数据集介绍1.2 数据预处理 二、模型搭建三、训练与测试3.1 模型训练3.2 模型测试 四、PyQt界面实现 前言 本项目是基于mini_Xception深度学习网络模型的人脸表情识别系统&#x…...

Qt 中的项目文件解析和命名规范

&#x1f40c;博主主页&#xff1a;&#x1f40c;​倔强的大蜗牛&#x1f40c;​ &#x1f4da;专栏分类&#xff1a;QT❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 目录 一、Qt项目文件解析 1、.pro 文件解析 2、widget.h 文件解析 3、main.cpp 文件解析 4、widget.cpp…...

【chatGPT】我:在Cadence Genus软件中,出现如下问题:......【4】

我 在Cadence Genus中&#xff0c;tcl代码为&#xff1a;foreach clk $clk_list{ set clkName [lindex $clk_list 0] set targetFreq [lindex $clk_list 1] set uncSynth [lindex $clk_list 4] set clkPeriod [lindex “%.3f” [expr 1 / $targetFreq]] … } 以上代码出现如下…...

单例模式(Singleton Pattern)在JAVA中的应用

在软件开发中&#xff0c;设计模式是解决特定问题的一种模板或者指南。它们是在多年的软件开发实践中总结出的有效方法。JAVA设计模式广泛应用于各种编程场景中&#xff0c;以提高代码的可读性、可维护性和扩展性。本文将介绍单例模式&#xff0c;这是一种常用的创建型设计模式…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...