የኮርስ መርሃግብር 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,]

ስፌት የመጀመሪያ ፍለጋን በመጠቀም

ለኮርስ መርሃግብር II ስልተ-ቀመር - LeetCode

  1. ኮርሶችን እና ቅድመ ሁኔታዎቻቸውን ለማከማቸት የ ኮርሶችን ብዛት እና የ 2 ዲ ድርድር ኮርስን የሚወክል አንድ ኢንቲጀር ያስጀምሩ ፡፡
  2. የትምህርቱ ድርድር የከንቱ ህትመት ባዶ ድርድር ከሆነ።
  3. ቅድመ ሁኔታዎችን የሚፈልጓቸውን ኮርሶች ለማከማቸት የመጠን n ድርድር pCounter ይፍጠሩ ፡፡
  4. ከ 0 ወደ n-1 እና ጭማሪ pCounter ውሰድ [ኮርስ [i] [0]]።
  5. ቬክተር ይፍጠሩ ተራ ሁሉንም ቅድመ ሁኔታዎች ለማከማቸት.
  6. ከ 0 ወደ n-1 ውሰድ እና ለአሁኑ መረጃ ጠቋሚ በ pCounter ውስጥ ያለው ዋጋ 0 መሆኑን ያረጋግጡ ፣ የወረፋውን ወቅታዊ መረጃ ጠቋሚ ያክሉ።
  7. የመጠን n ድርድር ውጤት ያስጀምሩ።
  8. ወረፋው ባዶ ባይሆንም በወረፋው ውስጥ የመጨረሻውን ንጥረ ነገር ያስወግዱ እና በውጤቱ ድርድር እና ኢንቲጀር ውስጥ ያከማቹ ፡፡
  9. ውስጣዊ ዑደት ይፍጠሩ እና በ [] [1] ውስጥ በእውነቱ ድርድር ያለው ዋጋ ከ c ቅነሳ 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,]

የጃቫ ፕሮግራም ለኮርስ መርሃግብር 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 ውስብስብነት ትንተና II - LeetCode

የጊዜ ውስብስብነት

ኦ (ጥ * መ) ጥ መጠኑ የት ነው ቬክተር ወይም ቅድመ ሁኔታዎችን እና ኤም የያዘ ዝርዝር የረድፎች ብዛት ማለትም የተሰጡ ጥንዶች ቁጥር ነው።

የቦታ ውስብስብነት

ኦ (ኤም * ኤን) M የረድፎችን ብዛት የሚያመለክት ሲሆን ኤን ደግሞ በተጠቀሰው ኮርስ ድርድር ውስጥ የአምዶች ብዛት ያሳያል።

ማጣቀሻዎች