2023-09-09 LeetCode每日一题(课程表)

2023-09-09每日一题

一、题目编号

207. 课程表

二、题目链接

点击跳转到题目位置

三、题目描述

你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。

  • 例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1 。
    请你判断是否可能完成所有课程的学习?如果可以,返回 true ;否则,返回 false 。

示例 1:
在这里插入图片描述
示例 2:
在这里插入图片描述
提示:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[i] 中的所有课程对 互不相同

四、解题代码

class Solution {#define maxn 100010vector<int> edges[maxn];int deg[maxn];void addEdge(int v, int u){edges[u].push_back(v);++deg[v];}public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {int i;int n=prerequisites.size();queue<int> q;int hash[maxn];memset(hash,0,sizeof(hash));for(i=0;i<numCourses;i++){edges[i].clear();deg[i] = 0;hash[i] = 0;}for(int i=0;i<n;i++){addEdge(prerequisites[i][1],prerequisites[i][0]);}int x=numCourses;for(int i=0;i<numCourses;i++){if(!deg[i]){q.push(i);x--;hash[i]=1;}}while( !q.empty() ){int u=q.front();q.pop();for(int i=0;i<edges[u].size();i++){int v=edges[u][i];deg[v]--;if(hash[v]==0 && deg[v]==0){q.push(v);hash[v]=1;x--;}}      }if(x==0){return true;}return false;}
};

五、解题思路

(1) 使用拓扑排序可以很轻松的的解决这道题目。这也是拓扑排序的一道经典例题。

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

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

相关文章

初次安装Pytorch过程

第一次安装Pytorch&#xff0c;刚开始安装的时候装错了CUDA的版本号 这里最高支持12.2.138&#xff0c; 但是我装了一个12.2.140的CUDA&#xff0c;导致不兼容我在测试时发现 import torch# if torch.cuda.is_available(): # print("GPU可用") # else: # p…

Kotlin(五) 循环语句

目录 For循环 关键字 until step downTo Java中主要有两种循环语句&#xff1a;while循环和for循环。而Kotlin也提供了while循环和for循环&#xff0c;其中while循环不管是在语法还是使用技巧上都和Java中的while循环没有任何区别&#xff0c;因此我们就直接跳过不进行讲解…

记LGSVL本地编译记录

主要的编译参考来着官方文件 Unity安装 安装unity hub 安装2020.3.3f1在unity hub上 但是我发现没有2020.3.3f1&#xff0c;只有2020.3.3f1c1&#xff0c;其实c1就是中国版&#xff0c;没有什么影响 GIT安装 安装GIT安装Git LFS验证git-lfs(输出Git LFS initialized就&am…

嵌入式Linux驱动开发(LCD屏幕专题)(三)

1. 硬件相关的操作 LCD驱动程序的核心就是&#xff1a; 分配fb_info设置fb_info注册fb_info硬件相关的设置 硬件相关的设置又可以分为3部分&#xff1a; 引脚设置时钟设置LCD控制器设置 2. 在设备树里指定LCD参数 framebuffer-mylcd {compatible "100ask,lcd_drv&qu…

运维学习之部署Alertmanager-0.24.0

参考《监控系统部署prometheus基本功能》先完成prometheus部署。 参考《运维学习之采集器 node_exporter 1.3.1安装并使用》安装node_exporter。 下载 nohup wget https://github.com/prometheus/alertmanager/releases/download/v0.24.0/alertmanager-0.24.0.linux-amd64.ta…

oled或数码管点阵的字模矩阵的原理讲解

通过取模软件得到的T字符的矩阵分析 字模选项中常用的设置的意义&#xff1a; **字宽和字高&#xff1a;**显示字符能够使用的长宽灯数量&#xff0c;也可以理解为像素 **点阵格式&#xff1a;**需要考虑实际焊接电路。阴码&#xff1a;灯共阴极&#xff0c;控制器输出高电位&…

NFS文件共享系统(K8S)

概述 部署NFS文件共享服务&#xff0c;为Kubernetes提供NFS共享做准备 步骤 安装软件 yum -y install nfs-utils 配置NFS(exports) 编辑 /etc/exports 文件。每一行代表一个共享目录&#xff0c;描述目录如何共享 编写规则&#xff1a; # <共享目录> [客户端1 选项…

【List篇】ArrayList 的线程不安全介绍

ArrayList 为什么线程不安全&#xff1f; 主要原因是ArrayList是非同步的,没有同步机制,并且其底层实现是基于数组&#xff0c;而数组的长度是固定的。当对 ArrayList 进行增删操作时&#xff0c;需要改变数组的长度&#xff0c;这就会导致多个线程可能同时操作同一个数组&…

