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

雨点打透心脏的1/2处 2024-03-04 07:50 107阅读 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 条评论，107人围观）

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

相关阅读

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

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

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

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

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

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

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

题目链接[https://leetcode.cn/problems/house-robber/][https_leetcode.cn_problems_house-robber

悠悠/ 2024年03月03日 09:01/ 0 赞/ 110 阅读

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

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

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

相关 LeetCode - 207 课程表

目录题目来源题目描述示例提示题目解析算法源码 -------------------- 题目来源 [207. 课程表 - 力扣（LeetCod

亦凉/ 2023年09月23日 14:54/ 0 赞/ 73 阅读

相关 207. 课程表

题目： [207. 课程表][207.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text

- 日理万妓/ 2023年02月23日 08:53/ 0 赞/ 34 阅读

相关 Leetcode 207. 课程表

Leetcode 207. 课程表 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn.co

浅浅的花香味﹌/ 2023年02月14日 03:01/ 0 赞/ 45 阅读

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

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

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

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

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

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

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

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

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