Biorąc pod uwagę unikalną, posortowaną listę liczb całkowitych, utwórz zrównoważone drzewo wyszukiwania binarnego reprezentowane jako tablica bez użycia rekurencji.
Na przykład:
func( [1,2,3,5,8,13,21] ) => [5,2,13,1,3,8,21]
Zanim zaczniemy, wskazówka: możemy uprościć ten problem tonę, abyśmy nie musieli myśleć o wejściowych liczbach całkowitych (ani o żadnym podobnym obiekcie!).
Jeśli wiemy, że lista wejściowa jest już posortowana, jej zawartość nie ma znaczenia. Możemy po prostu pomyśleć o tym w kategoriach wskaźników w oryginalnej tablicy.
Wewnętrzna reprezentacja tablicy wejściowej staje się następnie:
func( [0,1,2,3,4,5,6] ) => [3,1,5,0,2,4,6]
Oznacza to, że zamiast pisać coś, co ma do czynienia z porównywalnymi obiektami, naprawdę wystarczy napisać funkcję, która odwzorowuje zakres z zakresu [0, n) na wynikową tablicę. Po otrzymaniu nowego zamówienia możemy po prostu zastosować mapowanie z powrotem do wartości na wejściu, aby utworzyć tablicę zwrotną.
Prawidłowe rozwiązania muszą:
- Zaakceptuj tablicę z zerowymi elementami i zwróć pustą tablicę.
- Zaakceptuj tablicę liczb całkowitych o długości n i zwróć tablicę liczb całkowitych
- O długości od n do następnej największej potęgi 2 minus 1. (np. Dla wielkości wejściowej 13 powróć gdziekolwiek między 13 a 15).
- Tablica reprezentująca BST, w której węzeł główny znajduje się w pozycji 0, a wysokość jest równa log (n), gdzie 0 oznacza brakujący węzeł (lub
null
podobną wartość, jeśli pozwala na to Twój język). Puste węzły, jeśli są obecne, muszą istnieć tylko na końcu drzewa (np.[2,1,0]
)
Wejściowa tablica liczb całkowitych ma następujące gwarancje:
- Wartości to 32-bitowe liczby całkowite ze znakiem większe od zera.
- Wartości są unikalne.
- Wartości są w porządku rosnącym od pozycji zero.
- Wartości mogą być rzadkie (tj. Nie przylegać do siebie).
Wygrywa najbardziej zwięzły kod według liczby znaków ascii, ale interesują mnie również eleganckie rozwiązania dla każdego konkretnego języka.
Przypadki testowe
Wyjścia w prostych układach zawierających 1
się n
na różne n
. Jak opisano powyżej, końcowe 0
s są opcjonalne.
[]
[1]
[2,1,0]
[2,1,3]
[3,2,4,1,0,0,0]
[4,2,5,1,3,0,0]
[4,2,6,1,3,5,0]
[4,2,6,1,3,5,7]
[5,3,7,2,4,6,8,1,0,0,0,0,0,0,0]
[6,4,8,2,5,7,9,1,3,0,0,0,0,0,0]
[7,4,9,2,6,8,10,1,3,5,0,0,0,0,0]
[8,4,10,2,6,9,11,1,3,5,7,0,0,0,0]
[8,4,11,2,6,10,12,1,3,5,7,9,0,0,0]
[8,4,12,2,6,10,13,1,3,5,7,9,11,0,0]
[8,4,12,2,6,10,14,1,3,5,7,9,11,13,0]
[8,4,12,2,6,10,14,1,3,5,7,9,11,13,15]
źródło
Odpowiedzi:
Ruby , 143
Jest to (luźno) skompresowana wersja następującego kodu, która zasadniczo wykonuje BFS na drzewie.
Poza tym, ponieważ jest to BFS, a nie DFS, wymóg nierekurencyjnego rozwiązania nie jest znaczący i stawia niektóre języki w niekorzystnej sytuacji.
Edycja: Naprawiono rozwiązanie, dzięki @PeterTaylor za komentarz!
źródło
Java , 252
Ok, oto moja próba. Bawiłem się operacjami bitowymi i wymyśliłem ten bezpośredni sposób obliczania indeksu elementu w BST na podstawie indeksu w oryginalnej tablicy.
Wersja skompresowana
Długa wersja znajduje się poniżej.
źródło
int[] b(int[] a)
jest równie dobrze wyrażone jakint[]b(int[]a)
.a.length
przydział tablicy. Zmień to nas
. Pozbądź się miejscafor (
wiele razy. Każda pętla for tworzyint i=0
takżeint t=0
. Twórz za pomocąn
(int n=0,i,t;
), a następnie tylkoi=0
w pętlach it=1
wewnątrz. Zadeklaruj wewnętrznylong x
i zalong I
pomocąs
i po prostu zainicjuj w pętli (long s=a.length,I,x;
ix=..
/I=..
). Nie powinieneś potrzebować spacji wokół pliku binarnego AND&
.I=I|..
może być zapisanaI|=..
źródło
Nie jestem pewien, czy pasuje to dokładnie do twoich wymagań dotyczących pustych węzłów znajdujących się na końcu drzewa i na pewno nie wygra żadnych nagród za zwięzłość, ale myślę, że jest poprawne i ma przypadki testowe :)
źródło
Golfscript (
9989)Zasadniczo prosty port mojego rozwiązania w języku Python działa prawie w ten sam sposób.
Prawdopodobnie można go nieco ulepszyć dzięki większej liczbie „golfizmów”, poprawionych już o 10 znaków z wkładem @ petertaylor :)
źródło
!{;}{}if
może być po prostu!{;}*
dlatego, że!
gwarancje zwrotu0
lub1
. Możesz używać tokenów niealfabetycznych dla zmiennych, więc jeśli użyjesz^
zamiastr
,|
zamiastx
,&
zamiasty
, możesz wyeliminować całą białą spację.Java 192
Mapuje indeks na wejściu do indeksu na wyjściu
Długa wersja:
źródło
Wolfram Mathematica 11, 175 bajtów
Funkcja
g[l]
przyjmuje jako dane wejściowe aList
(np.l={1,2,3,4,...}
) I zwraca aList
żądanej postaci. Działa w następujący sposób:x[a_]:=Floor@Min[i-#/2,#]&@(i=Length[a]+1;2^Ceiling@Log2[i]/2)
pobiera listę i znajduje katalog główny skojarzonego BST.i=Length[a]+1
skrót do długości listy2^Ceiling@Log2[i]/2
górna granica wartości korzeniaMin[i-#/2,#]&@(...)
Minimum dwa argumenty, gdzie#
oznacza to, co jest w środku(...)
l//.{...}
Zastosuj wielokrotnie następujące zasady zastępowanial
{}->{}
Nic do zrobienia (jest to przypadek na krawędzi, aby uniknąć nieskończonej pętli)b__List:>(n[Take[b,#-1],b[[#]],Drop[b,#]]&@x[b])
PodzielList
na{{lesser}, root, {greater}}
Cases[...,_Integer,{m}]
Weź wszystkie liczby całkowite na poziomie (głębokość)m
Table[...,{m,1,x[l]}]
Dla wszystkichm
dox[l]
(co w rzeczywistości jest więcej niż to konieczne).Można to przetestować, uruchamiając
Ta implementacja nie zawiera końcowych zer.
źródło
Python (
175171)Dość skondensowane, wciąż dość czytelne;
Zwraca wynik, więc można go nad nim zapętlić lub (do celów wyświetlania) wydrukować jako listę;
źródło
Jawa
Jest to bezpośrednie rozwiązanie obliczeniowe. Myślę, że to działa, ale ma jeden pragmatycznie niewinny efekt uboczny. Tablica, którą tworzy, może być uszkodzona, ale nie może to w żaden sposób wpływać na wyszukiwanie. Zamiast produkować 0 (zerowych) węzłów, utworzy nieosiągalne węzły, to znaczy węzły zostały już wcześniej znalezione w drzewie podczas wyszukiwania. Działa poprzez mapowanie tablicy indeksów o regularnej sile 2-wymiarowej tablicy drzewa wyszukiwania binarnego na nieregularną tablicę drzewa wyszukiwania binarnego. Przynajmniej myślę, że to działa.
Oto bardziej skrócona wersja (tylko sparowana funkcja i nazwy). Wciąż jest biała przestrzeń, ale nie martwię się o wygraną. Również ta wersja faktycznie zajmuje tablicę. Drugi wziął int dla najwyższego indeksu w tablicy.
źródło
GolfScript (
79 7770 znaków)Ponieważ przykład w pytaniu używa funkcji, uczyniłem ją funkcją. Usunięcie w
{}:f;
celu pozostawienia wyrażenia, które pobiera dane wejściowe ze stosu i pozostawia BST na stosie, pozwoliłoby zaoszczędzić 5 znaków.Demo online (uwaga: aplikacja może trochę się rozgrzać: przekroczyła limit czasu dwa razy przed uruchomieniem za 3 sekundy).
Z białymi znakami, aby pokazać strukturę:
źródło
J , 52 bajty
funkcja pobiera posortowaną listę i zwraca w kolejności drzewa binarnego
zauważ, że drzewa mają identyczny kształt, ale dolny poziom jest skrócony
`1:
zacznij od 1<.@(2&^.)@>:@#
iteruj według podłogi log2 (długość + 1)+: , >:@+:@i.@>:@#
pętla: dołącza podwójny ostatni wektor o liczbach nieparzystych 1,3 .. 2 * długość + 1# /:@{.
weź tylko wymaganą liczbę przedmiotów i uzyskaj ich indeksy sortowania/:
zastosuj te wskaźniki sortowania do podanych danych wejściowychTIO
źródło
Python 2 , 107 bajtów
Golf odpowiedzi Joachima Isakssona: Input jest singletonem zawierającym listę.
Wypróbuj online!
źródło