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 $a$ , Twoim zadaniem jest ustalenie, czy istnieje BST, którego podróż w przedsprzedaży drukuje dokładnie $a$ .

Wkład

• Niepusta lista wyraźnych liczb całkowitych dodatnich $a$ .
• Opcjonalnie długość $a$ .

Wydajność

• Truthy wartość jeśli jest przechodzenie pre-order od jakiegoś BST.$a$
• 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.

JavaScript (Node.js) , 49 bajtów

a=>!a.some((p,i)=>a.some((q,j)=>q>p&a[j+=j>i]<p))

Wypróbuj online!

$a_0 ... a_{n-1}$$a$$\forall 0\le i<j<n; a_i<a_{j-1} \implies a_i<a_j$

Dzięki Arnauld zaoszczędź 1 bajt.

Galaretka , 7 bajtów

ŒPŒ¿€4ḟ

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 ₁ ... 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ę).

ŒP          All subsequences.
  Œ¿€       Permutation index of each.
     4ḟ     Set difference of {4} and this list.

Dowód

Podróż w przedsprzedaży nie zawiera podsekwencji dyskwalifikujących

Przypadek podstawowy: traversal (•) to pusta lista. ✓

Indukcja: traversal (t) to: t.root ++ traversal (t.left) ++ traversal (t.right) .

Niech [a, b, c] będzie podsekwencją tego. Pokażemy, że c <a <b jest niemożliwe.

• Jeśli t.root = a , to c <a <b wymaga c ∈ t. W lewo i b ∈ t. W prawo , więc [a, b, c] jest w niewłaściwej kolejności.
• Jeśli a, b, c ∈ t. W lewo lub a, b, c ∈ t. W prawo , zastosuj hipotezę indukcyjną.
• Jeśli ∈ t. W lewo i c ∈ t. W prawo, to c> a .

Lista odrębnych liczb całkowitych bez dyskwalifikujących podsekwencji jest przejściem BST w przedsprzedaży

Jeśli lista jest pusta, oznacza to przejście trywialnego BST •.

Jeśli na liście znajduje się głowa, a następnie ogon :

• Niech mniej będzie najdłuższym prefiksem ogona elementów mniejszym niż głowa , a niech więcej się reszta listy.
• Następnie więcej [1]> głowa i wszystkie inne jeszcze [i] są większe niż głowa (w przeciwnym razie [głowa, więcej [1], więcej [i]] byłoby podsekwencją dyskwalifikującą).
• Recurse: turn mniej i bardziej w BSTS.

• Teraz nasza lista to przejście

                   head
                  /    \
           BST(less)   BST(more),
  

  a to drzewo jest prawidłowym BST.

Java 10, 94 bajty

a->{var r=0>1;for(int j=a.length-1,i;j-->0;)for(i=0;i<j;)r|=a[j]>a[i]&a[j+1]<a[i++];return!r;}

Port odpowiedzi JavaScript na @tsh .

Wypróbuj online.

Wyjaśnienie:

a->{                      // Method with integer-array parameter and boolean return-type
  var r=0>1;              //  Result-boolean, starting at false
  for(int j=a.length-1,i;j-->0;)
                          //  Loop `j` in the range (length-1, 0]:
    for(i=0;i<j;)         //   Inner loop `i` in the range [0, j):
      r|=                 //    If any are true, change the result to true as well:
         a[j]>a[i]        //     The `j`'th item is larger than the `i`'th item
         &a[j+1]<a[i++];  //     And the `j+1`'th item is smaller than the `i`'th item
  return!r;}              //  After the nested loop, check if the boolean is still false

Rubinowy , 46 40 38 bajtów

f=->r{a,*b=r;!a||b==b&[*0..a]|b&&f[b]}

Wypróbuj online!

Działa to poprzez rekurencyjne przyjmowanie pierwszego elementu ajako 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).

Retina 0.8.2 , 31 bajtów

\d+
$*
M`\b((1+)1+,).*\1\2\b
^0

Wypróbuj online! Link zawiera przypadki testowe. Wykorzystuje algorytm @ tsh. Wyjaśnienie:

\d+
$*

Konwertuj na unary.

M`\b((1+)1+,).*\1\2\b

Znajdź liczby leżące między dwoma kolejnymi liczbami malejącymi.

^0

Sprawdź, czy liczba dopasowań wynosi zero.

Perl 6 , 38 bajtów

!*.combinations(3).grep:{[>] .[1,0,2]}

Wypróbuj online!

Wyjaśnienie

 *.combinations(3)  # All combinations of 3 elements a,b,c
!                 .grep:{            }  # Return false if check succeeds for any combination
                         [>] .[1,0,2]   # Check whether b>a>c, that is b>a and c<a

Haskell , 50 bajtów

f[]=1<3
f(x:r)|(a,b)<-span(<x)r=all(>x)b&&f a&&f b

