当前位置: 首页 > 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;这是一种常用的创建型设计模式…...

FPGA边缘视觉方案解析:从芯片选型到多传感器融合实战

1. 项目概述&#xff1a;单芯片FPGA嵌入式视觉与融合分析方案 最近在梳理一些老项目的技术文档时&#xff0c;翻到了Altera&#xff08;现在已是Intel PSG的一部分&#xff09;和Eutecus在2015年左右合作推出的一套方案&#xff0c;当时在EE Times上被称作“Single-Chip FPGA-B…...

Docker Desktop 快速搭建本地 Kubernetes 集群:解决镜像拉取与生态集成

1. 项目概述&#xff1a;在本地桌面环境快速搭建K8s生态 如果你是一名开发者或者运维工程师&#xff0c;想在自己的Mac或Windows电脑上快速体验和学习Kubernetes&#xff08;K8s&#xff09;及其周边生态&#xff0c;比如Istio服务网格、Helm包管理器&#xff0c;那么Docker D…...

毕设项目分享 大数据共享单车数据分析与可视化(源码分享)

文章目录 0 前言1 课题背景2 数据清洗3 数据可视化热力图整体特征分布**查看2011-2012间的单车租借情况**天气对于租借数量的影响湿度与温度对于租借数量的影响注册用户与未注册用户 4 总结&#xff1a;5 最后 0 前言 &#x1f525; 这两年开始毕业设计和毕业答辩的要求和难度…...

毕设成品 深度学习安全帽佩戴检测(源码+论文)

文章目录 0 前言&#x1f525;这两年开始毕业设计和毕业答辩的要求和难度不断提升&#xff0c;传统的毕设题目缺少创新和亮点&#xff0c;往往达不到毕业答辩的要求&#xff0c;这两年不断有学弟学妹告诉学长自己做的项目系统达不到老师的要求。为了大家能够顺利以及最少的精力…...

FastGithub终极提速方案:3步让GitHub访问速度翻倍

FastGithub终极提速方案&#xff1a;3步让GitHub访问速度翻倍 【免费下载链接】FastGithub github定制版的dns服务&#xff0c;解析访问github最快的ip 项目地址: https://gitcode.com/gh_mirrors/fa/FastGithub 对于开发者而言&#xff0c;GitHub访问缓慢已经成为日常开…...

别再照搬Zynq教程了!手把手教你为Arty A7-35T配置MicroBlaze的SPI Flash启动(附时钟连接避坑指南)

别再照搬Zynq教程了&#xff01;手把手教你为Arty A7-35T配置MicroBlaze的SPI Flash启动&#xff08;附时钟连接避坑指南&#xff09; 在FPGA开发领域&#xff0c;Zynq系列因其ARMFPGA的异构架构而广受欢迎&#xff0c;网上教程资源也最为丰富。但这也导致了一个常见陷阱——许…...

Python3+bypy实战:给你的服务器加个百度网盘自动备份脚本

Python3bypy实战&#xff1a;构建服务器自动化备份系统 在数据为王的时代&#xff0c;服务器上的关键数据如同数字生命线。想象一下凌晨三点收到数据库崩溃的告警&#xff0c;却发现最后一次备份是两周前的手动快照——这种噩梦般的场景正是自动化备份要消灭的敌人。本文将带你…...

开源硬件测试框架OpenClaw Harness:从GPIO到CI/CD的自动化测试实践

1. 项目概述&#xff1a;一个开源硬件测试框架的诞生最近在折腾一些嵌入式开发和硬件原型项目&#xff0c;发现一个挺普遍的问题&#xff1a;当你手头有一堆传感器、执行器或者自己设计的电路板时&#xff0c;怎么高效、可靠地对它们进行功能测试和性能验证&#xff1f;用万用表…...

TI C2000 DSP入门新姿势:Simulink硬件支持包安装与CCS v10.1.0联调实战记录

TI C2000 DSP开发环境搭建&#xff1a;从Simulink支持包到CCS联调全指南 当第一次打开Matlab准备为C2000 DSP开发算法时&#xff0c;很多人会惊讶地发现&#xff1a;明明安装了CCS和Matlab&#xff0c;却无法直接在Simulink中找到C2000的硬件支持。这不是个例——根据TI官方论坛…...

北京AGG专用配件哪家性价比高

在选择AGG聚砂吸声系统的专用配件时&#xff0c;不少工程方和设计师都会问“北京哪家性价比高”。我的建议是&#xff1a;别只看标价&#xff0c;要看配件与系统的适配度、长期使用的稳定性&#xff0c;以及能否提供及时的技术支持。AGG系统本身是一个完整的声学解决方案&#…...