jak przetestować zamówienie pop jest legalne czy nie?

Question

Biorąc pod uwagę dwie unikalne sekwencje numerów: push order of stack i pop order of stack, numery w push order są w kolejności rosnącej, teraz zapytaj pop order czy jest legalna czy nie?

Na przykład push order jest 1 2 3 4 5, więc 4 5 3 2 1 jest legalny porządek pop, ponieważ możemy naciskać i pop tak:

push 1, push 2, push 3, push 4, pop, push 5, pop, pop, pop, pop

tak pop zamówienie: 4 5 3 2 1 jest legalne, a 4 3 5 1 2 nie jest legalnym zamówieniem pop.

Answer 1

Od swojej sekwencji wypychania jest w porządku rosnącym, a następnie, gdy pojawi się numer N w kolejce pop, potem wszystkie numery, które wynosi 1) poniżej N i 2) jeszcze nie pojawił, musi być zdjęta w kolejności malejącej.

Na przykład 4 3 5 1 2 nie jest prawidłową kolejnością, ponieważ kiedy widzimy "4", wszystkie liczby mniejsze niż "4", ale jeszcze nie pobite, muszą być wyświetlone w malejącej kolejności. Jednak pierwsze "1", a następnie "2" naruszają tę właściwość.

Answer 2

Rozwiązanie:

i: from 1 to n 
j: from 1 to n, used to traverse the sequence seq[1...n] 
stack: empty at the beginning 
while i <= n || j <= n 
    IF stack is empty, 
     push i into stack, i plus 1; 
    ELSE IF the top of stack is equal to seq[j] 
     pop from stack, j plus 1; 
    ELSE IF the top of stack is larger than seq[j] 
     illegal sequence! Stop here! 
    ELSE 
     push i into stack, i plus 1; 
legal sequence if the stack is empty! 

Przykład 1: {1, 2, 4, 3} przeprowadzone prawidłowo

In the beginning, i = 1, j = 1, and stack is empty. 

1. stack is empty: 
    stack = {1}, i = 2, j = 1. 

2. top of stack 1 is equal to seq[j] = 1: 
    stack = {}, i = 2, j = 2. 

3. stack is empty: 
    stack = {2}, i = 3, j = 2. 

4. top of stack 2 is equal to seq[j] = 2: 
    stack = {}, i = 3, j = 3. 

5. stack is empty: 
    stack = {3}, i = 4, j = 3. 

6. top of stack 3 is smaller than seq[j] = 4: 
    stack = {3, 4}, i = 5, j = 3. 

7. top of stack 4 is equal to seq[j] = 4: 
    stack = {3}, i = 5, j = 4. 

8. top of stack 3 is equal to seq[j] = 3: 
    stack = {}, i = 5, j = 5. 

Przykład 2: {1, 4, 2, 3}, niedozwolona sekwencja

In the beginning, i = 1, j = 1, and stack is empty. 

1. stack is empty: 
    stack = {1}, i = 2, j = 1. 

2. top of stack 1 is equal to seq[j] = 1: 
    stack = {}, i = 2, j = 2. 

3. stack is empty: 
    stack = {2}, i = 3, j = 2. 

4. top of stack 2 is smaller than seq[j] = 4: 
    stack = {2, 3}, i = 4, j = 2. 

5. top of stack 3 is smaller than seq[j] = 4: 
    stack = {2, 3, 4}, i = 5, j = 2. 

6. top of stack 4 is equal to seq[j] = 4: 
    stack = {2, 3}, i = 5, j = 3. 

7. top of stack 3 is larger than seq[j] = 2: 
    illegal sequence, stop here. 

Staram się jak najlepiej wyjaśnić mój pomysł, mam nadzieję, że wyjaśniłem.

Answer 3

Jedną z opcji jest faktycznie skonstruowania stosu:

Dla każdego numeru X w kolejności pop:

• Jeśli ta liczba nie jest taka sama jak w szczycie stosu (lub stos jest pusty), naciśnij numery od kolejności push, aż nacisnąłeś X. Jeśli pchnąłeś wszystkie liczby i nie znalazłeś X, nie ma sposobu, aby uzyskać pop-pop.
• Pop X

Zauważ, że to rzeczywiście nie wymaga, aby zamówienie Push jest rosnący.

Możesz skorzystać z zamówienia, aby zoptymalizować powyższe informacje (aby wcześniej zawieść), jeśli nie uda się, jeśli X jest mniejszy niż szczyt stosu.

Ponieważ naciskasz tylko jeden element co najwyżej raz, powyższy jest czasem liniowym (którego nie można zrobić lepiej) i liniowym.

Przykład:

Push: 1 2 3 4 5 
Pop: 4 5 3 2 1 

Processing: 4 
    Stack empty -> push until 4 is on the top of the stack. 
    Stack: 1 2 3 4 
    Pop 4 
    Stack: 1 2 3 

Processing: 5 
    3 != 5 -> push until 5 is on the top of the stack. 
    Stack: 1 2 3 5 
    Pop 5 
    Stack: 1 2 3 

Processing: 3 
    Pop 3 
    Stack: 1 2 

Processing: 2 
    Pop 2 
    Stack: 1 

Processing: 1 
    Pop 1 
    Stack: 

Done. 

Answer 4

Założenie: Kolejność Push oraz kolejność pop zawiera dokładnie te same numery. Jeśli nie jest to prawidłowe założenie, można je zweryfikować za pomocą skrótu (lub hash-map zliczeń, jeśli mogą być duplikaty) w czasie liniowym, chociaż mogłoby to zagrozić złożoności przestrzeni O (1).

Idea: Każdy element w kolejności pop musi być albo mniej niż element przed nim, lub więcej niż maksimum tej pory, w przeciwnym razie zamówienie pop nie jest ważna.

Można to sprawdzić w przestrzeni O (n) i O (1), po prostu śledząc wartość maksymalną.

Dlaczego to działa:

Kolejność Push jest w porządku rosnącym, w ten sposób, niezależnie od tego, kiedy pop elementy:

1. Stos zawsze będzie porządku rosnącym, jak również i
2. Następny element w kolejności push będzie zawsze większy niż największy element widoczny na stosie. w -
   • Dwie operacje pop z rzędu - w tym przypadku drugi element będzie mniejsze
   • Dwie operacje POP z jednego lub większej liczby operacji wypychania w dniach:

Tak więc istnieją dwie opcje w tym przypadku drugi element będzie większa niż maksymalna (zgodnie z 2.)

Przykłady:

4 5 3 2 1 jest ważne od 5> max (4), +3 < 5, 3 i 2 2.

4 3 5 1 2 nie jest ważna, ponieważ 2> 1 a 2 < max (5).

1 2 3 5 4 jest ważne od 2> max (1), 3> max (2), 5> max (3) i 4 < 5.