Kurs Cədvəli II - LeetCode

Çətinlik səviyyəsi Mühit
alqoritmlər Genişlik İlk Axtarış kodlaşdırma Dərinlik İlk Axtarış Qrafik müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions Topoloji SortBaxılıb 29

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.

Kurs Cədvəli II - LeetCodePin

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

  1. 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.
  2. Kurs massivi sıfır çap boş bir massivdirsə.
  3. İlkin şərtlərə ehtiyacı olan kursları saxlamaq üçün n ölçülü bir sıra pCounter yaradın.
  4. 0-dan n-1-ə keçin və pCounter [course [i] [0]] artırın.
  5. Bir vektor yaradın queue bütün şərtləri saxlamaq.
  6. 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.
  7. N ölçülü bir sıra nəticəsini başladın.
  8. Növbə boş deyilsə, növbədəki son elementi çıxarın və nəticə massivində və c tam ədədi ilə saxlayın.
  9. 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.
  10. PCounter [course [i] [0]] -nın 0 sıra əlavə etdiyini yoxlayın [i] [0] növbədə.
  11. 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.

References

Şərh yaz

Translate »