資料結構
網路
關係型資料庫管理系統 (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 次瀏覽
