tło
Binarne drzewo jest zakorzenione drzewo której każdy węzeł ma co najwyżej dwoje dzieci.
Oznaczone drzewo binarne to drzewo binarne której każdy węzeł jest oznaczony liczbą całkowitą dodatnią; ponadto wszystkie etykiety są odrębne .
BST (binarne drzewo poszukiwań) jest oznaczony drzewo binarne, w którym etykieta każdego węzła jest większa niż etykietach wszystkich węzłów w jego lewym poddrzewie, a mniejszy niż etykietach wszystkich węzłów w jego prawym poddrzewie. Na przykład następujące BST:
Przejścia pre-order z oznaczonego drzewa binarnego jest określona według następującego pseudo-kodu.
function preorder(node)
if node is null then
return
else
print(node.label)
preorder(node.left)
preorder(node.right)
Zobacz poniższy obraz, aby uzyskać lepszą intuicję:
Wierzchołki tego drzewa binarnego są drukowane w następującej kolejności:
F, B, A, D, C, E, G, I, H
Możesz przeczytać więcej o BST tutaj , a więcej o przechodzeniu w przedsprzedaży tutaj .
Wyzwanie
Biorąc pod uwagę listę liczb całkowitych , Twoim zadaniem jest ustalenie, czy istnieje BST, którego podróż w przedsprzedaży drukuje dokładnie .
Wkład
- Niepusta lista wyraźnych liczb całkowitych dodatnich .
- Opcjonalnie długość .
Wydajność
- Truthy wartość jeśli jest przechodzenie pre-order od jakiegoś BST.
- W przeciwnym razie wartość falsey .
Zasady
- Standardowe zasady dla prawidłowych zgłoszeń , I / O , luki zastosowania.
- To jest golf golfowy , więc wygrywa najkrótsze rozwiązanie (w bajtach). Jak zwykle, nie pozwól, aby absurdalnie krótkie rozwiązania w językach golfowych zniechęcały Cię do publikowania dłuższych odpowiedzi w wybranym języku.
- Nie jest to regułą, ale twoja odpowiedź będzie lepiej odebrana, jeśli będzie zawierała link do przetestowania rozwiązania i wyjaśnienie, jak to działa.
Przykłady
Input ----> Output
[1] ----> True
[1,2,3,4] ----> True
[5,1,4,2,3] ----> True
[5,4,3,2,1,6,7,8,9] ----> True
[4,2,1,3,6,5,7] ----> True
[8,3,1,6,4,7,10,14,13] ----> True
[2,3,1] ----> False
[6,3,2,4,5,1,8,7,9] ----> False
[1,2,3,4,5,7,8,6] ----> False
[3,1,4,2] ----> False
Sprawdź ten link (dzięki uprzejmości Kevina Cruijssena ), aby obejrzeć przykłady.
źródło
Odpowiedzi:
JavaScript (Node.js) , 49 bajtów
Wypróbuj online!
Dzięki Arnauld zaoszczędź 1 bajt.
źródło
Galaretka , 7 bajtów
Wypróbuj online!
Zwraca
[4]
w przypadku podróży[]
.Zasadniczo wykorzystuje algorytm tsh: warunek „dyskwalifikujący” dla przejścia w przedsprzedaży to podciąg 3 elementów, który wygląda następująco: [średni, wysoki, niski] . (Na przykład [20, 30, 10].)
Mamy równoważnie sprawdzić za podciągów dowolny długości, które mają indeks 4 w swoich listach permutacji, które są wszystkie listy sortowane jak [a 1 ... O k CDB] gdzie i są klasyfikowane i i <b <c <d . (Każda taka lista dyskwalifikuje, jeśli spojrzymy na ostatnie trzy elementy, a każda lista dyskwalifikująca ma oczywiście tę formę).
Dowód
źródło
Java 10, 94 bajty
Port odpowiedzi JavaScript na @tsh .
Wypróbuj online.
Wyjaśnienie:
źródło
|=
. Zakładam,&=
że też będzie działać?|=
i&=
praca jako skrótówb = b | condition
ib = b & condition
(gdzie&
i|
są skróty&&
i||
w większości przypadków oczywiście).Rubinowy ,
46 4038 bajtówWypróbuj online!
Działa to poprzez rekurencyjne przyjmowanie pierwszego elementu
a
jako elementu przestawnego i sprawdzanie, czy resztę tablicy można podzielić na dwie części (używając przecięcia i łączenia: najpierw usuń wszystkie elementy> a, a następnie dodaj je ponownie po prawej stronie i sprawdź, czy coś ma zmienione).źródło
Retina 0.8.2 , 31 bajtów
Wypróbuj online! Link zawiera przypadki testowe. Wykorzystuje algorytm @ tsh. Wyjaśnienie:
Konwertuj na unary.
Znajdź liczby leżące między dwoma kolejnymi liczbami malejącymi.
Sprawdź, czy liczba dopasowań wynosi zero.
źródło
Perl 6 , 38 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
Haskell , 50 bajtów
Wypróbuj online!
źródło
Scala (
6867 bajtów)Wypróbuj online
Port @ nwellnhof's odpowiedź .
Scala (
122103 bajty)Dziękujemy @Laikoni za sugestie skrócenia obu rozwiązań.
Wypróbuj online
Wyjaśnienie:
span
) tablicę, używając głowy tablicy jako kryteriów krojenia.źródło
val (s,t)
,true
możesz być1>0
i możesz spaść,s.forall(_<i(0))&
ponieważ powinno to być już ubezpieczonespan
.%
i upuścić spację:def%(i:Seq[Int])=
l.zipWithIndex.foldLeft(1>0){case(r,v,i)=>r&l.zip(l.tail).slice(i+1,l.length).forall(x=>l(i)>x._1|l(i)<x._2)}
.. Wersja 2(for(i<-l.indices)yield l.zip(l.tail).slice(i+1,l.length).forall(x =>l(i)>x._1|l(i)<x._2)).forall(x=>x)
.. Wszelkie pomysły, jak je skrócić?05AB1E ,
1510 bajtówPort odpowiedzi galaretki @Lynn .
-5 bajtów dzięki @Emigna .
Wypróbuj online lub sprawdź wszystkie przypadki testowe .
Objaśnienie: „
źródło
ŒεD{3.IÊ}P
?Haskell , 41 bajtów
Wypróbuj online!
Wykorzystuje spostrzeżenie Lynn, że wystarczy sprawdzić, czy nie ma podsekwencji dla środkowej wysokości . Niskiej . Oznacza to, że dla każdego elementu
h
następująca lista elementówt
jest blokiem elementów,<h
po którym następuje blok elementów>h
(oba bloki mogą być puste). Tak więc kod sprawdza, czy po upuszczeniu prefiksu elementów<h
wt
pozostałe elementy są wszyscy>h
. Rekurencja sprawdza to dla każdego elementu początkowegoh
dopóki lista nie będzie długości 1.Potencjalnym uproszczeniem jest to, że wystarczy sprawdzić wzorce w połowie ... wysoko, nisko tam , gdzie dwa ostatnie są kolejne. Niestety Haskell nie ma krótkiego sposobu na wyodrębnienie dwóch ostatnich elementów, co można zrobić z przodu za pomocą dopasowania wzoru
a:b:c
. Znalazłem krótsze rozwiązanie, które sprawdza średnie, wysokie .. niskie , ale to nie odrzuca danych wejściowych takich jak[3,1,4,2]
.Sformatowane przypadki testowe zaczerpnięte z Laikoni .
źródło
Japt , 14 bajtów
Japt Interpreter
Wyjścia
false
dla BST,true
bez BST.Wyjaśnienie:
źródło
Scala
Wszystkie podejścia są implementacjami reguły pokazanej przez tsh.
109
101
98
78
Jeśli musi to być funkcja, a nie tylko wyrażenie, każda linia musi zaczynać się od (17 bajtów)
źródło
Oracle SQL, 177 bajtów
Ponieważ w Oracle SQL nie ma typu logicznego, zapytanie zwraca 1 lub 0.
Oracle SQL 12c, 210 bajtów
Nie jest możliwy dostęp do elementu tablicy w SQL w taki sam sposób jak w PL / SQL - tj. A (i), dlatego funkcja
f
została zadeklarowana wwith clause
tym celu. W przeciwnym razie rozwiązanie byłoby znacznie krótsze.Inne ograniczenia
aukcja sqlplus
Weryfikacja online apex.oracle.com
Aktualizacja
Oracle SQL, 155 bajtów
źródło
C, 823 bajty (nie licząc białych znaków); 923 bajty (w tym białe znaki)
Wersja programu do odczytu znajduje się poniżej:
Główną metodą tego programu jest odczytywanie listy liczb, które (rzekomo) są zgodne z prawem przedsprzedażą.
Wywołana funkcja insert_root wstawia liczby całkowite do drzewa wyszukiwania binarnego, w którym poprzednie węzły zawierają mniejsze wartości, a kolejne węzły zawierają większe wartości int.
Funkcja preorder (root) przechodzi przez drzewo podczas przechodzenia w przedsprzedaży i jednocześnie konkatenuje każdą liczbę całkowitą, którą algorytm napotyka na tablicy int lista test_list .
Końcowa pętla while sprawdza, czy każda z wartości int w liście stdin i na liście test_list jest równoważna dla każdego indeksu. Jeśli istnieje element listy ze standardowego wejścia, który nie pasuje do odpowiedniego elementu w liście test_list w odpowiednim indeksie, funkcja główna zwraca 0. W przeciwnym razie metoda główna zwraca 1 .
Aby ustalić, co main zwrócił, wpisz echo $ status w terminalu bash. BASH wydrukuje 1 lub 0.
źródło