د کورس مهالویش II - لیټ کوډ


مشکل کچه منځني
لومړی پراخه پلټنه ژور لومړی لټون ګراف توپوولوژیکي ترتیب

تاسو باید د N شمیر شمیر کورسونو کې برخه واخلئ (له 0 څخه تر N-1 پورې) چیرې چې ځینې کورسونه شرایط لري. د مثال په توګه: جوړه [2 ، 1] د کورس 2 ته حاضر کیږي چې تاسو یې کورس باید 1 کړی وي. د بشپړ کورس n ورکړل شوی چې د کورسونو ټول شمیر استازیتوب کوي او د دوی شرایطو سره د کورسونو لیست وړاندې کوي. موږ اړتیا لرو هر هغه امر بیرته راولو چې تاسو پکې د N ټول کورسونه بشپړ کولی شئ. که امکان شتون نلري نو خالي ځواب ورکړئ سور. که چیرې څو ځوابونه ولرئ کوم یو چې تاسو غواړئ.

د کورس مهالویش II - لیټ کوډ

بېلګه

ننوتل:  4

[[1,0،2,0] ، [3,1،3,2] ، [XNUMX،XNUMX] ، [XNUMX،XNUMX]]

محصول: [0 ، 1 ، 2 ، 3 ،]

ننوتل: 2

[[1 ، 0]]

محصول: [0 ، 1 ،]

د بډر لومړۍ لټون کارول

د کورس مهال ویش II لپاره الګوریتم - لیټ کوډ

  1. د بشپړ کورس n پیل کړئ چې د کورسونو شمیر او د 2D سرې کورس استازیتوب کوي د کورسونو او د دوی شرطونو ساتلو لپاره.
  2. که د کورس صف یو خالي چاپ صف وي.
  3. د کورسونو ذخیره کولو لپاره چې د اړتیا وړ شرایطو ته اړتیا لرئ د اندازې نوی صف لرونکی کاونټر جوړ کړئ.
  4. له 0 څخه تر n-1 او د زیاتوالي pCounter [کورس [i] [0]] ته حرکت وکړئ.
  5. ویکتور جوړ کړئ په ليکه کې د ټولو شرطونو ذخیره کول.
  6. له 0 څخه n-1 ته وخوځیږئ او وګورئ چې د اوسني شاخص لپاره په pCounter کې ارزښت 0 دی ، په قطار کې اوسنی شاخص اضافه کړئ.
  7. د اندازې نري پایله پیل کړئ.
  8. پداسې حال کې چې قطار خالي نه وي وروستی عنصر په قطار کې لرې کړئ او په پایله کې یې زیرمه کړئ او یو بشپړ ک c.
  9. داخلي لوپ رامینځته کړئ او وګورئ چې ایا په [] [1] کې ارزښت په حقیقت کې د c کمولو سره برابر دی [کورس [i] [0]].
  10. وګورۍ چې pCounter [کورس [i] [0]] 0 اضافه کورس دی [i] [0] په قطار کې.
  11. د پایلو سرۍ چاپ کړئ.

تطبیق

C ++ د کورس مهال ویش 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 په ورکړل شوي کورس کې د کالمونو شمیر منع کوي.

ماخذونه