Tenim una pila buida i podem realitzar operacions push i pop. Ens donen dues matrius a[] i b[] on a[] representa l'ordre en què els elements s'empenyen a la pila i b[] representa l'ordre en què es treuen els elements de la pila. Trobeu si les seqüències push i pop donades són vàlides.
Exemples:
xor en c++
Entrada: a[] = [1 2 3] b[] = [2 1 3]
Sortida: veritat
Explicació: Premeu 1 i 2. Com que b[] requereix 2 primer pop 2 i després pop 1 a continuació. Finalment, premeu 3 i feu-lo caure. La seqüència push i pop coincideix amb a[] i b[].Entrada: a[] = [1 2 3] b[] = [3 1 2]
Sortida: fals
Explicació: Després de prémer 1, 2 i 3, podem treure 3 segons sigui necessari. Però el següent element a b[] és 1 mentre que la part superior de la pila és 2. Com que 1 està bloquejat per sota de 2, aquest ordre no es pot aconseguir.
Taula de continguts
- [Enfocament ingenu] Ús de la cua: temps O(n) i espai O(n).
- [Enfocament esperat] Simulant Push and Pop - O(n) temps i O(n) espai
[Enfocament ingenu] Ús de la cua: temps O(n) i espai O(n).
La idea és simular les operacions de la pila mentre es fa un seguiment dels elements restants per processar-los cues .
Empengem els elements de a[] en ordre i per a cada element comprovem si coincideix amb la part frontal de b[] (l'ordre pop esperat). Si coincideix, l'eliminem de b[]; si no, l'empenyem a una pila. Després de cada empenta també comprovem la part superior de la pila si coincideix amb la part frontal de b[] sortim de la pila i la traiem de b[]. En repetir això, veiem si tots els elements de b[] es poden coincidir. En cas afirmatiu, la seqüència pop és vàlida; en cas contrari no ho és.
C++#include
import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class GfG { static boolean checkPerm(int[] a int[] b) { Queue<Integer> q1 = new LinkedList<>(); for (int i = 0; i < a.length; i++) q1.add(a[i]); Queue<Integer> q2 = new LinkedList<>(); for (int i = 0; i < b.length; i++) q2.add(b[i]); Stack<Integer> st = new Stack<>(); // Dequeue all items one by one while (!q1.isEmpty()) { int ele = q1.poll(); if (ele == q2.peek()) { // If matches dequeue from output queue q2.poll(); // Pop from stack while top matches q2 front while (!st.isEmpty() && !q2.isEmpty() && st.peek() == q2.peek()) { st.pop(); q2.poll(); } } else { st.push(ele); } } return q2.isEmpty(); } public static void main(String[] args) { int[] a = {1 2 3}; int[] b = {3 2 1}; if (checkPerm(a b)) System.out.println('true'); else System.out.println('false'); } }
from collections import deque def checkPerm(a b): q1 = deque(a) q2 = deque(b) st = [] # Dequeue all items one by one while q1: ele = q1.popleft() if ele == q2[0]: # If matches dequeue from output queue q2.popleft() # Pop from stack while top matches q2 front while st and q2 and st[-1] == q2[0]: st.pop() q2.popleft() else: st.append(ele) return not q2 if __name__ == '__main__': a = [1 2 3] b = [3 2 1] if checkPerm(a b): print('true') else: print('false')
using System; using System.Collections.Generic; public class GfG { static bool checkPerm(int[] a int[] b) { Queue<int> q1 = new Queue<int>(a); Queue<int> q2 = new Queue<int>(b); Stack<int> st = new Stack<int>(); // Dequeue all items one by one while (q1.Count > 0) { int ele = q1.Dequeue(); if (ele == q2.Peek()) { // If matches dequeue from output queue q2.Dequeue(); // Pop from stack while top matches q2 front while (st.Count > 0 && q2.Count > 0 && st.Peek() == q2.Peek()) { st.Pop(); q2.Dequeue(); } } else { st.Push(ele); } } return q2.Count == 0; } public static void Main() { int[] a = { 1 2 3 }; int[] b = { 3 2 1 }; if (checkPerm(a b)) Console.WriteLine('true'); else Console.WriteLine('false'); } }
function checkPerm(a b) { // simulate queue with array let q1 = a; // simulate queue with array let q2 = b; let st = []; // pointer for front of q1 let front1 = 0; // pointer for front of q2 let front2 = 0; while (front1 < q1.length) { let ele = q1[front1]; front1++; if (ele === q2[front2]) { front2++; // Pop from stack while top matches q2 front while (st.length > 0 && st[st.length - 1] === q2[front2]) { st.pop(); front2++; } } else { st.push(ele); } } return front2 === q2.length; } // Driver Code let a = [1 2 3]; let b = [3 2 1]; console.log(checkPerm(a b));
Sortida
true
[Enfocament esperat] Simulació de push i pop - O(n) temps i O(n) espai
En aquest enfocament, en realitat no creem cues ni modifiquem les matrius d'entrada. En canvi, simulem directament les operacions push i pop en una pila.
matriu java per llistar
Cada element d'a[] s'empeny a la pila un per un. Després de cada empenta, comprovem si la part superior de la pila coincideix amb l'element actual de b[]. Si ho fa, l'extraurem de la pila i avancem en b[]. Aquest procés es repeteix fins que tots els elements d'a[] s'han empès i comprovat. Si al final tots els elements de b[] s'han trobat correctament i s'han aparegut, la permutació és vàlida (retorn cert); en cas contrari, no és vàlid (retorna fals).
C++#include
import java.util.Stack; public class GfG { static boolean checkPerm(int[] a int[] b) { Stack<Integer> st = new Stack<>(); int j = 0; for (int i = 0; i < a.length; i++) { // Push top of a[] to stack st.push(a[i]); // Keep popping from stack while it // matches front of the output array while (!st.isEmpty() && st.peek().equals(b[j])) { st.pop(); j++; } } return (j == b.length); } public static void main(String[] args) { int[] a = {1 2 3}; int[] b = {2 1 3}; System.out.println(checkPerm(a b) ? 'true' : 'false'); } }
def checkPerm(a b): st = [] j = 0 for i in range(len(a)): # Push top of a[] to stack st.append(a[i]) # Keep popping from stack while it # matches front of the output queue while st and st[-1] == b[j]: st.pop() j += 1 return j == len(b) if __name__ == '__main__': a = [1 2 3] b = [2 1 3] print('true' if checkPerm(a b) else 'false')
using System; using System.Collections.Generic; class GfG { static bool checkPerm(int[] a int[] b) { Stack<int> stack = new Stack<int>(); int j = 0; for (int i = 0; i < a.Length; i++) { // Push top of a[] to stack stack.Push(a[i]); // Keep popping from stack while it matches b[j] while (stack.Count > 0 && stack.Peek() == b[j]) { stack.Pop(); j++; } } return j == b.Length; } static void Main() { int[] a = { 1 2 3 }; int[] b = { 2 1 3 }; Console.WriteLine(checkPerm(a b) ? 'true' : 'false'); } }
function checkPerm(a b) { const stack = []; let j = 0; for (let i = 0; i < a.length; i++) { // Push top of a[] to stack stack.push(a[i]); // Keep popping from stack while it // matches front of the output queue while (stack.length > 0 && stack[stack.length - 1] === b[j]) { stack.pop(); j++; } } return j === b.length; } //Driven Code const a = [1 2 3]; const b = [2 1 3]; console.log(checkPerm(a b) ? 'true' : 'false');
Sortida
trueCrea un qüestionari