数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++课程安排 IV
假设我们总共有 n 门课程需要学习，课程从 0 到 n-1 编号。
一些课程可能有直接先修课程，例如，要学习课程 0，我们首先需要学习课程 1，这可以用一对表示：[1,0]。
所以，如果我们有 n 门课程，一个直接先修课程对列表和一个查询对列表。
对于每个查询 queries[i]，你应该找到课程 queries[i][0] 是否是课程 queries[i][1] 的先修课程。最后，我们必须返回一个布尔列表，即给定查询的答案。
我们必须记住，如果课程 a 是课程 b 的先修课程，而课程 b 是课程 c 的先修课程，那么课程 a 也是课程 c 的先修课程。
因此，如果输入类似于 n = 3，prerequisites = [[1,2],[1,0],[2,0]]，queries = [[1,0],[1,2]]，则输出将为 [true,true]
为了解决这个问题，我们将遵循以下步骤 -
N := 110
定义一个数组 ret
定义一个 map in
对于每个元素 it 在 v 中，执行以下操作
将 it[1] 插入到 graph[it[0]] 的末尾
(将 in[it[1]] 增加 1)
定义一个队列 q
初始化 i := 0，当 i < n 时，更新 (将 i 增加 1)，执行以下操作 -
如果 in[i] 等于 0，则 -
将 i 插入到 q 中
定义一个 map idx
初始化 lvl := 1，当 q 不为空时，更新 (将 lvl 增加 1)，执行以下操作 -
sz := q 的大小
当 sz 不为 0 时，每次迭代减少 sz，执行以下操作 -
node := q 的第一个元素
从 q 中删除元素
对于 graph[node] 中的每个元素 it
(将 in[it] 减少 1)
对于 c[node] 中的每个元素 x，执行以下操作
将 x 插入到 c[it] 中
将 node 插入到 c[it] 中
如果 in[it] 等于 0，则 -
将 it 插入到 q 中
对于 x 中的每个元素 it，执行以下操作
将 (it[0] 在 c[it[1]] 中出现的频率) 插入到 ret 的末尾
返回 ret
示例
让我们看看以下实现，以便更好地理解 -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<bool> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
const int N = 110;
class Solution {
public:
vector <int> graph[N];
map <int, set <int>> c;
vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& v, vector<vector<int>>& x) {
vector<bool> ret;
map<int, int> in;
for (auto& it : v) {
graph[it[0]].push_back(it[1]);
in[it[1]]++;
}
queue<int> q;
for (int i = 0; i < n; i++) {
if (in[i] == 0)
q.push(i);
}
map<int, int> idx;
for (int lvl = 1; !q.empty(); lvl++) {
int sz = q.size();
while (sz--) {
int node = q.front();
q.pop();
for (auto& it : graph[node]) {
in[it]--;
for (auto& x : c[node])
c[it].insert(x);
c[it].insert(node);
if (in[it] == 0) {
q.push(it);
}
}
}
}
for (auto& it : x) {
ret.push_back(c[it[1]].count(it[0]));
}
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> prerequisites = {{1,2},{1,0},{2,0}}, queries = {{1,0},{1,2}};
print_vector(ob.checkIfPrerequisite(3, prerequisites, queries));
}输入
3, {{1,2},{1,0},{2,0}}, {{1,0},{1,2}}输出
[1, 1, ]
257 次浏览
