பாடநெறி அட்டவணை II - லீட்கோட்


சிரமம் நிலை நடுத்தர
அகலம் முதல் தேடல் ஆழம் முதல் தேடல் வரைபடம் இடவியல் வரிசை

சில படிப்புகளுக்கு முன்நிபந்தனைகள் உள்ள n எண்ணிக்கையிலான படிப்புகளில் (0 முதல் n-1 வரை) நீங்கள் கலந்து கொள்ள வேண்டும். உதாரணமாக: ஜோடி [2, 1] நீங்கள் நிச்சயமாக பாடநெறி 2 ஐக் கொண்டிருக்க வேண்டும் என்பதைக் குறிக்கிறது. மொத்த படிப்புகளின் எண்ணிக்கையையும் அவற்றின் முன்நிபந்தனைகளுடன் படிப்புகளின் பட்டியலையும் குறிக்கும் ஒரு முழு எண் n கொடுக்கப்பட்டுள்ளது. நீங்கள் அனைத்து n படிப்புகளையும் முடிக்கக்கூடிய எந்த வரிசையையும் நாங்கள் திருப்பித் தர வேண்டும். சாத்தியமான பதில் இல்லை என்றால் காலியாக திரும்பவும் வரிசை. பல பதில்கள் இருந்தால், நீங்கள் விரும்பும் ஒன்றைத் திருப்பி விடுங்கள்.

பாடநெறி அட்டவணை II - லீட்கோட்

உதாரணமாக

உள்ளீடு:  4

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

வெளியீடு: [0, 1, 2, 3,]

உள்ளீடு: 2

[[1, 0]]

வெளியீடு: [0, 1,]

அகல முதல் தேடலைப் பயன்படுத்துதல்

பாடநெறி அட்டவணை II க்கான வழிமுறை - லீட்கோட்

  1. படிப்புகளின் எண்ணிக்கையையும், அவற்றின் முன்நிபந்தனைகளையும் சேமிப்பதற்கான 2 டி வரிசை பாடத்தையும் குறிக்கும் ஒரு முழு எண் n ஐத் தொடங்கவும்.
  2. பாடநெறி வரிசை என்பது பூஜ்ய அச்சு வெற்று வரிசை என்றால்.
  3. முன்நிபந்தனைகள் தேவைப்படும் படிப்புகளை சேமிக்க அளவு n இன் வரிசை pCounter ஐ உருவாக்கவும்.
  4. 0 இலிருந்து n-1 க்கு நகர்த்தவும் மற்றும் pCounter ஐ அதிகரிக்கவும் [நிச்சயமாக [i] [0]].
  5. ஒரு திசையன் உருவாக்க வரிசையில் அனைத்து முன்நிபந்தனைகளையும் சேமிக்க.
  6. 0 இலிருந்து n-1 க்கு நகர்த்தி, தற்போதைய குறியீட்டுக்கான pCounter இல் உள்ள மதிப்பு 0 என்பதை சரிபார்க்கவும், வரிசையில் தற்போதைய குறியீட்டைச் சேர்க்கவும்.
  7. அளவு n இன் வரிசை முடிவைத் தொடங்கவும்.
  8. வரிசை காலியாக இல்லாத நிலையில், வரிசையில் உள்ள கடைசி உறுப்பை அகற்றி, முடிவு வரிசை மற்றும் ஒரு முழு எண் c இல் சேமிக்கவும்.
  9. ஒரு உள் சுழற்சியை உருவாக்கி, நிச்சயமாக வரிசையில் [] [1] இல் உள்ள மதிப்பு c குறைப்பு 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 என்பது வரிசைகளின் எண்ணிக்கையைக் குறிக்கிறது மற்றும் N கொடுக்கப்பட்ட பாடநெறி வரிசையில் உள்ள நெடுவரிசைகளின் எண்ணிக்கையைக் குறிக்கிறது.

குறிப்புகள்