Stack Permutations (Array တစ်ခုသည်အခြားတစ်ခု၏ stack permutation ဟုတ်မဟုတ်စစ်ဆေးပါ)


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ လေးကစ်
ပေါင်းစပ် ဆံပင်ကြိုး စုပုံထား

ပြProbleနာဖော်ပြချက်

ပြStနာက“ Stack Permutations (array တစ်ခုသည်အခြားတစ်ခု၏ stack permutation ဟုတ်မဟုတ်စစ်ဆေးပါ)” ပြyouနာကသင့်အားအရွယ်အစား n ၏ [] နှင့် b [] နှစ်ခု Array များပေးထားသည်ဟုဖော်ပြသည်။ Array တစ်ခု၏ element အားလုံးသည်ထူးခြားသည်။ ပေးထားသောခင်းကျင်းခြင်း [b] သည်ပေးထားသောခင်းကျင်းခြင်း၏ [stack permutation] ဟုတ်မဟုတ်စစ်ဆေးရန် function တစ်ခုကိုဖန်တီးပါ။

Stack Permutations (Array တစ်ခုသည်အခြားတစ်ခု၏ stack permutation ဟုတ်မဟုတ်စစ်ဆေးပါ)

နမူနာ

a[ ] = {1, 2, 3}

b[ ] = {2, 1, 3}
Yes

ရှင်းလင်းချက် - ပထမနှင့် ၁ ကိုပထမသို့တွန်းပါ။ ထိုအခါသူတို့ကို stack ကနေ pop ။ ပြီးရင် 1 ကိုနှိပ်ပြီးတော့ pop 2 ကိုနှိပ်လိုက်ပါ။ ဒါကြောင့်ထွက်ပေါ်လာတဲ့ sequence က 3, 3 နဲ့တူတယ်။ အဲဒါကကျွန်တော်တို့ရဲ့ဒုတိယ array ပါ။

a[ ] = {1, 2, 3}

b[ ] = {3, 1, 2}
No

ရှင်းလင်းချက် - ဒုတိယခင်းကျင်းမှုကိုဖြစ်ပေါ်စေသော push နှင့် pop အစီအစဉ်များမရှိပါ။ ထို့ကြောင့်အဖြေမှာ NO ဖြစ်သည်။

algorithm

  1. နှစ်ခုစတင်ပါ Array များ အရွယ်အစား of တစ် [] နှင့်ခ [] ။
  2. နှစ်ခုလက်ခံသော stack permutation ကိုစစ်ဆေးရန် function တစ်ခုကိုဖန်တီးပါ ကိန်း ၎င်းကို parameter များအနေဖြင့် Array နှင့် Array ၏အရွယ်အစား။
  3. ထို့နောက်တစ် ဦး ဖန်တီးပါ ဆံပင်ကြိုး ကိန်းအမျိုးအစား၏ဒေတာဖွဲ့စည်းပုံ။
  4. Array ကိုဖြတ်ပြီးဖြတ်သန်းသွားပြီး၊ တန်းစီထဲမှ array [] တစ်ခု၏ element အားလုံးကိုတွန်းထည့်ပါ။
  5. ထို့နောက်ဒုတိယကိန်းတန်းဒေတာဖွဲ့စည်းပုံကိုကိန်းအမျိုးအစားကိုဖန်တီးပါ။
  6. array b ကို ဖြတ်၍ ဖြတ်သန်းပြီး၊ တန်းစီထဲရှိ array b ၏အစိတ်အပိုင်းအားလုံးကိုတွန်းထည့် / ထည့်ပါ။
  7. အလားတူပင် a ကိုဖန်တီးပါ စုပုံထား ကိန်းအမျိုးအစား၏ဒေတာဖွဲ့စည်းပုံ။
  8. ပထမတန်း၏အရွယ်အစားသည် 0. မဟုတ်ပါကဖြတ်သန်းသွားပါ။ သုညကိန်းတစ်ခု ဖန်တီး၍ element ကို၎င်းပထမတန်း၏ရှေ့တွင်သိုလှောင်ပြီးပထမတန်းမှ pop / remove လုပ်ပါ။
  9. integer variable ၏တန်ဖိုးသည်ဒုတိယတန်း၏ရှေ့ဖက်ရှိ element နှင့်တန်းတူမဟုတ်ကြောင်းကိုစစ်ဆေးပါ၊ stack ထဲတွင် integer variable ကိုတွန်း / ထည့်ပါ။
  10. ကျန်တဲ့အပိုင်းကတော့ element ရဲ့ဒုတိယတန်းရဲ့ရှေ့ပိုင်းမှာပါ။
  11. stack ၏အရွယ်အစားသည် 0. မဟုတ်ပါကထပ်မံလှည့်ပါ။ stack ၏ထိပ်ရှိ element သည်ဒုတိယတန်း၏ရှေ့ဖက်ရှိ element နှင့်တန်းတူလား၊ ဒုတိယတန်း၏ရှေ့တွင် element နှင့် pop / ဖယ်ပါ။ အဆိုပါ stack ၏ထိပ်။ ကျန်အပိုင်း
  12. stack နှင့်ပထမတန်းတန်းနှစ်ခုစလုံးသည်ဗလာဟုတ်မဟုတ်ကိုစစ်ဆေးပါ၊ ဟုတ်ကဲ့၊ မဟုတ်ပါကို print ထုတ်ပါ။ မဟုတ်ပါ။