222. 完全二叉树的节点个数

题目链接&#xff1a; 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 我的想法&#xff1a; 递归法 万金油--层次遍历法 当然上面两中都是笨方法&#xff0c;就算不是完全二叉树也能算&#xff0c;没有用到完全二叉树的特性。 我的代码&#xff1…

【个人博客系统网站】注册与登录 · 加盐加密验密算法 · 上传头像

【JavaEE】进阶 个人博客系统&#xff08;3&#xff09; 文章目录 【JavaEE】进阶 个人博客系统&#xff08;3&#xff09;1. 加盐加密验密算法原理1.1 md5加密1.2 md5验密1.3 md5缺漏1.4 加盐加密1.5 后端的盐值拼接约定1.6 代码实现1.6.1 加密1.6.2 验密1.6.3 测试 2. 博客…

MySQL的常用术语

目录 1.关系 2.元组 3.属性 MySQL从小白到总裁完整教程目录:https://blog.csdn.net/weixin_67859959/article/details/129334507?spm1001.2014.3001.5502 1.关系 前面的博客有说到,MySQL是一款关系型数据库管理软件,一个关系就是 一张二维表(表) 我想大家都知道表格怎么…

sqli-labs闯关

目录 less-01: less-08: less-19: less-20: 项目地址—Github 使用HackBar插件 less-01: Sqli-labs前20关均为数字型注入 Sqli-labs前四关较为类似以less-01为模板 将网址导入HackBar中&#xff1a; 1.根据提示&#xff0c;输入http://127.0.0.1/sqli/Less-1/?id1查看…

算法[动态规划]---买卖股票最佳时机

1、题目&#xff1a; 给你一个整数数组 prices&#xff0c;其中 prices[i] 表示某支股票第 i 天的价格。 在每一天&#xff0c;你可以决定是否购买和/或出售股票。你在任何时候最多只能持一股股票。你也可以先购买&#xff0c;然后在同一天出售。 返回你能获得的最大利润 。 2…

9. xaml ComboBox控件

1.运行图像 2.运行源码 a.Xaml源码 <Grid Name="Grid1"><!--IsDropDownOpen="True" 默认就是打开的--><ComboBox x:Name="co

完成Centos上使用SSH公钥进行免密上传文件到gitee的步骤后,测试免密推送到gitee的时候还是需要输入邮箱和密码

如果你已经按照正确的步骤设置了SSH公钥并进行了免密测试&#xff0c;但仍然需要输入邮箱地址和密码才能推送到gitee&#xff0c;那么可能有以下几种原因&#xff1a; 您可能没有使用SSH URL来推送代码。请确保您使用的是SSH URL而不是HTTPS URL来推送代码。您可以使用命令 gi…

电商3D资产优化管线的自动化

如果你曾经尝试将从 CAD 程序导出的 3D 模型上传到 WebGL 或 AR 服务&#xff0c;那么可能会遇到最大文件大小、永无休止的进度条和糟糕的帧速率等问题。 为了创作良好的在线交互体验&#xff0c;优化 3D 数据的大小和性能至关重要。 这也有利于你的盈利&#xff0c;因为较小的…

GDB用法(三)

预备 测试代码参照GDB用法(二) 命令历史 可以将命令历史保存到文件中 (show history) 展示当前gdb中history的设置信息 设置expansion (set history expansion) 打开历史扩展 能使用历史处理命令对历史数据进行处理, 暂不细究 (show history expansion) 展示历史扩展配置…

什么是原生IP?原生IP与住宅IP有何区别?

相信许多做跨境的都会接触到IP代理&#xff0c;比如电商平台、社媒平台、收款平台等等&#xff0c;都会检测IP。那也会经常听到一些词汇&#xff1a;原生IP、住宅IP&#xff0c;这两者之间有什么区别呢&#xff1f;什么业务需要用到呢&#xff1f;接下来带大家具体了解一下。 什…

软件架构设计(十三) 构件与中间件技术

中间件的定义 其实中间件是属于构件的一种。是一种独立的系统软件或服务程序,可以帮助分布式应用软件在不同技术之间共享资源。 我们把它定性为一类系统软件,比如我们常说的消息中间件,数据库中间件等等都是中间件的一种体现。一般情况都是给应用系统提供服务,而不是直接…

Jenkins介绍

Jenkins介绍 持续集成、持续部署的工具很多&#xff0c;其中Jenkins是一个开源的持续集成平台。 Jenkins涉及到将编写完毕的代码发布到测试环境和生产环境的任务&#xff0c;并且还涉及到了构建项目等任务。 Jenkins需要大量的插件保证工作&#xff0c;安装成本较高&#xff0…