Wypróbuj online!

Scala ( 68 67 bajtów)

def%(i:Seq[Int])= !i.combinations(3).exists(c=>c(0)<c(1)&c(0)>c(2))

Wypróbuj online

Port @ nwellnhof's odpowiedź .

Scala ( 122 103 bajty)

def f(i:Seq[Int]):Boolean=if(i.size<1)1>0 else{val(s,t)=i.tail.span(_<i(0));t.forall(_>i(0))&f(s)&f(t)}

Dziękujemy @Laikoni za sugestie skrócenia obu rozwiązań.

Wypróbuj online

Wyjaśnienie:

1. plasterek (przy użyciu Scali span ) tablicę, używając głowy tablicy jako kryteriów krojenia.
2. Potwierdź, że pierwszy plasterek tablicy jest mniejszy niż głowa, a drugi plasterek jest większy niż głowa.
3. rekurencyjnie sprawdź, czy każdy plasterek również spełnia (2)

05AB1E , 15 10 bajtów

ŒεD{3.IÊ}P

Port odpowiedzi galaretki @Lynn .
-5 bajtów dzięki @Emigna .

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Objaśnienie: „

Π            # Take all sublists of the (implicit) input-list
              #  i.e. [2,3,1] → [[2],[2,3],[2,3,1],[3],[3,1],[1]]
              #  i.e. [1,2,3,4]
              #   → [[1],[1,2],[1,2,3],[1,2,3,4],[2],[2,3],[2,3,4],[3],[3,4],[4]]
 ε      }     # Map each to:
  D           #  Duplicate the current sublist on the stack
   {          #  Sort the copy
              #   i.e. [2,3,1] → [1,2,3]
              #   i.e. [2,3,4] → [2,3,4]
    3.I       #  Get the 4th (3rd 0-indexed) permutation of this list
              #   i.e. [1,2,3] → [2,3,1]
              #   i.e. [2,3,4] → [3,4,2]
       Ê      #  Check that the lists are NOT equal
              #   i.e. [2,3,1] and [2,3,1] → 0 (falsey)
              #   i.e. [2,3,4] and [3,4,2] → 1 (truthy)
         P    # Check whether all are truthy (and output implicitly)
              #  i.e. [1,1,0,1,1,1] → 0 (falsey)
              #  i.e. [1,1,1,1,1,1,1,1,1,1] → 1 (truthy)

Haskell , 41 bajtów

f(h:t)=t==[]||all(>h)(snd$span(<h)t)&&f t

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 hnastępująca lista elementów tjest blokiem elementów, <hpo 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 w tpozostał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 wzorua: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 .

Japt , 14 bajtów

d@sY ð_§XÃxÈ-Y

Japt Interpreter

Wyjścia falsedla BST, truebez BST.

Wyjaśnienie:

d@                Run on each item X, return true if any aren't 0: 
  sY                  Ignore the numbers before this index
     ð_§XÃ            Get the indexes of numbers less than or equal to X
                          If it is a BST, this list will be e.g. [0,1,2...]
            -Y        Subtract the position within the index list from each index
                          eg. [0,1,2] -> [0,0,0] , [0,1,4] -> [0,0,2]
          xÈ          Sum the resulting array

Scala

Wszystkie podejścia są implementacjami reguły pokazanej przez tsh.

109

l.zipWithIndex.foldLeft(1>0){case(r,(v,i))=>r&l.zip(l.tail).slice(i+1,l.size).forall(x=>l(i)>x._1|l(i)<x._2)}

101

(for(i<-l.indices)yield l.zip(l.tail).slice(i+1,l.size).forall(x =>l(i)>x._1|l(i)<x._2)).forall(x=>x)

98

l.indices.foldLeft(1>0)((r,i)=>r&(l.zip(l.tail).slice(i+1,l.size).forall(x=>l(i)>x._1|l(i)<x._2)))

78

(for(i<-l.indices;j<-i+1 to l.size-2)yield l(i)>l(j)|l(i)<l(j+1)).forall(x=>x)

Jeśli musi to być funkcja, a nie tylko wyrażenie, każda linia musi zaczynać się od (17 bajtów)

def%(l:Seq[Int])=

Oracle SQL, 177 bajtów

with r(i,v)as(select rownum,value(t)from table(a)t)
select nvl(min(case when r.v<p.l and r.v>p.v then 0end),1)from r,(select i,lag(v)over(order by i)l,v from r)p where r.i+1<p.i

Ponieważ w Oracle SQL nie ma typu logicznego, zapytanie zwraca 1 lub 0.

Oracle SQL 12c, 210 bajtów

with function f(n ku$_objnumset,i int)return int as begin return n(i);end;
select min(case when f(c,1)>f(c,2)or f(c,1)<f(c,3)then 1else 0end)from(select value(t)c from table(powermultiset_by_cardinality(a,3))t)

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 fzostała zadeklarowana wwith clause tym celu. W przeciwnym razie rozwiązanie byłoby znacznie krótsze.

Inne ograniczenia

• zgłasza wyjątek dla tablic krótszych niż 3 elementy (zamiast zwracania 1)
• zakłada się, że powermultiset_by_cardinality zachowuje porządek, nawet jeśli nie jest to wyraźnie określone w dokumentacji

aukcja sqlplus

SQL> set heading off
SQL> with r(i,v)as(select rownum,value(t)from table(ku$_objnumset(6,3,2,4,5,1,8,7,9))t)
  2  select nvl(min(case when r.v<p.l and r.v>p.v then 0end),1)from r,
  3  (select i,lag(v)over(order by i)l,v from r)p where r.i+1<p.i
  4  /

                                            0

SQL> with function f(n ku$_objnumset,i int)return int as begin return n(i);end;
  2  select min(case when f(c,1)>f(c,2)or f(c,1)<f(c,3)then 1else 0end)
  3  from(select value(t)c from table(powermultiset_by_cardinality(ku$_objnumset(6,3,2,4,5,1,8,7,9),3))t)
  4  /

                                                     0

SQL> with r(i,v)as(select rownum,value(t)from table(ku$_objnumset(8,3,1,6,4,7,10,14,13))t)
  2  select nvl(min(case when r.v<p.l and r.v>p.v then 0end),1)from r,
  3  (select i,lag(v)over(order by i)l,v from r)p where r.i+1<p.i
  4  /

                                            1

SQL> with function f(n ku$_objnumset,i int)return int as begin return n(i);end;
  2  select min(case when f(c,1)>f(c,2)or f(c,1)<f(c,3)then 1else 0end)
  3  from(select value(t)c from table(powermultiset_by_cardinality(ku$_objnumset(8,3,1,6,4,7,10,14,13),3))t)
  4  /

                                                     1

Weryfikacja online apex.oracle.com

Aktualizacja

Oracle SQL, 155 bajtów

with r(i,v)as(select rownum,value(t)from table(a)t)select nvl(min(case when a.v<b.v and a.v>c.v then 0end),1)r from r a,r b,r c where a.i<b.i and b.i+1=c.i

C, 823 bajty (nie licząc białych znaków); 923 bajty (w tym białe znaki)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tree
{struct tree * left;struct tree * right;int val;}tree;static int * test_p = 0;
void insert_root(tree ** root, int in)
{if (*root == NULL){*root = (tree *)calloc(1,sizeof(tree));(*root)->val = in;return;}else if (in < (*root)->val){insert_root(&((*root)->left),in);}else{insert_root(&((*root)->right),in);}}
void preorder(tree * root)
{if ( root == 0x0 ) { return; }*test_p++ = root->val;preorder(root->left);preorder(root->right);}
int main(int argc, char ** argv)
{int test_list[argc-1];memset(test_list,0,argc*sizeof(int));test_p = test_list;tree * root = (tree *)calloc(1,sizeof(tree));root->val = strtol(argv[1],0x0,10);int i = 1;while ( argv[++i] != 0x0 ){insert_root(&root,strtol(argv[i],0x0,10));}preorder(root);test_p = test_list;i = 1;while ( ( i < argc ) ){if ( *test_p != strtol(argv[i],0x0,10) ){return 0;}test_p++;i++;}return 1;}

Wersja programu do odczytu znajduje się poniżej:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct tree
{
    struct tree * left;

    struct tree * right;

    int val;

} tree;


static int * test_p = 0;

void insert_root(tree ** root, int in)
{
  if (*root == NULL)
  {
    *root = (tree *)calloc(1,sizeof(tree));

    (*root)->val = in;

    return;
  }

  else if (in < (*root)->val)
  {
    insert_root(&((*root)->left),in);
  }

  else
  {
    insert_root(&((*root)->right),in);
  }
}

void preorder(tree * root)
{
    if ( root == 0x0 ) {  return; }

        *test_p++ = root->val;

        preorder(root->left);

        preorder(root->right);

}

int main(int argc, char ** argv)
{
    int test_list[argc-1];

    memset(test_list,0,argc*sizeof(int));

    test_p = test_list;

    tree * root = (tree *)calloc(1,sizeof(tree));

    root->val = strtol(argv[1],0x0,10);

    int i = 1;

    while ( argv[++i] != 0x0 )
    {
        insert_root(&root,strtol(argv[i],0x0,10));
    }

    preorder(root);

    test_p = test_list;

    i = 1;

    while ( ( i < argc ) )
    {
        if ( *test_p != strtol(argv[i],0x0,10) )
        {
            return 0;
        }

        test_p++;

        i++;
    }

    return 1;   
}

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.