Diberikan daftar unik, diurutkan dari bilangan bulat, buat pohon pencarian biner seimbang yang diwakili sebagai array tanpa menggunakan rekursi.
Sebagai contoh:
func( [1,2,3,5,8,13,21] ) => [5,2,13,1,3,8,21]
Sebelum kita mulai, sebuah petunjuk: kita dapat menyederhanakan masalah ini satu ton sehingga kita tidak benar-benar harus memikirkan bilangan bulat input (atau objek yang sebanding dalam hal ini!).
Jika kita tahu daftar input sudah disortir, isinya tidak relevan. Kita bisa memikirkannya dalam hal indeks ke dalam array asli.
Representasi internal dari array input kemudian menjadi:
func( [0,1,2,3,4,5,6] ) => [3,1,5,0,2,4,6]
Ini berarti daripada menulis sesuatu yang harus berurusan dengan objek yang sebanding, kita benar-benar hanya perlu menulis fungsi yang memetakan dari rentang [0, n) ke array yang dihasilkan. Setelah kami memiliki orde baru, kami cukup menerapkan pemetaan kembali ke nilai-nilai dalam input untuk membuat array kembali.
Solusi yang valid harus:
- Terima array elemen-nol dan kembalikan array kosong.
- Terima array integer dengan panjang n dan kembalikan array integer
- Panjang antara n dan daya tertinggi berikutnya 2 minus 1. (misalnya, untuk ukuran input 13 kembali di mana saja antara 13 dan 15).
- Array yang mewakili BST di mana simpul akar berada di posisi 0 dan tingginya sama dengan log (n) di mana 0 mewakili simpul yang hilang (atau
null
nilai -seperti jika bahasa Anda memungkinkan). Node kosong, jika ada, harus hanya ada di ujung pohon (misalnya,[2,1,0]
)
Array integer input memiliki jaminan berikut:
- Nilai adalah bilangan bulat bertanda 32-bit yang lebih besar dari nol.
- Nilai unik.
- Nilai berada dalam urutan menaik dari posisi nol.
- Nilai mungkin jarang (yaitu, tidak berdekatan satu sama lain).
Kode paling singkat menurut jumlah karakter ascii menang, tapi saya juga tertarik melihat solusi elegan untuk bahasa tertentu.
Uji kasus
Output untuk array sederhana yang berisi 1
untuk n
untuk berbagai n
. Seperti dijelaskan di atas, trailing 0
s adalah opsional.
[]
[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]
sumber
Jawaban:
Ruby , 143
Ini adalah (secara longgar) versi terkompresi dari kode berikut yang pada dasarnya melakukan BFS di pohon.
Selain itu, karena BFS, bukan DFS, persyaratan solusi non-rekursif tidak signifikan, dan menempatkan beberapa bahasa pada posisi yang kurang menguntungkan.
Sunting: Solusi tetap, terima kasih kepada @PeterTaylor untuk komentarnya!
sumber
Jawa , 252
Ok, ini usahaku. Saya telah bermain-main dengan operasi bit dan saya datang dengan cara langsung menghitung indeks elemen dalam BST dari indeks dalam array asli.
Versi terkompresi
Versi panjangnya mengikuti di bawah ini.
sumber
int[] b(int[] a)
diekspresikan jugaint[]b(int[]a)
.a.length
alokasi array. Ubah kes
. Singkirkan ruang antarafor (
beberapa kali. Masing-masing untuk loop menciptakanint i=0
dan jugaint t=0
. Buat dengann
(int n=0,i,t;
) dan kemudian hanyai=0
di loop dant=1
di dalam. Deklarasikan bagian dalamlong x
danlong I
dengans
dan baru saja diinisialisasi dalam loop (long s=a.length,I,x;
danx=..
/I=..
). Anda seharusnya tidak memerlukan spasi di sekitar biner DAN&
.I=I|..
dapat ditulisI|=..
sumber
Tidak yakin apakah ini cocok dengan kebutuhan Anda akan node kosong berada di ujung pohon dan itu pasti tidak akan memenangkan hadiah untuk singkatnya, tapi saya pikir itu benar dan ia memiliki test case :)
sumber
Golfscript (
9989)Pada dasarnya port langsung dari solusi Python saya, bekerja dengan cara yang hampir sama.
Mungkin bisa ditingkatkan sedikit dengan lebih banyak "golfisms", sudah ditingkatkan oleh 10 karakter dengan input @ petertaylor :)
sumber
!{;}{}if
bisa saja!{;}*
karena!
jaminan untuk kembali0
atau1
. Anda dapat menggunakan token non-abjad untuk variabel, jadi jika Anda menggunakan^
bukanr
,|
bukanx
,&
bukany
Anda dapat menghilangkan semua spasi itu.Jawa 192
Indeks peta di input ke indeks di output
Versi panjang:
sumber
Wolfram Mathematica 11, 175 Bytes
Fungsi ini
g[l]
mengambil input aList
(misalnyal={1,2,3,4,...}
) dan mengembalikan aList
dari bentuk yang diinginkan. Ia bekerja sebagai berikut:x[a_]:=Floor@Min[i-#/2,#]&@(i=Length[a]+1;2^Ceiling@Log2[i]/2)
mengambil daftar dan menemukan akar BST terkait.i=Length[a]+1
pintas untuk panjang daftar2^Ceiling@Log2[i]/2
batas atas pada nilai rootMin[i-#/2,#]&@(...)
Minimal dari dua argumen di mana#
singkatan dari apa yang ada di dalam(...)
l//.{...}
Terapkan berulang kali aturan penggantian yang diikutil
{}->{}
Tidak ada yang dilakukan (ini adalah tepi kasus untuk menghindari loop tak terbatas)b__List:>(n[Take[b,#-1],b[[#]],Drop[b,#]]&@x[b])
MembagiList
menjadi{{lesser}, root, {greater}}
Cases[...,_Integer,{m}]
Ambil semua bilangan bulat di level (kedalaman)m
Table[...,{m,1,x[l]}]
Untuk semuam
sampai denganx[l]
(yang lebih dari yang diperlukan sebenarnya).Itu bisa diuji dengan menjalankan
Implementasi ini tidak termasuk trailing zero.
sumber
Python (
175171)Cukup padat, masih cukup mudah dibaca;
Ini menghasilkan hasilnya kembali, sehingga Anda dapat mengulanginya atau (untuk tujuan tampilan) mencetaknya sebagai daftar;
sumber
Jawa
Ini adalah solusi perhitungan langsung. Saya pikir itu berhasil, tetapi memiliki satu efek samping yang pragmatis tidak berbahaya. Array yang dihasilkannya mungkin rusak tetapi tidak dengan cara apa pun yang akan memengaruhi pencarian. Alih-alih menghasilkan 0 (null) node, itu akan menghasilkan node yang tidak dapat dijangkau, yaitu node yang sudah ditemukan sebelumnya di pohon selama pencarian. Ia bekerja dengan memetakan larik indeks kekuatan reguler 2 susunan pohon pencarian biner ke susunan pohon pencarian biner berukuran tidak teratur. Setidaknya, saya pikir itu berhasil.
Ini versi yang lebih ringkas (hanya fungsi dan nama yang dipasangkan). Masih ada ruang putih, tapi saya tidak khawatir menang. Versi ini juga membutuhkan array. Yang lain hanya mengambil int untuk indeks tertinggi dalam array.
sumber
GolfScript (
79 7770 karakter)Karena contoh dalam pertanyaan menggunakan fungsi, saya membuat fungsi ini. Menghapus
{}:f;
untuk meninggalkan ekspresi yang mengambil input pada stack dan meninggalkan BST pada stack akan menghemat 5 karakter.Demo online (catatan: aplikasi mungkin butuh sedikit pemanasan: waktunya habis untuk saya sebelum berjalan dalam 3 detik).
Dengan spasi untuk menampilkan struktur:
sumber
J , 52 byte
fungsi mengambil daftar yang diurutkan dan mengembalikan dalam urutan pohon biner
perhatikan bahwa pohon memiliki bentuk yang identik tetapi level bawahnya lebih pendek
`1:
mulai dengan 1<.@(2&^.)@>:@#
beralih dengan lantai log2 (panjang + 1)+: , >:@+:@i.@>:@#
loop: menambahkan dua kali lipat dari vektor terakhir dengan angka ganjil 1,3 .. 2 * panjang + 1# /:@{.
hanya ambil jumlah item yang diperlukan dan dapatkan indeks sortirnya/:
terapkan indeks semacam itu ke input yang diberikanTIO
sumber
Python 2 , 107 byte
Golf dari jawaban Joachim Isaksson , Input adalah singleton yang berisi daftar.
Cobalah online!
sumber