কোর্সের সময়সূচি দ্বিতীয় - লেটকোড


কাঠিন্য মাত্রা মধ্যম
প্রস্থ প্রথম অনুসন্ধান গভীরতা প্রথম অনুসন্ধান চিত্রলেখ টপোলজিকাল বাছাই

আপনাকে n নম্বর সংখ্যক কোর্সে (0 থেকে এন -1 পর্যন্ত) উপস্থিত থাকতে হবে যেখানে কয়েকটি কোর্সে পূর্বশর্ত রয়েছে। উদাহরণস্বরূপ: জোড় [2, 1] আপনি অবশ্যই কোর্স 2 গ্রহণ করা উচিত অবশ্যই কোর্স 1 এ উপস্থিত হতে পারে XNUMX. আমাদের যে কোনও অর্ডার যাতে আপনি সমস্ত এন কোর্স সম্পন্ন করতে পারেন তা ফিরিয়ে দিতে হবে। যদি কোনও সম্ভাব্য উত্তর না থাকে তবে খালি ফিরে আসুন বিন্যাস। যদি একাধিক উত্তর থাকে তবে আপনি যা চান তা ফেরত দিন।

কোর্সের সময়সূচী II - লেটকোড

উদাহরণ

ইনপুট :  4

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

আউটপুট: [0, 1, 2, 3,]

ইনপুট : 2

[[১, ০]]

আউটপুট: [0, 1,]

প্রস্থের প্রথম অনুসন্ধান ব্যবহার করা

কোর্সের সময়সূচী II এর জন্য অ্যালগরিদম - লেটকোড

  1. কোর্সগুলির সংখ্যা এবং তাদের পূর্বশর্ত সংরক্ষণের জন্য 2 ডি অ্যারে কোর্স উপস্থাপন করে একটি পূর্ণসংখ্যা এন শুরু করুন।
  2. কোর্স অ্যারেটি যদি নাল প্রিন্ট খালি অ্যারে হয়।
  3. পূর্বশর্ত প্রয়োজন এমন কোর্সগুলি সংরক্ষণ করতে আকারের একটি অ্যারে পিনকাউন্টার তৈরি করুন।
  4. 0 থেকে এন -1 এবং ইনক্রিমেন্ট পিকাউন্টারে চলে যান [কোর্স [i] [0]]।
  5. একটি ভেক্টর তৈরি করুন বেণী সমস্ত পূর্বশর্ত সংরক্ষণ করতে।
  6. 0 থেকে n-1 এ সরান এবং বর্তমান সূচকের জন্য pCounter এর মান 0 হয় কিনা তা পরীক্ষা করে সারিতে বর্তমান সূচকটি যুক্ত করুন।
  7. আকার এন এর অ্যারে ফলাফল শুরু করুন।
  8. সারিটি খালি না থাকা অবস্থায় কাতারে শেষ উপাদানটি সরিয়ে ফেলুন এবং ফলাফলের অ্যারে এবং একটি পূর্ণসংখ্যা সি তে সংরক্ষণ করুন।
  9. একটি অভ্যন্তরীণ লুপ তৈরি করুন এবং চেক করুন [] [1] অবশ্যই অ্যারে এর মান সি হ্রাস পয়েন্টের সমান [কোর্স [i] [0]]।
  10. PCounter [অবশ্যই [i] [0]] 0 জোড় কোর্স [i] [0] সারি রয়েছে কিনা তা পরীক্ষা করুন।
  11. ফলাফল অ্যারে মুদ্রণ করুন।

বাস্তবায়ন

সি ++ প্রোগ্রাম কোর্সের দ্বিতীয় তফসিলের জন্য - লেটকোড

#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,]

কোর্সের দ্বিতীয় তফসিলের জন্য জাভা প্রোগ্রাম - লেটকোড

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 এর জন্য জটিলতা বিশ্লেষণ - লেটকোড

সময় জটিলতা

O (Q * M) যেখানে Q এর আকার ভেক্টর বা পূর্বশর্ত এবং এম সমন্বিত তালিকাটি সারিগুলির সংখ্যা অর্থাৎ প্রদত্ত জোড়াগুলির সংখ্যা।

স্পেস জটিলতা ity

ও (এম * এন) যেখানে এম সারিগুলির সংখ্যা চিহ্নিত করে এবং এন প্রদত্ত কোর্স অ্যারেটিতে কলামগুলির সংখ্যা বোঝায়।

তথ্যসূত্র