ਕੋਰਸ ਸ਼ਡਿuleਲ II - LeetCode


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਚੌੜਾਈ ਪਹਿਲੀ ਖੋਜ ਡੂੰਘਾਈ ਪਹਿਲੀ ਖੋਜ ਗਰਾਫ਼ ਟੋਪੋਲੋਜੀਕਲ ਲੜੀਬੱਧ

ਤੁਹਾਨੂੰ ਕੋਰਸਾਂ ਦੀ ਗਿਣਤੀ ਦੇ ਨੰਬਰ (0 ਤੋਂ ਐਨ -1) ਵਿਚ ਸ਼ਾਮਲ ਹੋਣਾ ਪਏਗਾ ਜਿੱਥੇ ਕੁਝ ਕੋਰਸਾਂ ਲਈ ਜ਼ਰੂਰੀ ਸ਼ਰਤ ਹੈ. ਉਦਾਹਰਣ ਦੇ ਲਈ: ਜੋੜਾ [2, 1] ਕੋਰਸ ਵਿੱਚ ਹਾਜ਼ਰੀ ਭਰਨ ਲਈ ਨੁਮਾਇੰਦਗੀ ਕਰਦਾ ਹੈ 2 ਤੁਸੀਂ ਕੋਰਸ ਕੀਤਾ ਹੋਣਾ ਚਾਹੀਦਾ ਹੈ. ਕੋਰਸ ਦੀ ਕੁੱਲ ਸੰਖਿਆ ਅਤੇ ਉਨ੍ਹਾਂ ਦੀਆਂ ਸ਼ਰਤਾਂ ਦੇ ਨਾਲ ਕੋਰਸਾਂ ਦੀ ਸੂਚੀ ਨੂੰ ਦਰਸਾਉਂਦਾ ਪੂਰਨ ਅੰਕ ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ. ਸਾਨੂੰ ਕਿਸੇ ਵੀ ਆਰਡਰ ਨੂੰ ਵਾਪਸ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਜਿਸ ਵਿਚ ਤੁਸੀਂ ਸਾਰੇ n ਕੋਰਸ ਪੂਰੇ ਕਰ ਸਕਦੇ ਹੋ. ਜੇ ਕੋਈ ਸੰਭਵ ਜਵਾਬ ਨਹੀਂ ਹੈ ਤਾਂ ਖਾਲੀ ਵਾਪਸ ਕਰੋ ਐਰੇ. ਜੇ ਇੱਥੇ ਬਹੁਤ ਸਾਰੇ ਉੱਤਰ ਆਉਂਦੇ ਹਨ ਜੋ ਤੁਸੀਂ ਚਾਹੁੰਦੇ ਹੋ.

ਕੋਰਸ ਸ਼ਡਿuleਲ II - LeetCode

ਉਦਾਹਰਨ

ਇੰਪੁੱਟ:  4

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

ਆਉਟਪੁੱਟ: [0, 1, 2, 3,]

ਇੰਪੁੱਟ: 2

[[1, 0]]

ਆਉਟਪੁੱਟ: [0, 1,]

ਬਰੈਥਥ ਫਸਟ ਸਰਚ ਦੀ ਵਰਤੋਂ

ਕੋਰਸ ਸ਼ਡਿuleਲ II - ਐਲਟਕੋਡ ਲਈ ਐਲਗੋਰਿਦਮ

  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 [ਕੋਰਸ [i] [0]] ਦੇ ਬਰਾਬਰ ਹੈ ਜਾਂ ਨਹੀਂ.
  10. ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਪਕਾਉਂਟਰ [ਕੋਰਸ [i] [0]] 0 ਐਡ ਕੋਰਸ ਹੈ [i] [0] ਕਤਾਰ ਵਿੱਚ.
  11. ਨਤੀਜਾ ਐਰੇ ਪ੍ਰਿੰਟ ਕਰੋ.

ਲਾਗੂ

C ++ ਪ੍ਰੋਗਰਾਮ ਕੋਰਸ ਸ਼ਡਿ IIਲ 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ਲ 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,]

ਕੋਰਸ ਸ਼ਡਿuleਲ II - ਲੀਟਕੋਡ ਲਈ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

O (Q * M) ਜਿੱਥੇ ਕਿ. ਦਾ ਅਕਾਰ ਹੈ ਵੈਕਟਰ ਜਾਂ ਲੋੜੀਂਦੀਆਂ ਜ਼ਰੂਰਤਾਂ ਵਾਲੀ ਸੂਚੀ ਅਤੇ ਐਮ ਕਤਾਰਾਂ ਦੀ ਸੰਖਿਆ ਹੈ ਭਾਵ ਦਿੱਤੇ ਗਏ ਜੋੜਿਆਂ ਦੀ ਸੰਖਿਆ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਮ * ਐਨ) ਜਿੱਥੇ ਐਮ ਕਤਾਰਾਂ ਦੀ ਗਿਣਤੀ ਦਰਸਾਉਂਦਾ ਹੈ ਅਤੇ N ਦਿੱਤੀ ਗਈ ਕੋਰਸ ਐਰੇ ਵਿਚ ਕਾਲਮਾਂ ਦੀ ਸੰਖਿਆ ਦਰਸਾਉਂਦਾ ਹੈ.

ਹਵਾਲੇ