သင်တန်းအစီအစဉ် II - LeetCode


ခက်ခဲအဆင့် အလယ်အလတ်
အနံပထမရှာဖွေရေး အနက်ရောင်ပထမရှာဖွေမှု သရုပ်ပြဇယား Topological Sort

သင့်အနေဖြင့် n 0 မှ n-1 အထိ n နံပါတ်များကိုတက်ရောက်ရန်လိုအပ်သည်။ ဥပမာအားဖြင့် - pair [2, 1] သည်သင်တန်း ၂ ကိုတက်ရောက်ရန်အတွက်ကိုယ်စားပြုသည်။ သင်ကသင်တန်း ၁ ကိုသင်တက်ရမည်ဖြစ်သည်။ စုစုပေါင်း n ကိုကိုယ်စားပြုသောသင်ခန်းစာစုစုပေါင်းအရေအတွက်နှင့်သင်တန်းများ၏စာရင်းကိုသူတို့လိုအပ်ချက်များနှင့်အတူ။ n n သင်တန်းများအားလုံးကိုသင်ပြီးဆုံးနိုင်သည့်မည်သည့်အစီအစဉ်ကိုမဆိုကျွန်ုပ်တို့ပြန်လည်ပေးပို့ရန်လိုအပ်သည်။ ဖြစ်နိုင်သောအဖြေမရှိပါကအလွတ်တစ်ခုကိုပြန်ပေးပါ အခင်းအကျင်း။ အဖြေမျိုးစုံရှိလျှင်သင်လိုချင်သည့်အရာကိုပြန်ပို့ပါ။

သင်တန်းအစီအစဉ် II - LeetCode

နမူနာ

ထည့်သွင်းမှု -  4

[[၁.၀]၊ [၂.၀]၊ [၃.၁]၊ [၃.၂]]

output: [0, 1, 2, 3,]

ထည့်သွင်းမှု - 2

[[၁၊ ၀]

output: [0, 1,]

Breadth First Search ကိုအသုံးပြုခြင်း

သင်တန်းဇယား II အတွက် Algorithm - LeetCode

  1. ကိန်းဂဏန်းစုစုပေါင်း n ကိုစတင်ခြင်းနှင့်သင်တန်းများနှင့်၎င်းတို့၏လိုအပ်ချက်များကိုသိုလှောင်ခြင်းအတွက် 2D ခင်းကျင်းပြသသည့်သင်တန်းကိုစတင်ပါ။
  2. သင်တန်းခင်းကျင်းတဲ့ null ပုံနှိပ်ခြင်းဗလာခင်းကျင်းသည်ဆိုပါက။
  3. လိုအပ်သောသင်တန်းများသိုလှောင်ရန်အရွယ်အစား n ၏နံပါတ် pCounter တစ်ခုကိုဖန်တီးပါ။
  4. 0 မှ n-1 သို့ရွှေ့။ pCounter [သင်တန်း [i] [0]] ကိုတိုးပါ။
  5. vector တစ်ခုဖန်တီးပါ ဆံပင်ကြိုး အားလုံးလိုအပ်ချက်များကိုသိမ်းဆည်းရန်။
  6. 0 မှ n-1 သို့ရွှေ့။ လက်ရှိညွှန်းကိန်းအတွက် pCounter တန်ဖိုးသည် 0 ဖြစ်မဖြစ်စစ်ဆေးပါ၊ တန်းတွင်လက်ရှိအညွှန်းကိုထည့်ပါ။
  7. အရွယ်အစား n ၏ခင်းကျင်းမှုရလဒ်ကိုစတင်ပါ။
  8. အဆိုပါတန်းစီအချည်းနှီးဖြစ်နေစဉ်တန်းစီအတွက်နောက်ဆုံး element ကိုဖယ်ရှားခြင်းနှင့်ရလဒ်ခင်းကျင်းခြင်းနှင့်တစ်ကိန်းဂဏန်းက c ထဲမှာသိမ်းထားတဲ့။
  9. အတွင်းပိုင်းကွင်းဆက်တစ်ခု ဖန်တီး၍ သင်တန်းခင်းကျင်းမှုအတွင်း [] [1] ရှိတန်ဖိုးသည် pCounter [သင်တန်း [i] [0]] နှင့်တူညီမှုရှိမရှိစစ်ဆေးပါ။
  10. တန်းစီထဲမှာ pCounter [သင်တန်း [i] [0]] 0 င်သင်တန်း [i] [0] လျှင်ဟုတ်မဟုတ်စစ်ဆေးပါ။
  11. ရလဒ်ခင်းကျင်းပုံနှိပ်ပါ။

အကောင်အထည်ဖော်ရေး

သင်တန်းဇယား II အတွက် C ++ အစီအစဉ် - 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 အတွက် Java အစီအစဉ် - LeetCode

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

သင်တန်းအစီအစဉ်ဇယား -၂ အတွက်ရှုပ်ထွေးမှုဆန်းစစ်ခြင်း - LeetCode

အချိန်ရှုပ်ထွေး

အို (မေး * M) ဘယ်မှာမေး၏အရွယ်အစားသည် အားနည်းချက်ကို သို့မဟုတ်လိုအပ်သောစာရင်းနှင့် M သည်အတန်းအရေအတွက်ဖြစ်သောဆိုလိုသည်မှာပေးထားသောအတွဲအရေအတွက်ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (M * N) M သည်အတန်းအရေအတွက်ကိုရည်ညွှန်းပြီး N သည်ပေးထားသောသင်တန်းခင်းကျင်းစာရင်းတွင်ကော်လံအရေအတွက်ကိုဖော်ပြသည်။

ကိုးကား