Bəzi kursların ilkin şərtlərinin olduğu n sayda (0-dan n-1-dək) iştirak etməlisiniz. Məsələn: cütlük [2, 1] 2-ci kursda iştirak etməyi təmsil edir. Siz 1-ci kursu keçmiş olmalısınız. Dərslərin ümumi sayını və ilkin şərtləri olan kursların siyahısını əks etdirən bir tam n verilmişdir. Bütün n kurslarını tamamlaya biləcəyiniz hər hansı bir sıranı qaytarmalıyıq. Mümkün cavab yoxdursa, boş bir qayıt array. Birdən çox cavab varsa, hansını istədiyinizi qaytarın.
Mündəricat
misal
Giriş: 4
[[1,0], [2,0], [3,1], [3,2]]
Çıxış: [0, 1, 2, 3,]
Giriş: 2
[[1, 0]]
Çıxış: [0, 1,]
Genişlik İlk Axtarışdan istifadə
Kurs Cədvəli II üçün Alqoritm - LeetCode
- Kursların sayını əks etdirən bir tam ədədi və kursların və onların şərtlərinin saxlanılması üçün 2B sıra kursunu başladın.
- Kurs massivi sıfır çap boş bir massivdirsə.
- İlkin şərtlərə ehtiyacı olan kursları saxlamaq üçün n ölçülü bir sıra pCounter yaradın.
- 0-dan n-1-ə keçin və pCounter [course [i] [0]] artırın.
- Bir vektor yaradın queue bütün şərtləri saxlamaq.
- 0-dan n-1-ə keçin və cari indeks üçün pCounter-dakı dəyərin 0 olub olmadığını yoxlayın, cari indeksi növbəyə əlavə edin.
- N ölçülü bir sıra nəticəsini başladın.
- Növbə boş deyilsə, növbədəki son elementi çıxarın və nəticə massivində və c tam ədədi ilə saxlayın.
- Daxili bir döngə yaradın və kurs massivindəki [] [1] qiymətinin c azalma pCounter [kurs [i] [0]] ilə bərabər olub olmadığını yoxlayın.
- PCounter [course [i] [0]] -nın 0 sıra əlavə etdiyini yoxlayın [i] [0] növbədə.
- Nəticə seriyasını çap edin.
Həyata keçirilməsi
Kurs Cədvəli II üçün C ++ Proqramı - LeetCode
#include <bits/stdc++.h>
using namespace std;
int len = 4;
void findOrder(int n, int course[4][2]){
if(course == NULL){
cout<<"empty array";
}
int pCounter[n];
for(int i=0; i<len; i++){
pCounter[course[i][0]]++;
}
vector<int> queue;
for(int i=0; i<n; i++){
if(pCounter[i]==0){
queue.push_back(i);
}
}
int numNoPre = queue.size();
int result[n];
int j=0;
while(queue.size()!=0){
int c = 0;
if(!queue.empty()){
c = queue.back();
queue.pop_back();
}
result[j++]=c;
for(int i=0; i<len; i++){
if(course[i][1]==c){
pCounter[course[i][0]]--;
if(pCounter[course[i][0]]==0){
queue.push_back(course[i][0]);
numNoPre++;
}
}
}
}
cout<<"[";
for(int i=0; i<n; i++){
cout<<result[i]<<",";
}
cout<<"]";
}
int main(){
int n = 4;
int course[4][2] = {{1,0}, {2,0}, {3,1}, {3,2}};
findOrder(n, course);
return 0;
}
[0,2,1,3,]
Kurs Cədvəli II üçün Java Proqramı - LeetCode
import java.util.*;
class selection{
static int[] findOrder(int n, int[][] course) {
if(course == null){
throw new IllegalArgumentException("empty array");
}
int len = course.length;
if(len == 0){
int[] res = new int[n];
for(int m=0; m<n; m++){
res[m]=m;
}
return res;
}
int[] pCounter = new int[n];
for(int i=0; i<len; i++){
pCounter[course[i][0]]++;
}
LinkedList<Integer> queue = new LinkedList<Integer>();
for(int i=0; i<n; i++){
if(pCounter[i]==0){
queue.add(i);
}
}
int numNoPre = queue.size();
int[] result = new int[n];
int j=0;
while(!queue.isEmpty()){
int c = queue.remove();
result[j++]=c;
for(int i=0; i<len; i++){
if(course[i][1]==c){
pCounter[course[i][0]]--;
if(pCounter[course[i][0]]==0){
queue.add(course[i][0]);
numNoPre++;
}
}
}
}
if(numNoPre==n){
return result;
}
else{
return new int[0];
}
}
public static void main (String[] args) {
int n = 4;
int[][] course = {{1,0}, {2,0}, {3,1}, {3,2}};
int[] result = findOrder(n, course);
System.out.print("[");
for(int i=0; i<result.length; i++){
System.out.print(result[i]+",");
}
System.out.print("]");
}
}
[0,1,2,3,]
Kurs Cədvəli II üçün Mürəkkəblik Təhlili - LeetCode
Zamanın mürəkkəbliyi
O (Q * M) burada Q ölçüsüdür vektor və ya ilkin şərtləri ehtiva edən siyahı və M sətirlərin sayı, yəni verilən cütlərin sayıdır.
Kosmik Mürəkkəblik
O (M * N) burada M satır sayını, N isə verilən kurs massivindəki sütun sayını göstərir.
