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

Leetcode 课程表

在这里插入图片描述
这段代码的算法思想是基于**深度优先搜索(DFS)**来检测图中的环路,从而判断是否可以完成所有课程。具体来说,我们将每门课程和它的先修关系视为一个有向图,问题的核心就是判断这个有向图中是否存在环路。如果有环路,则说明有课程之间存在相互依赖的关系,导致无法完成所有课程;如果没有环路,则说明可以按顺序完成所有课程。

代码思路解析:

  1. 图的表示

    • 使用邻接表(adjList)表示图,adjList[i]存储的是课程 i 的所有后续课程,即要先完成 i 才能完成的课程列表。
    • 遍历 prerequisites 数组,为每个先修关系 [a, b],在 adjList[b] 中添加 a,表示完成课程 b 是课程 a 的前置条件。
  2. 节点访问状态(visitState 数组)

    • visitState[i] 用于记录每门课程的访问状态:
      • 0 表示未访问,
      • 1 表示正在访问(即当前 DFS 路径上),
      • 2 表示已完全访问(即 DFS 已处理完该节点及其所有后续节点)。
    • 这种状态设置的目的是为了检测环路,如果在 DFS 中再次访问到一个状态为 1 的节点,就说明存在环路。
  3. DFS 检测环路

    • 对每一门课程执行 DFS。如果当前课程状态是 1,表示存在环路,返回 false
    • 如果当前课程状态是 2,表示该课程已经处理完成,不存在环路,可以直接返回当前课程节点判断的 true
    • 否则,将当前课程状态设为 1,然后递归处理所有后续课程。
    • 在递归完成后,将当前课程状态设为 2,表示该课程已经完全访问完毕,未检测到环路。
  4. 返回结果

    • 如果在任何一次 DFS 中检测到环路,立即返回 false
    • 如果所有课程都能被成功访问且无环路,返回整体结果的 true,表示可以完成所有课程。

复杂度分析:

  • 时间复杂度O(V + E),其中 V 是课程数量,E 是先修关系数量。我们需要遍历所有课程和所有先修关系。
  • 空间复杂度O(V + E),用于存储图的邻接表以及访问状态数组。

总结:

这个算法的核心在于将问题转换为图中的环检测问题。通过使用 DFS 并结合访问状态来检测环路,我们可以有效判断课程计划是否可行。

java 代码

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {//首先构建有向图的存储List<List<Integer>> adjList = new ArrayList<>();for(int i = 0; i < numCourses; ++i) {adjList.add(new ArrayList<>());}for(int[] prerequisite : prerequisites) {adjList.get(prerequisite[1]).add(prerequisite[0]);}//然后DFS过程, 首先创建访问状态数组//0代表尚未访问过,1代表访问转换后的状态,2代表当前节点及其所有相邻节点都不存在环int[] visitState = new int[numCourses];for(int i = 0; i < numCourses; ++i) { //每个图节点(课程)进行dfs过程if(!dfs(i, adjList, visitState)) { //dfs()返回false,当存在环时return false;}}return true;}private boolean dfs(int course, List<List<Integer>> adjList, int[] visitState) {if(visitState[course] == 1) {return false;}if(visitState[course] == 2) {return true; //这里返回的true代表的是当前课程节点不存在冲突,而不是所有课程都不存在冲突} //说明当前课程节点的访问状态是0,尚未被访问过//访问当前节点,将其访问状态改变visitState[course] = 1;for(int nextCourse : adjList.get(course)) { //遍历所有相邻节点if(!dfs(nextCourse, adjList, visitState)) {//如果存在环return false;}} //执行到这里说明当前节点的所有邻接节点都不存在环//更新节点访问状态, 2代表当前节点及其所有相邻节点都不存在环visitState[course] = 2;return true;}
}

相关文章:

Leetcode 课程表

