Задний план

Бинарное дерево является внедренным деревом, каждый узел имеет не более двух детей.

Меченное бинарное дерево представляет собой бинарное дерево, каждый узел обозначен с положительным целым числом; Более того, все ярлыки различны .

БСТ (бинарное дерево поиска) представляет собой меченый бинарное дерево , в котором метка каждого узла больше , чем этикетках всех узлов в левом поддереве, и меньше , чем этикетках всех узлов в его правого поддерева. Например, следующее является BST:

Обход предварительного порядка для помеченного двоичного дерева определяется следующим псевдокодом.

function preorder(node)
    if node is null then
        return
    else
        print(node.label)
        preorder(node.left)
        preorder(node.right)

Смотрите следующее изображение, чтобы получить лучшую интуицию:

Вершины этого двоичного дерева печатаются в следующем порядке:

F, B, A, D, C, E, G, I, H

Вы можете прочитать больше о BST здесь и больше о предварительном заказе здесь .

Вызов

Учитывая список целых чисел $a$ , ваша задача состоит в том, чтобы определить, существует ли BST, чей обход при предварительном заказе печатает ровно $a$ .

вход

• Непустой список различных положительных целых чисел $a$ .
• Опционально, длина $a$ .

Выход

• Truthy значение , если является предзаказ обход некоторых BST.$a$
• Falsey значение в противном случае.

правила

• Применяются стандартные правила для действительных представлений , ввода / вывода , лазеек .
• Это код-гольф , поэтому выигрывает самое короткое (в байтах) решение . Как обычно, не позволяйте смехотворно коротким решениям на языках игры в гольф отговаривать вас публиковать более длинные ответы на выбранном вами языке.
• Это не правило, но ваш ответ будет лучше принят, если он будет содержать ссылку для проверки решения и объяснение того, как оно работает.

Примеры

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

Проверьте эту ссылку (любезно предоставлено Кевином Круйссеном ), чтобы наглядно увидеть примеры.

JavaScript (Node.js) , 49 байт

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

Попробуйте онлайн!

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

Благодаря Арно , сэкономьте 1 байт.

Желе , 7 байт

ŒPŒ¿€4ḟ

Попробуйте онлайн!

Возвращает [4]для обходов, в противном случае [].

По сути, используется алгоритм tsh: условие «дисквалификации» для обхода предварительного заказа - это подпоследовательность из 3 элементов, которая выглядит как [средний, высокий, низкий] . (Например, [20, 30, 10].)

Мы то же самое проверить любые подпоследовательности любой длины , которые имеют индекс 4 в их списках перестановок, которые все списки сортируются как [а ₁ ... A _к CDB] , где _я сортирую и _я <Ь <с <d . (Каждый такой список дисквалифицирует, если мы посмотрим на последние три элемента, и каждый дисквалифицирующий список, очевидно, имеет такую ​​форму.)

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

доказательство

Обход предварительного заказа не содержит дисквалифицирующих подпоследовательностей.

Базовый случай: обход (•) - пустой список. ✓

Индукция: обход (t) : обход t.root ++ (t.left) ++ обход (t.right) .

Пусть [a, b, c] - подпоследовательность этого. Покажем, что c <a <b невозможно.

• Если t.root = a , то для c <a <b требуется c ∈ t.left и b ∈ t.right , поэтому [a, b, c] - неправильный порядок.
• Если a, b, c ∈ t.left или a, b, c ∈ t.right , используйте гипотезу индукции.
• Если a ∈ t.left и c ∈ t.right, то c> a .

Список различных целых чисел без дисквалифицирующих подпоследовательностей является обходом предварительного заказа BST

Если список пуст, это обход тривиального BST •.

Если список возглавляется, за ним следует хвост :

• Пусть less будет самым длинным префиксом tail элементов меньше, чем head , и пусть more будет остальной частью списка.
• Тогда more [1]> head и все остальные more [i] тоже больше, чем head (иначе [head, more [1], more [i]] будет дисквалифицирующей подпоследовательностью).
• Recurse: превращайте все меньше и больше в BST.

• Теперь наш список является обходом

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

  и это дерево является действительным BST.

Java 10, 94 байта

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;}

Порт @tsh 'JavaScript ответа .

Попробуйте онлайн.

Объяснение:

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

Рубин , 46 40 38 байт

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

Попробуйте онлайн!

