కోర్సు షెడ్యూల్ II - లీట్‌కోడ్


కఠినత స్థాయి మీడియం
వెడల్పు మొదటి శోధన లోతు మొదటి శోధన గ్రాఫ్ టోపోలాజికల్ క్రమబద్ధీకరణ

మీరు కొన్ని కోర్సులకు (0 నుండి n-1 వరకు) హాజరు కావాలి, ఇక్కడ కొన్ని కోర్సులు అవసరం. ఉదాహరణకు: జత [2, 1] కోర్సు 2 కి హాజరు కావడానికి ప్రాతినిధ్యం వహిస్తుంది. మీరు కోర్సు 1 తీసుకోవాలి. మొత్తం కోర్సుల సంఖ్యను మరియు వాటి అవసరాలతో కూడిన కోర్సుల జాబితాను సూచించే పూర్ణాంకం n ఇవ్వబడింది. మీరు అన్ని n కోర్సులను పూర్తి చేయగల ఏ క్రమాన్ని అయినా తిరిగి ఇవ్వాలి. సాధ్యం సమాధానం లేకపోతే ఖాళీగా ఇవ్వండి అమరిక. బహుళ సమాధానాలు ఉంటే మీకు కావలసినదాన్ని తిరిగి ఇవ్వండి.

కోర్సు షెడ్యూల్ II - లీట్‌కోడ్

ఉదాహరణ

ఇన్పుట్:  4

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

అవుట్పుట్: [0, 1, 2, 3,]

ఇన్పుట్: 2

[[1, 0]]

అవుట్పుట్: [0, 1,]

వెడల్పు మొదటి శోధనను ఉపయోగించడం

కోర్సు షెడ్యూల్ II కోసం అల్గోరిథం - లీట్‌కోడ్

  1. కోర్సుల సంఖ్యను సూచించే పూర్ణాంక n ను ప్రారంభించండి మరియు కోర్సులు మరియు వాటి అవసరాలను నిల్వ చేయడానికి 2D శ్రేణి కోర్సును ప్రారంభించండి.
  2. కోర్సు శ్రేణి శూన్య ముద్రణ ఖాళీ శ్రేణి అయితే.
  3. ముందస్తు అవసరాలు అవసరమయ్యే కోర్సులను నిల్వ చేయడానికి పరిమాణం n యొక్క శ్రేణి pCounter ను సృష్టించండి.
  4. 0 నుండి n-1 మరియు ఇంక్రిమెంట్ pCounter [కోర్సు [i] [0]] కి తరలించండి.
  5. వెక్టర్ సృష్టించండి క్యూ అన్ని అవసరాలను నిల్వ చేయడానికి.
  6. 0 నుండి n-1 కి తరలించి, ప్రస్తుత సూచిక కోసం pCounter లోని విలువ 0 అని తనిఖీ చేయండి, క్యూలో ప్రస్తుత సూచికను జోడించండి.
  7. పరిమాణం n యొక్క శ్రేణి ఫలితాన్ని ప్రారంభించండి.
  8. క్యూ ఖాళీగా లేనప్పటికీ, క్యూలోని చివరి మూలకాన్ని తీసివేసి, ఫలిత శ్రేణిలో మరియు పూర్ణాంకంలో నిల్వ చేయండి.
  9. లోపలి లూప్‌ను సృష్టించండి మరియు కోర్సు శ్రేణిలో [] [1] వద్ద ఉన్న విలువ సి తగ్గింపు pCounter [కోర్సు [i] [0]] కు సమానంగా ఉందో లేదో తనిఖీ చేయండి.
  10. PCounter [course [i] [0]] క్యూలో 0 యాడ్ కోర్సు [i] [0] ఉందో లేదో తనిఖీ చేయండి.
  11. ఫలిత శ్రేణిని ముద్రించండి.

అమలు

కోర్సు షెడ్యూల్ II కోసం సి ++ ప్రోగ్రామ్ - లీట్‌కోడ్

#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 కోసం జావా ప్రోగ్రామ్ - లీట్‌కోడ్

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 యొక్క పరిమాణం వెక్టర్ లేదా అవసరం ఉన్న జాబితా మరియు M అనేది అడ్డు వరుసల సంఖ్య, ఇచ్చిన జంటల సంఖ్య.

అంతరిక్ష సంక్లిష్టత

O (M * N) ఇక్కడ M వరుసల సంఖ్యను సూచిస్తుంది మరియు N ఇచ్చిన కోర్సు శ్రేణిలోని నిలువు వరుసల సంఖ్యను సూచిస్తుంది.

ప్రస్తావనలు