这段代码的算法思想是基于**深度优先搜索&#xff08;DFS&#xff09;**来检测图中的环路&#xff0c;从而判断是否可以完成所有课程。具体来说&#xff0c;我们将每门课程和它的先修关系视为一个有向图&#xff0c;问题的核心就是判断这个有向图中是否存在环路。如果有环路&am…...

Java面试经典 150 题.P55. 跳跃游戏(009)

本题来自&#xff1a;力扣-面试经典 150 题 面试经典 150 题 - 学习计划 - 力扣&#xff08;LeetCode&#xff09;全球极客挚爱的技术成长平台https://leetcode.cn/studyplan/top-interview-150/ 题解&#xff1a; class Solution {public boolean canJump(int[] nums) {int…...

登录的时候密码使用crypto-js加密解密

首先要下载插件 npm install crypto-js 然后新建一个js文件 crypto.js // 导入 CryptoJS 模块 import CryptoJS from crypto-js; const secretKey"pZsgDSvzaeHWDkhLDxvrrrYvBlAsIHmZ";//一般是后端提供的 /*** description: 加解密函数* param {*} data 需要加密的数…...

LLM大模型部署实战指南:部署简化流程

LLM大模型部署实战指南:Ollama简化流程,OpenLLM灵活部署,LocalAI本地优化,Dify赋能应用开发 1. Ollama 部署的本地模型(🔺) Ollama 是一个开源框架,专为在本地机器上便捷部署和运行大型语言模型(LLM)而设计。,这是 Ollama 的官网地址:https://ollama.com/ 以下是其…...

24年10月Google Play政策更新通知

今天gmail邮箱里收到了google play最新的政策更新通知&#xff0c;这次的通知对于我来说&#xff0c;影响不大&#xff0c;邮件内容主要分为三部分。 一、政策更新部分 这里更新的政策只有医疗功能相关的。针对健康和医疗应用增加了最新的医疗指南和免责声明要求&#xff0c;并…...

玄机-应急响应- Linux入侵排查

一、web目录存在木马&#xff0c;请找到木马的密码提交 到web目录进行搜索 find ./ type f -name "*.php" | xargs grep "eval(" 发现有三个可疑文件 1.php看到密码 1 flag{1} 二、服务器疑似存在不死马&#xff0c;请找到不死马的密码提交 被md5加密的…...

数据驱动业务中的BDS对账班牛返款表集成方案

数据驱动业务中的BDS对账班牛返款表集成方案 BDS对账班牛返款表_update&#xff1a;班牛数据集成到MySQL的技术实现 在数据驱动的业务环境中&#xff0c;如何高效、准确地将分散在不同系统中的数据进行整合&#xff0c;是每个企业面临的重要挑战。本文将分享一个具体的技术案例…...

【Kubernetes实战】三、资源组件Namespace、Pod、Label、Deployment、Service概述。

目录 1. Namespace1) namespace作用2) namespace资源的具体操作 2. Pod1) Pod概述2) Pod资源的具体操作 3. Label1) Label概述2) Label资源的具体操作 4. Deployment1) Deployment概述2) Deployment控制器的具体操作 5. Service1) Service概述2) Service资源的具体操作 1. Name…...

去中心化的模型训练

去中心化的模型训练&#xff08;Decentralized Model Training&#xff09;是一种不依赖单一中心服务器或数据存储中心&#xff0c;而是在多个节点&#xff08;如设备或数据拥有者&#xff09;上进行联合训练的方法。这种训练模式可以更好地保护数据隐私、降低数据传输成本&…...

Arthas调试线上代码技巧

1、Arthas概述 官网地址&#xff1a;https://arthas.aliyun.com/ 下载地址&#xff1a;https://arthas.aliyun.com/arthas-boot.jar 使用教程&#xff1a;https://arthas.aliyun.com/doc/quick-start.html Arthas&#xff08;阿尔萨斯&#xff09;是 Alibaba 开源的一款Java诊断…...

QT访问数据库:应用提示Driver not loaded