Это работает путем рекурсивного принятия первого элемента aв качестве точки поворота и проверки, можно ли разбить оставшуюся часть массива на две части (используя пересечение и объединение: сначала удалите все элементы> a, затем добавьте их снова справа и проверьте, что-то изменено).

Сетчатка 0.8.2 , 31 байт

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

Попробуйте онлайн! Ссылка включает в себя тестовые случаи. Использует алгоритм @ tsh. Объяснение:

\d+
$*

Преобразовать в одинарный.

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

Найти числа, которые лежат между двумя последовательными по убыванию числами.

^0

Убедитесь, что количество совпадений равно нулю.

Perl 6 , 38 байт

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

Попробуйте онлайн!

объяснение

 *.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 байтов

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

Попробуйте онлайн!

Скала ( 68 67 байт)

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

Попробуйте онлайн

Порт ответа @ nwellnhof .

Scala ( 122 103 байта)

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)}

Спасибо @Laikoni за предложения сделать оба решения короче.

Попробуйте онлайн

Объяснение:

1. Нарезать (используя Scala span) массив, используя в качестве критерия нарезки заголовок массива.
2. Убедитесь, что первый срез массива меньше заголовка, а второй срез больше заголовка.
3. рекурсивно проверить, что каждый срез также удовлетворяет (2)

05AB1E , 15 10 байт

ŒεD{3.IÊ}P

Порт @Lynn 's Jelly ответа .
-5 байт благодаря @Emigna .

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение: "

Π            # 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 байт

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

Попробуйте онлайн!

Использует наблюдение Линн о том, что достаточно проверить, что нет подпоследовательности для mid..high..low . Это означает, что для каждого элемента hсписок элементов, tкоторый следует после, является блоком элементов, <hза которым следует блок элементов >h(оба блока могут быть пустыми). Итак, код проверяет, что после удаления префикса элементов<h в tоставшиеся элементы все >h. Повторяющиеся проверяют это для каждого начального элемента, hпока список не станет длиной 1.

Потенциальное упрощение состоит в том, что достаточно проверить субпаттерны в середине ... высоко, низко, где последние два последовательны. К сожалению, у Haskell нет короткого способа извлечь последние два элемента, как это можно сделать спереди с помощью сопоставления с образцом a:b:c. Я нашел более короткое решение, которое проверяет средний, высокий .. низкий , но это не в состоянии отклонить входные данные, как [3,1,4,2].

Отформатированные тестовые наборы взяты из Laikoni .

Japt , 14 байт

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

Japt Переводчик

Выходы falseдля BST,true без BST.

Объяснение:

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

Все подходы являются реализациями правила, показанного в 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)

Если это должна быть функция, а не просто выражение, то каждая строка должна начинаться с (17 байт)

def%(l:Seq[Int])=

Oracle SQL, 177 байт

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

Поскольку в Oracle SQL логический тип отсутствует, запрос возвращает 1 или 0.

Oracle SQL 12c, 210 байт

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)

Не возможно получить доступ к элементу массива в SQL так же, как в PL / SQL - то есть a (i), таким образом, функция fбыла объявлена with clauseдля этой цели. В противном случае решение было бы намного короче.

Другие ограничения

• выдает исключение для массивов короче 3-х элементов (вместо возврата 1)
• есть предположение, что powermultiset_by_cardinality сохраняет порядок, хотя это явно не указано в документации

листинг 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

Онлайн проверка apex.oracle.com

Обновить

Oracle SQL, 155 байт

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 байта (не считая пробельных символов); 923 байта (включая пробелы)

#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;}

Читаемая версия программы ниже:

#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;   
}

Основной метод в этой программе читает список чисел, которые (предположительно) являются законным обходом предварительного заказа.

Вызываемая функция insert_root вставляет целые числа в двоичное дерево поиска, где предыдущие узлы содержат меньшие значения, а следующие узлы содержат большие значения int.

Функция preorder (root) обходит дерево в обходе preorder и одновременно объединяет каждое целое число, которое алгоритм находит в массиве int находит в test_list .

Последний цикл while проверяет , эквивалентны ли каждое из значений int в списке stdin и значений в test_list для каждого индекса. Если есть элемент списка из stdin, который не соответствует соответствующему элементу в test_list по соответствующему индексу, функция main возвращает 0. Иначе метод main возвращает 1 .

Чтобы определить, что вернуло main, наберите echo $ status в терминале bash. BASH либо распечатает 1 или 0.