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

【LeetCode207.课程表】以及变式

题目链接

207. 课程表 - 力扣(LeetCode)

实现思路

  1. 用一个二维数组存邻接表,存储的是某个课程的下一门课程的集合;
  2. 用一个数组存储每门课程的入度,也就是如果某门课程需要另外一门先修课程,入度就+1;
  3. 用一个队列,存储当前入度为0的课程,也就是可以修的课程x,每次循环,判断x作为哪些课程的先修课程,那么这门课程的入度-1,如果为0,这门课程也可以修了,加入队列中;
  4. 最后,判断完成的课程数是否和总课程数相等。

代码实现

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {// 构造邻接表vector<vector<int>> edges(numCourses);// 统计入度vector<int> indegree(numCourses, 0);for (int i = 0; i < prerequisites.size(); i++) {int x = prerequisites[i][0];int y = prerequisites[i][1];edges[x].push_back(y);indegree[y]++;}int finish = 0;queue<int> q;for (int i = 0; i < numCourses; i++) {if (!indegree[i]) {finish++;q.push(i);}}while (q.size()) {int x = q.front();q.pop();for (int y : edges[x]) {indegree[y]--;if (!indegree[y]) {finish++;q.push(y);}}}return finish == numCourses;}
};

变式

题目解析

如果已经修好的课程是通过另外一个数组传入的,也就是说,如果仅仅给出修课条件[[1,0]],那么0,1两门课都不能修,但是如果已经修好的课程数组为[0],那么0,1就都可以修。(限制:不存在循环依赖的情况,也就是0的先修课程是1,1的先修课程是0的情况)。

实现思路

  • 在之前的代码上,增加一个判断,就是如果不在已经学习的集合中,那么就算通过邻接图的入度为0,也要手动将入度设置为1。

代码实现

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites, set<int>& learned) {// 构造邻接表vector<vector<int>> edges(numCourses);// 统计入度vector<int> indegree(numCourses, 0);for (int i = 0; i < prerequisites.size(); i++) {int x = prerequisites[i][0];int y = prerequisites[i][1];edges[x].push_back(y);indegree[y]++;}// 新增:只有在learned数组中的课程,入度才是0,否则若原来是0的需要改为1for (int i = 0; i < numCourses; i++) {if (!indegree[i] && !learned.count(i)) {indegree[i] = 1;}}int finish = 0;queue<int> q;for (int i = 0; i < numCourses; i++) {if (!indegree[i]) {finish++;q.push(i);}}while (q.size()) {int x = q.front();q.pop();for (int y : edges[x]) {indegree[y]--;if (!indegree[y]) {finish++;q.push(y);}}}return finish == numCourses;}
};

http://www.lryc.cn/news/583604.html

相关文章:

  • Flutter基础(前端教程⑨-图片)
  • 「macOS 系统字体收集器 (C++17 实现)」
  • JavaScript对象的深度拷贝
  • 全球发展币GDEV:从中国出发,走向全球的数字发展合作蓝图
  • 【RK3568+PG2L50H开发板实验例程】FPGA部分 | DDR3 读写实验例程
  • 【学习笔记】OkHttp源码架构解析:从设计模式到核心实现
  • 【Java】【力扣】【字节高频】3.无重复字符的最长字串
  • 便捷的电脑自动关机辅助工具
  • Deepseek搭建智能体个人知识库
  • yolo8实现目标检测
  • 操作系统核心技术剖析:从Android驱动模型到鸿蒙微内核的国产化实践
  • Day 56
  • EPLAN 电气制图(六):结构盒与设备管理器核心概念(基础知识选看)
  • Linux操作系统之进程间通信:管道概念
  • EF提高性能(查询禁用追踪)(关闭延迟加载)
  • 神经网络初步学习3——数据与损失
  • 如何选择时序数据库:关键因素与实用指南
  • HCIP(综合实验)
  • 备受期待的 MMORPG 游戏《侍魂R》移动端现已上线 Sui
  • 【教程】基于GNN的药物相互作用网络中的链接预测
  • 200nl2sql
  • 安全管理协议(SMP):配对流程、密钥生成与防中间人攻击——蓝牙面试核心考点精解
  • python 在运行时没有加载修改后的版本
  • 自动驾驶决策与规划
  • 华为动态路由配置
  • 【Linux | 网络】socket编程 - 使用UDP实现服务端向客户端提供简单的服务
  • 分库分表之实战-sharding-JDBC水平分库+分表后:查询与删除操作实战
  • Android Notification 通过增加addAction 跳转回Service重新执行逻辑
  • 海信IP501H_GK6323处理器免拆卡刷包和线刷救砖包_当贝纯净版
  • LLM 在预测下一个词的时候是怎么计算向量的,说明详细过程