पाठ्यक्रम तालिका दोस्रो - LeetCode


कठिनाई तह मध्यम
चौड़ाई पहिलो खोजी गहिराई पहिलो खोजी ग्राफ टोपोलॉजिकल क्रमबद्ध

तपाइँले पाठ्यक्रमहरूको संख्या संख्यामा भाग लिनुपर्दछ (० देखि n-१ सम्म) जहाँ केही पाठ्यक्रमहरूका पूर्व शर्तहरू छन्। उदाहरण को लागी: जोडी [२, १] ले पाठ्यक्रम २ मा भाग लिने प्रतिनिधित्व गर्दछ तपाईंले पाठ्यक्रम १ लिनुपर्‍यो। १. पाठ्यक्रमको कुल संख्या र उनीहरूको पूर्वावलोकनको साथ पाठ्यक्रमहरूको सूचीलाई प्रतिनिधित्व गर्ने पूर्णांक n दिइयो। हामीले कुनै पनि अर्डर फिर्ता गर्न आवश्यक छ जसमा तपाईं सबै एन पाठ्यक्रमहरू पूरा गर्न सक्नुहुनेछ। यदि सम्भव छैन भने खाली जवाफ दिनुहोस् array। यदि त्यहाँ बहु उत्तरहरू छन् जुन तपाईं चाहानुहुन्छ।

पाठ्यक्रम तालिका दोस्रो - LeetCode

उदाहरणका

इनपुट:  4

[[१,०], [२,०], [1,0,१], [2,0.२]]

आउटपुट: [०, १, २,,,]

इनपुट: 2

[[१, ०]]

आउटपुट: [०, १,]

ब्रेडथ पहिलो खोजी प्रयोग गर्दै

पाठ्यक्रम तालिका दोस्रो को लागी एल्गोरिथ्म - LeetCode

  1. पाठ्यक्रम को संख्या र 2D एरे कोर्स को कोर्स र तिनीहरूको पूर्व शर्तहरु को भण्डारण को लागी प्रतिनिधित्व एक पूर्णांक एन शुरू गर्नुहोस्।
  2. यदि पाठ्यक्रम एरे एक शून्य प्रिन्ट खाली एर्रे हो।
  3. पूर्वावलोकन चाहिने पाठ्यक्रमहरू भण्डार गर्न साइज n को एरे pCounter सिर्जना गर्नुहोस्।
  4. ० देखि n-१ मा र बढाउने pCounter मा सार्नुहोस् [कोर्स [i] [०]]।
  5. भेक्टर बनाउनुहोस् लाम सबै आवश्यक चीजहरू भण्डार गर्न।
  6. ० बाट एन -१ मा सार्नुहोस् र जाँच गर्नुहोस् यदि हालको अनुक्रमणिकाको लागि pCounter मा मान ० छ भने, वर्तमान सूचकांक लाममा थप्नुहोस्।
  7. आकार n का एरे परिणाम प्रारम्भ गर्नुहोस्।
  8. जबकि पue्क्ति खाली छैन, प element्क्तिमा अन्तिम तत्व हटाउनुहोस् र यसलाई परिणाम एर्रे र पूर्णांक सीमा भण्डार गर्नुहोस्।
  9. एक भित्री लूप सिर्जना गर्नुहोस् र जाँच गर्नुहोस् यदि [] [१] पाठ्यक्रम एर्रेमा मान घटाव pCounter [कोर्स [i] [०]] बराबर छ कि छैन।
  10. जाँच गर्नुहोस् यदि pCounter [कोर्स [i] [०]] ० जोडी कोर्स हो [i] [०] लाममा।
  11. परिणाम एर्रे प्रिन्ट गर्नुहोस्।

कार्यान्वयन

C ++ कार्यक्रम कोर्स अनुसूची २ - 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,]

कोर्स अनुसूची दोस्रो को लागी जावा कार्यक्रम - 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,]

पाठ्यक्रम अनुसूची २ - LeetCode को लागी जटिलता विश्लेषण

समय जटिलता

O (Q * M) जहाँ Q को आकार छ सदिश वा पूर्व शर्तहरू र एम समावेश गर्ने सूची प r्क्तिहरूको संख्या हो। जुन जोडीहरूको संख्या।

ठाउँ जटिलता

O (M * N) जहाँ M ले पows्क्तिहरूको संख्या दर्शाउँछ र N ले पाठ्यक्रम एर्रेमा स्तम्भहरूको संख्या दर्शाउँछ।

सन्दर्भ