本文主要是介绍Leetcode1462. 课程表 IV,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Every day a Leetcode
题目来源:1462. 课程表 IV
解法1:拓扑排序
代码:
/** @lc app=leetcode.cn id=1462 lang=cpp** [1462] 课程表 IV*/// @lc code=start// 拓扑排序(广度优先搜索)class Solution
{
public:vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>> &prerequisites, vector<vector<int>> &queries){// 邻接矩阵vector<vector<int>> graph(numCourses, vector<int>());// 入度数组vector<int> inDegree(numCourses, 0);vector<vector<bool>> isPre(numCourses, vector<bool>(numCourses, false));// 初始化邻接矩阵和入度数组for (vector<int> &p : prerequisites){int from = p[0], to = p[1];graph[from].push_back(to);inDegree[to]++;}queue<int> q;// 把入度为 0 的节点(即没有前置课程要求)放在队列中for (int i = 0; i < inDegree.size(); i++)if (inDegree[i] == 0)q.push(i);while (!q.empty()){// 每次从队列中获得节点,我们将该节点放在排序的末尾,// 并且把它指向的课程的入度各减 1int u = q.front();q.pop();for (auto &v : graph[u]){// 存在一条 u->v 边isPre[u][v] = true;// 更新所有 i->u->v 的路径for (int i = 0; i < numCourses; i++)isPre[i][v] = isPre[i][v] | isPre[i][u];inDegree[v]--;// 有课程的所有前置必修课都已修完(即入度为 0),// 我们把这个节点加入队列中if (inDegree[v] == 0)q.push(v);}}vector<bool> ans;for (auto &query : queries){int from = query[0], to = query[1];ans.push_back(isPre[from][to]);}return ans;}
};
// @lc code=end
结果:
复杂度分析:
时间复杂度:O(numCourses3),其中 numCourses 为课程数。其中通过计算矩阵 isPre 的时间复杂度为 O(numCourses2×numCourses)=O(numCourses3),构建有向图的复杂度为 O(numCourses+n),处理每一个查询的复杂度为 O(1),共有 m 个查询,所以总的查询时间复杂度为 O(m)。
空间复杂度:O(numCourses2+n),其中 numCourses 为课程数,n 为题目给出的先决条件的数目,主要为构建有向图和矩阵 isPre 的空间开销。
这篇关于Leetcode1462. 课程表 IV的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!