ကုဒ်

Stack permutations များအတွက် C ++ အစီအစဉ်

#include<bits/stdc++.h> 
using namespace std; 
  
bool checkStackPermutation(int a[], int b[], int n){ 
    
    queue<int> input; 
    for(int i=0; i<n; i++){ 
        input.push(a[i]);
    }
  
    queue<int> output; 
    for(int i=0; i<n; i++){ 
        output.push(b[i]);
    }
  
    stack <int> tempStack; 
    while(!input.empty()){ 
        int ele = input.front(); 
        input.pop(); 
        
        if (ele == output.front()){ 
            output.pop(); 
            
            while(!tempStack.empty()){ 
                
                if(tempStack.top() == output.front()){ 
                    tempStack.pop(); 
                    output.pop(); 
                } 
                
                else{
                    break;
                }
            } 
        } 
        else{
            tempStack.push(ele); 
        }
    } 
  
    return (input.empty()&&tempStack.empty()); 
} 
  
int main(){ 
    int a[] = {1, 2, 3}; 
    int b[] = {2, 1, 3}; 
  
    int n = sizeof(a)/sizeof(a[0]); 
  
    if(checkStackPermutation(a, b, n)){ 
        cout << "Yes"; 
    }
    else{
        cout << "No"; 
    }
    return 0; 
}
Yes

Stack permutations များအတွက်ဂျာဗားအစီအစဉ်

import java.util.LinkedList; 
import java.util.Queue; 
import java.util.Stack; 
  
class StackPermutation{ 
    static boolean checkStackPermutation(int a[], int b[], int n){ 
        Queue<Integer> input = new LinkedList<>(); 
  
        for(int i = 0; i < n; i++){ 
            input.add(a[i]); 
        } 
  
        Queue<Integer> output = new LinkedList<>(); 
        for(int i = 0; i < n; i++){ 
            output.add(b[i]); 
        } 
  
        Stack<Integer> tempStack = new Stack<>(); 
        while(!input.isEmpty()){ 
            int ele = input.poll(); 
  
            if(ele == output.peek()){ 
                output.poll(); 
                
                while(!tempStack.isEmpty()){ 
                    
                    if(tempStack.peek() == output.peek()){ 
                        tempStack.pop(); 
                        output.poll(); 
                    } 
                    
                    else{
                        break;
                    }
                } 
            }  
            else{ 
                tempStack.push(ele); 
            } 
        } 
  
        return (input.isEmpty() && tempStack.isEmpty()); 
    } 
  
    public static void main(String[] args){ 
        
        int a[] = { 1, 2, 3 }; 
        int b[] = { 2, 1, 3 }; 
        int n = a.length;
        
        if(checkStackPermutation(a, b, n)){ 
            System.out.println("Yes"); 
        }
        else{
            System.out.println("No"); 
        }
    } 
}
Yes

ရှုပ်ထွေးဆန်းစစ်ခြင်း

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

အို (ဎ) n သည်ပေးထားသောခင်းကျင်းခြင်းမှ [] နှင့် b [] ၏နံပါတ်များဖြစ်သည်။ ကျွန်ုပ်တို့သည် array element များမှတဆင့်ရွေ့လျားနေသည့်အချိန်အတိုင်းအတာတစ်ခုအထိဖြတ်သန်းသွားသည်။

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

အို (ဎ) ဘာလို့လဲဆိုတော့ကျွန်တော်တို့ဟာ n element တွေအတွက် space သုံးလို့ပဲ။ အာကာသအတွင်း၌ရှုပ်ထွေးမှုများကိုရှုပ်ထွေးစေသည့် Queue နှစ်ခုနှင့် stack တစ်ခုကိုပြုလုပ်ခဲ့သည်။