Пермутации на магацинот (Проверете дали низата е пермутација на другиот)


Ниво на тешкотија Медиум
Често прашувано во Амазон Фуркити
Комбинаторски редот Магацинот

Изјава за проблем

Проблемот „Stack Permutations (Проверете дали низата е магацин за пермутација на другите)“ вели дека ви се дадени две низи a [] и b [] со големина n. Сите елементи на низата се единствени. Создадете функција за да проверите дали дадената низа b [] е пермутација на оџакот на дадената низа a [] или не.

Пермутации на магацинот (Проверете дали низата е пермутација на другиот)

пример

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. Поминете низ низата a [] и притиснете / вметнете ги сите елементи на низата a [] во редот.
  5. После тоа, креирајте втора структура на податоци за редици од цел број.
  6. Поминете низ низата b [] и притиснете / вметнете ги сите елементи на низата b [] во редот.
  7. Слично на тоа, создадете А. магацинот структура на податоци од цел тип.
  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

Јава програма за 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 е бројот на елементи во дадена низа a [] и b []. Само што преминавме низ низата елементи и со тоа линеарна временска комплексност.

Комплексноста на просторот

Тој) затоа што користевме простор за n елементи. Создадовме две редици и стек што го прави алгоритмот да има линеарна сложеност во просторот.