Πρόγραμμα μαθημάτων II - LeetCode


Επίπεδο δυσκολίας Μέσον
Πρώτη αναζήτηση Πρώτη αναζήτηση βάθους Διάγραμμα Τοπολογική ταξινόμηση

Πρέπει να παρακολουθήσετε n αριθμό μαθημάτων (από 0 έως n-1) όπου ορισμένα από τα μαθήματα έχουν προϋποθέσεις. Για παράδειγμα: το ζεύγος [2, 1] αντιπροσωπεύει για να παρακολουθήσει το μάθημα 2, πρέπει να έχετε λάβει το μάθημα 1. Με δεδομένο έναν ακέραιο αριθμό που αντιπροσωπεύει τον συνολικό αριθμό μαθημάτων και τη λίστα μαθημάτων με τις προϋποθέσεις τους. Πρέπει να επιστρέψουμε οποιαδήποτε σειρά με την οποία μπορείτε να ολοκληρώσετε όλα τα μαθήματα n. Εάν δεν υπάρχει πιθανή απάντηση, επιστρέψτε ένα κενό παράταξη. Εάν υπάρχουν πολλές απαντήσεις, επιστρέψτε ποια θέλετε.

Πρόγραμμα μαθημάτων II - LeetCode

Παράδειγμα

Είσοδος:  4

[[1,0], [2,0], [3,1], [3,2]]

Έξοδος: [0, 1, 2, 3,]

Είσοδος: 2

[[1, 0]]

Έξοδος: [0, 1,]

Χρήση της Πρώτης Αναζήτησης Breadth

Αλγόριθμος για το Πρόγραμμα Μαθήματος II - LeetCode

  1. Αρχικοποιήστε έναν ακέραιο n που αντιπροσωπεύει τον αριθμό των μαθημάτων και ένα 2D σειρά μαθημάτων για την αποθήκευση των μαθημάτων και τις προϋποθέσεις τους.
  2. Εάν ο πίνακας μαθημάτων είναι κενός πίνακας με μηδενική εκτύπωση.
  3. Δημιουργήστε έναν πίνακα pCounter του μεγέθους n για να αποθηκεύσετε τα μαθήματα που χρειάζονται προϋποθέσεις.
  4. Μετακίνηση από 0 στο n-1 και αύξηση pCounter [course [i] [0]].
  5. Δημιουργήστε ένα διάνυσμα ουρά για να αποθηκεύσετε όλες τις προϋποθέσεις.
  6. Μεταβείτε από το 0 στο n-1 και ελέγξτε αν η τιμή στο pCounter για το τρέχον ευρετήριο είναι 0, προσθέστε το τρέχον ευρετήριο στην ουρά.
  7. Αρχικοποιήστε ένα αποτέλεσμα πίνακα μεγέθους n.
  8. Ενώ η ουρά δεν είναι κενή, αφαιρέστε το τελευταίο στοιχείο στην ουρά και αποθηκεύστε το στον πίνακα αποτελεσμάτων και έναν ακέραιο γ.
  9. Δημιουργήστε έναν εσωτερικό βρόχο και ελέγξτε αν η τιμή στο [] [1] στη σειρά μαθημάτων είναι ίση με τη μείωση pCounter [course [i] [0]].
  10. Ελέγξτε αν το pCounter [course [i] [0]] είναι 0 add course [i] [0] στην ουρά.
  11. Εκτυπώστε τον πίνακα αποτελεσμάτων.

Εκτέλεση

Πρόγραμμα C ++ για το Πρόγραμμα Μαθήματος II - 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,]

Πρόγραμμα Java για πρόγραμμα μαθημάτων II - 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,]

Ανάλυση πολυπλοκότητας για το πρόγραμμα μαθημάτων II - LeetCode

Χρόνος πολυπλοκότητας

O (Q * M) όπου Q είναι το μέγεθος του διάνυσμα ή λίστα που περιέχει προαπαιτούμενα και το M είναι ο αριθμός των σειρών, δηλαδή ο αριθμός των συγκεκριμένων ζευγών.

Διαστημική πολυπλοκότητα

Ο (Μ * Ν) όπου το Μ δηλώνει τον αριθμό των σειρών και το Ν υποδηλώνει τον αριθμό των στηλών στη δεδομένη σειρά μαθημάτων

αναφορές