力扣每日一题---207. 课程表

雨点打透心脏的1/2处 2024-03-04 07:50 91阅读 0赞

> Problem: [207. 课程表][207.]  
> ![在这里插入图片描述][f7c795380b784281a7a6c765308a9fc5.png]

#### 文章目录 ####

*  解题方法
 *  复杂度
 *  Code

## 解题方法 ##

> y总的 Topsort 模板题

## 复杂度 ##

*  时间复杂度:

> 添加时间复杂度, 示例：  O ( n ) O(n) O(n)

*  空间复杂度:

> 添加空间复杂度, 示例：  O ( n ) O(n) O(n)

## Code ##

class Solution 
    {
        
        int res = 0;
    public:
        bool canFinish(int n, vector<vector<int>>& pre) 
        {
        
            vector<int> d(n,0);//记录每节课的入度
            for(auto p : pre) d[p[0]]++;//将每节课的入度计入数组里面
            queue<int> q;//运用队列储存入度为零的课程
            for(int i = 0;i < d.size(); ++i)//找到所有出边为0的节点放到队列 q 里面
                if(!d[i]) 
                    q.push(i);
            
            while(!q.empty())
            {
        
                auto t = q.front();//取出对头元素
                q.pop();
                res++;//将与 t 相连的课程的入度减一
                for(int i = 0; i < pre.size(); ++i)
                {
        
                    if(t == pre[i][1])
                    {
        
                        if(--d[pre[i][0]]==0) q.push(pre[i][0]);
                    }
                }
            }
            return res == n;
        }
    };

[207.]: https://leetcode.cn/problems/course-schedule/description/
[f7c795380b784281a7a6c765308a9fc5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/cbdfb05e2d1c423abb332249fba20893.png

发表评论取消回复

表情：

评论列表（有 0 条评论，91人围观）

还没有评论，来说两句吧...

相关阅读

相关力扣每日一题（环形链表II）

力扣每日一题——环形链表II

深碍√TFBOYSˉ_/ 2024年04月23日 15:37/ 0 赞/ 67 阅读

相关力扣每日一题：三数之和

给你一个整数数组 nums ，判断是否存在三元组 \[nums\[i\], nums\[j\], nums\[k\]\] 满足 i != j、i != k 且 j != k ，

古城微笑少年丶/ 2024年03月17日 18:10/ 0 赞/ 44 阅读

相关力扣每日一题---207. 课程表

> Problem: [207. 课程表][207.] > ![在这里插入图片描述][f7c795380b784281a7a6c765308a9fc5.png] 文章目

雨点打透心脏的1/2处/ 2024年03月04日 07:50/ 0 赞/ 92 阅读

相关力扣（LeetCode)每日一题 213. 打家劫舍 II

题目链接[https://leetcode.cn/problems/house-robber-ii/?envType=daily-question&envId=2023-09-

墨蓝/ 2024年03月02日 08:16/ 0 赞/ 42 阅读

相关数据结构：力扣OJ题(每日一练)

![426ad32ad9be41f8b005bec41d93dd09.png][] 本篇主要以理解结构为主！！！题一：用队列实现栈 ![3d8ca42e98

梦里梦外;/ 2023年10月14日 20:24/ 0 赞/ 46 阅读

相关数据结构：力扣OJ题（每日一练）

![9ca51dfa59ca4473919ea735ffaed8b9.png][]题一：有效的括号给定一个只包括 `'('`，`')'`，`'{'`，`'}'`，`'[

清疚/ 2023年10月14日 19:51/ 0 赞/ 42 阅读

相关【力扣每日一题/04】57. 插入区间

> C\中对于list的取值，直接使用：list\[i\] 1. 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdG

r囧r小猫/ 2022年12月19日 06:18/ 0 赞/ 123 阅读

相关【力扣每日一题】925. 长按键入

1. 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG

╰半夏微凉°/ 2022年12月17日 04:30/ 0 赞/ 144 阅读

相关力扣-292题 Nim游戏（C++）- 博弈论+每日一题

题目链接：[https://leetcode-cn.com/problems/nim-game/][https_leetcode-cn.com_problems_nim-gam

本是古典何须时尚/ 2022年09月12日 01:43/ 0 赞/ 203 阅读

相关力扣-165题比较版本号（C++）- 每日一题

题目链接：[https://leetcode-cn.com/problems/compare-version-numbers/][https_leetcode-cn.com_p

墨蓝/ 2022年09月09日 13:48/ 0 赞/ 167 阅读