在QT中运行完全正确错误截图 解决办法1 我用的是MySQL。我把libmysql.dll复制到应用程序的目录下&#xff0c;即可正常访问数据库。 解决办法2 bool open_work_db() {QString info "support drivers:";for (int i0; i<QSqlDatabase::drivers().size(); i){inf…...

支持ANC的头戴式蓝牙耳机,更有小金标认证,QCY H3 Pro体验

平时听音乐、看视频&#xff0c;大家都想获得更悦耳的音质体验&#xff0c;这时候蓝牙耳机就是性价比更高的一种方案&#xff0c;同时因其无线束缚、便携性高的特点&#xff0c;随时拿出来就能用。更不用说如今国产品牌的蓝牙耳机升级迭代速度非常快&#xff0c;百元的价位就可…...

net framework 3.5组件更新失败错误代码0x80072f8f怎样解决

浏览器地址栏输入www.dnz9.com远程解决netframework问题 当遇到.NET Framework 3.5 组件更新失败&#xff0c;错误代码为 0x80072f8f 时&#xff0c;可以尝试以下几种解决方法&#xff1a; 一、检查网络连接和时间设置 网络连接 错误代码 0x80072f8f 通常与网络相关问题有关。首…...

C语言初阶:十一.代码调试技巧

❤欢迎各位大佬访问&#xff1a;折枝寄北-CSDN博客折枝寄北擅长C语言初阶,等方面的知识,折枝寄北关注python,c,java,qt,c语言领域.https://blog.csdn.net/2303_80170533?typeblog❤文章所属专栏https://blog.csdn.net/2303_80170533/category_12794764.html?spm1001.2014.300…...

Jenkins Pipeline 部署总结

Jenkins Pipeline 部署总结 前言 Jenkins Pipeline 是 Jenkins 提供的一套强大的工作流框架&#xff0c;它允许开发者以代码的形式定义整个软件交付过程&#xff0c;从而实现持续集成和持续部署&#xff08;CI/CD&#xff09;。通过 Pipeline&#xff0c;原本独立运行于单个或…...

HTTP的初步了解

目录 前言 一、HTTP协议的基本概念 1.1、请求格式 1.2、响应格式 二、HTTP链接问题 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; HTTP协议是超文本传输协议 HTTP的短连接&#xff1a;建立连接——数据传输——关闭连接 HTTP的长连接&#xff1a;…...

SM单元 硬件

在硬件上&#xff0c;SM&#xff08;Streaming Multiprocessor&#xff09;指的是流式多处理器单元&#xff0c;它是GPU架构中非常重要的组成部分。SM可以看作是GPU的心脏&#xff0c;类似于CPU核心&#xff0c;负责执行并行计算任务。每个SM包含多个流处理器&#xff08;cores…...

如何从CSV、JSON等格式创建DataFrame

在Spark中&#xff0c;你可以使用 SparkSession 从CSV和JSON等格式创建 DataFrame。以下是如何从这两种格式创建 DataFrame 的示例。 1. 从CSV文件创建DataFrame scala// 创建SparkSessionval spark SparkSession.builder().appName("CSV to DataFrame").getOrCrea…...

Java避坑案例 - 线程池错误的混用引发的性能故障分析

文章目录 问题现象问题分析问题修复线程池的混用策略任务类型与线程池配置最佳实践 问题现象 代码使用了线程池异步处理一些内存中的数据&#xff0c;但通过监控发现处理得非常慢&#xff0c;整个处理过程都是内存中的计算不涉及 IO 操作&#xff0c;也需要数秒的处理时间&…...

七种方法助你找到实用且免费的API服务

随着现代互联网的迅猛发展&#xff0c;API&#xff08;应用程序编程接口&#xff09;已成为推动技术创新的核心工具。API使得开发者能够快速实现复杂的功能&#xff0c;如数据分析、自然语言处理、图像识别等&#xff0c;而无需从头编写大量的代码。在这个开放的生态中&#xf…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...