סטאַק פּערמיוטיישאַנז (טשעק אויב אַ מענגע איז סטאַק פּערמיוטיישאַן פון אנדערע)


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַמאַזאָן פאָורקיטעס
קאָמבינאַטאָריאַל ריי אָנלייגן

פּראָבלעם סטאַטעמענט

די פּראָבלעם "סטאַק פּערמיוטיישאַנז (קוק אויב אַ מענגע איז סטאַק פּערמוטיישאַן פון אנדערע)" שטאַטן אַז איר האָט צוויי ערייז אַ [] און ב [] פון גרייס N. אַלע די עלעמענטן פון די מענגע זענען יינציק. שאַפֿן אַ פונקציע צו קאָנטראָלירן אויב די געגעבן מענגע ב [] איז די אָנלייגן פּערמאַטיישאַן פון געגעבן מענגע אַ [] אָדער נישט.

סטאַק פּערמיוטיישאַנז (טשעק אויב אַ מענגע איז סטאַק פּערמיוטיישאַן פון אנדערע)

בייַשפּיל

a[ ] = {1, 2, 3}

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

דערקלערונג: ערשטער שטופּן 1 און 2 אין דעם אָנלייגן. דערנאך קנאַל זיי פֿון די אָנלייגן. דערנאָך, שטופּן 3 און דאַן קנאַל 3. אַזוי די ריזאַלטאַנט סיקוואַנס קוקט עפּעס ווי 2, 1,3 וואָס איז אונדזער רגע מענגע.

a[ ] = {1, 2, 3}

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

דערקלערונג: עס איז קיין סיקוואַנס פון שטופּן און קנאַל וואָס וועט רעזולטאַט אין די רגע מענגע. און אַזוי ענטפֿערן איז קיין.

אַלגאָריטהם

  1. ערשט צוויי ערייז a [] און b [] פון גרייס n.
  2. שאַפֿן אַ פֿונקציע צו קאָנטראָלירן פּערמוטאַטיאָן פון די אָנלייגן וואָס אַקסעפּץ די צוויי ינטעגער ערייז און די גרייס פון דעם מענגע ווי די פּאַראַמעטערס.
  3. נאָך דעם, שאַפֿן אַ ריי דאַטן ביניען פון ינטאַדזשער טיפּ.
  4. אַריבער דורך די מענגע אַ [] און שטופּן / טאָן אַלע די יסודות פון די מענגע אַ [] אין די ריי.
  5. דערנאָך, שאַפֿן אַ רגע ריי דאַטן סטרוקטור פון גאַנץ נומער.
  6. דורכפאָר דורך די מענגע ב [] און שטופּן / טאָן אַלע די יסודות פון מענגע ב [] אין די ריי.
  7. סימילאַרלי, שאַפֿן אַ stack דאַטן ביניען פון ינטאַדזשער טיפּ.
  8. דורך די גרייס פון דער ערשטער ריי איז ניט 0. שאַפֿן אַ ינטעגער בייַטעוודיק און קראָם די עלעמענט אין די פראָנט פון דער ערשטער ריי און קנאַל / באַזייַטיקן עס פֿון דער ערשטער ריי.
  9. קאָנטראָלירן אויב די ווערט אין די ינטעגער בייַטעוודיק איז נישט גלייַך צו די עלעמענט אין די פראָנט פון די רגע ריי, שטופּן / אַרייַן די גאַנץ נומער בייַטעוודיק אין די אָנלייגן.
  10. אַנדערש קנאַל / אַראָפּנעמען די עלעמענט אין די פראָנט פון די רגע ריי.
  11. דורכפאָר ווידער ווען די גרייס פון דעם אָנלייגן איז ניט 0. קאָנטראָלירן אויב דער עלעמענט אין דער שפּיץ פון דעם אָנלייגן איז גלייַך צו די עלעמענט אין די פראָנט פון די רגע ריי, קנאַל / באַזייַטיקן די עלעמענט אין די פראָנט פון די רגע ריי און פֿון די שפּיץ פון די אָנלייגן. אַנדערש ברעכן.
  12. קוק אויב ביידע סטאַק און דער ערשטער ריי זענען ליידיק, דרוקן "יא" אַנדערש דרוקן "ניין".

קאָדעקס

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

Java פּראָגראַם פֿאַר סטאַק פּערמיוטיישאַנז

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) וווּ n איז די נומער פון עלעמענטן אין אַ געגעבן מענגע אַ [] און b []. מיר האָבן נאָר דורכגעגאנגען די מענגע עלעמענטן און אַזוי אַ לינעאַר צייט קאַמפּלעקסיטי.

ספעיס קאַמפּלעקסיטי

אָ (N) ווייַל מיר געוויינט פּלאַץ פֿאַר n עלעמענטן. מיר באשאפן צוויי קיוז און סטאַק וואָס אַלאַוז די אַלגערידאַם לינעאַר קאַמפּלעקסיטי אין פּלאַץ.