Latar Belakang
Sebuah pohon biner adalah pohon berakar yang setiap node memiliki paling banyak dua anak.
Sebuah pohon biner berlabel adalah pohon biner yang setiap simpul diberi label dengan bilangan bulat positif; Selain itu, semua label berbeda .
Sebuah BST (pohon pencarian biner) adalah pohon biner berlabel dimana label setiap node lebih besar dari label semua node di subtree kiri, dan lebih kecil dari label semua node di subtree kanan. Misalnya, berikut ini adalah BST:
The pre-order traversal dari pohon biner berlabel didefinisikan oleh pseudo-kode berikut.
function preorder(node)
if node is null then
return
else
print(node.label)
preorder(node.left)
preorder(node.right)
Lihat gambar berikut untuk mendapatkan intuisi yang lebih baik:
Simpul pohon biner ini dicetak dalam urutan berikut:
F, B, A, D, C, E, G, I, H
Anda dapat membaca lebih banyak tentang BST di sini , dan lebih banyak tentang traversal pre-order di sini .
Tantangan
Diberikan daftar bilangan bulat , tugas Anda adalah menentukan apakah ada BST yang cetakan traversal pra-cetaknya persis .
Memasukkan
- Daftar bilangan bulat positif yang tidak kosong .
- Secara opsional, panjang .
Keluaran
- Nilai kebenaran jika adalah traversal pre-order dari beberapa BST.
- Nilai falsey sebaliknya.
Aturan
- Aturan standar untuk pengiriman yang valid , I / O , celah berlaku.
- Ini adalah kode-golf , sehingga solusi terpendek (dalam byte) menang. Seperti biasa, jangan biarkan solusi yang sangat pendek dalam bahasa golf mencegah Anda untuk mengirim jawaban yang lebih panjang dalam bahasa pilihan Anda.
- Ini bukan aturan, tetapi jawaban Anda akan lebih baik diterima jika itu termasuk tautan untuk menguji solusi dan penjelasan tentang cara kerjanya.
Contohnya
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
Lihatlah tautan ini (milik Kevin Cruijssen ) untuk melihat contohnya secara visual.
sumber
Jawaban:
JavaScript (Node.js) , 49 byte
Cobalah online!
Menggunakan fakta bahwa untuk array , adalah traversal pre-order dari beberapa BST iff .Sebuah0. . . Sebuahn - 1 Sebuah ∀ 0 ≤ i < j < n ; Sebuahsaya< aj - 1⟹Sebuahsaya< aj
Berkat Arnauld , hemat 1 byte.
sumber
Jelly , 7 byte
Cobalah online!
Pengembalian
[4]
untuk traversal, jika tidak[]
.Pada dasarnya menggunakan algoritma tsh: kondisi "mendiskualifikasi" untuk pre-order traversal adalah kelanjutan dari 3 elemen yang terlihat seperti [pertengahan, tinggi, rendah] . (Misalnya, [20, 30, 10].)
Kami ekuivalen memeriksa setiap subsequences dari setiap panjang yang memiliki indeks 4 dalam daftar permutasi mereka, yang semua daftar diurutkan seperti [a 1 ... sebuah k CDB] di mana sebuah i diurutkan dan sebuah i <b <c <d . (Setiap daftar tersebut didiskualifikasi jika kita melihat tiga elemen terakhir, dan masing-masing daftar diskualifikasi jelas dari formulir ini.)
Bukti
sumber
Java 10, 94 byte
Port jawaban JavaScript @tsh .
Cobalah online.
Penjelasan:
sumber
|=
. Saya berasumsi&=
juga akan bekerja?|=
dan&=
berfungsi sebagai jalan pintas untukb = b | condition
danb = b & condition
(tempat&
dan|
merupakan jalan pintas untuk&&
dan||
dalam kebanyakan kasus tentu saja).Ruby ,
46 4038 byteCobalah online!
Ini bekerja dengan secara rekursif mengambil elemen pertama
a
sebagai pivot, dan memeriksa apakah sisa array dapat dibagi menjadi dua (menggunakan persimpangan dan penyatuan: pertama hapus semua elemen> a, lalu tambahkan lagi di sebelah kanan dan periksa apakah ada sesuatu yang memiliki berubah).sumber
Retina 0.8.2 , 31 byte
Cobalah online! Tautan termasuk kasus uji. Gunakan algoritma @ tsh. Penjelasan:
Konversikan ke unary.
Temukan angka yang terletak di antara dua angka menurun berurutan berikutnya.
Pastikan jumlah kecocokan adalah nol.
sumber
Perl 6 , 38 byte
Cobalah online!
Penjelasan
sumber
Haskell , 50 byte
Cobalah online!
sumber
Scala (
6867 Bytes)Cobalah online
Jawaban Port of nwellnhof .
Scala (
122103 bytes)Terima kasih kepada @Laikoni untuk saran untuk membuat kedua solusi ini lebih pendek.
Cobalah online
Penjelasan:
span
) array menggunakan head array sebagai kriteria slicing.sumber
val (s,t)
,true
bisa1>0
dan Anda bisa turuns.forall(_<i(0))&
karena ini sudah harus diasuransikan olehspan
.%
dan menjatuhkan ruang: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)}
.. Versi 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)
.. Ada ide bagaimana membuat ini lebih pendek?05AB1E ,
1510 bytePort of @Lynn 's Jelly menjawab .
-5 byte terima kasih kepada @Emigna .
Cobalah secara online atau verifikasi semua kasus uji .
Penjelasan: "
sumber
ŒεD{3.IÊ}P
?Haskell , 41 byte
Cobalah online!
Menggunakan pengamatan Lynn bahwa itu sudah cukup untuk memeriksa bahwa tidak ada urutan untuk pertengahan ... tinggi ... rendah . Ini berarti bahwa untuk setiap elemen
h
, daftar element
yang muncul setelahnya adalah blok elemen yang<h
diikuti oleh blok elemen>h
(kedua blok mungkin kosong). Jadi, kode memeriksa bahwa setelah kita meletakkan awalan elemen<h
dalamt
, elemen yang tersisa semuanya>h
. Berulang memeriksa ini untuk setiap elemen awalh
sampai daftar panjangnya 1.Penyederhanaan yang potensial adalah bahwa itu cukup untuk memeriksa sub-pola pertengahan .. tinggi, rendah di mana dua terakhir berturut-turut. Sayangnya, Haskell's tidak memiliki cara pendek untuk mengekstraksi dua elemen terakhir, seperti yang dapat dilakukan dari depan dengan pencocokan pola
a:b:c
. Saya menemukan solusi yang lebih pendek yang memeriksa mid, high..low , tetapi ini gagal untuk menolak input seperti[3,1,4,2]
.Kasus uji yang diformat diambil dari Laikoni .
sumber
Japt , 14 byte
Japt Interpreter
Output
false
untuk BST,true
tanpa BST.Penjelasan:
sumber
Scala
Semua pendekatan adalah implementasi dari aturan yang ditunjukkan oleh tsh.
109
101
98
78
Jika itu harus fungsi dan bukan hanya ekspresi maka setiap baris harus mulai dengan (17 byte)
sumber
Oracle SQL, 177 byte
Karena tidak ada tipe boolean dalam Oracle SQL, kueri mengembalikan 1 atau 0.
Oracle SQL 12c, 210 byte
Itu tidak mungkin elemen akses array dalam SQL dengan cara yang sama seperti pada PL / SQL - yaitu a (i), dengan demikian fungsi
f
dideklarasikanwith clause
untuk tujuan itu. Kalau tidak, solusinya akan jauh lebih pendek.Keterbatasan lainnya
daftar sqlplus
Verifikasi online apex.oracle.com
Memperbarui
Oracle SQL, 155 byte
sumber
C, 823 byte (tidak termasuk karakter spasi); 923 byte (termasuk spasi putih)
Versi program yang dapat dibaca adalah di bawah ini:
Metode utama dalam program ini membaca daftar angka yang (diduga) merupakan preorder traversal yang sah.
Fungsi insert_root yang disebut menyisipkan integer ke dalam pohon pencarian biner di mana node sebelumnya berisi nilai yang lebih rendah dan node berikutnya berisi nilai int yang lebih besar.
Fungsi preorder (root) melintasi pohon dalam preorder traversal dan secara bersamaan menggabungkan setiap bilangan bulat algoritma datang ke test_list int array .
Final while loop menguji apakah masing-masing nilai int dalam daftar stdin dan orang-orang di test_list setara pada setiap indeks. Jika ada elemen daftar dari stdin yang gagal untuk mencocokkan elemen yang sesuai di test_list pada indeks masing-masing, fungsi utama mengembalikan 0. Lain dengan metode utama mengembalikan 1 .
Untuk menentukan main apa yang dikembalikan, ketikkan echo $ status ke terminal bash. BASH akan mencetak 1 atau 0.
sumber