Hari ini saya menemukan pertanyaan algoritma yang sangat menarik. Berikut ini adalah deskripsi algoritma, yang berasal dari pertanyaan wawancara di Twitter.
Deskripsi Algoritma Puding Twitter
Lihat gambar dulu
Angka -angka pada gambar di atas dijelaskan sesuai dengan konten array. Akhirnya, ketinggian dinding akan disimulasikan sesuai dengan ukuran setiap angka, dan dinding akan dihasilkan. Tanyakan kepada Anda, saat hujan, berapa banyak air yang dapat diisi dengan dinding ini, dalam 1 sebagai unit penghitungan.
Ini dinding setelah mengisi air
Setelah membaca gambar di atas, apakah Anda merasa itu menyenangkan? Memang, mari kita analisis secara singkat implementasi algoritma di bawah ini.
Bahkan, prinsip ini relatif sederhana, ada beberapa poin penting:
1. Jelas tidak ada air di sisi kiri dan kanan
2. Ketinggian beban air tergantung pada nilai minimum dari dua nilai maksimum di sisi kiri dan kanan diri
Mari kita gunakan JS untuk mengimplementasikannya:
Salinan kode adalah sebagai berikut:
/**
* Hitung berapa banyak air yang dapat dipasang di dinding dengan istilah array sebagai ketinggian
* Contoh array [2,5,1,2,3,4,7,7,6,9]
**/
fungsi getWaterCounts (arg) {
var i = 0,
j = 0,
hitung = 0;
// item pertama dan terakhir harus dikecualikan
untuk (i = 1; i <arg.length - 1; i ++) {
var left = math.max.Apply (null, arg.slice (0, i + 1));
var right = math.max.Apply (null, arg.slice (i, arg.length));
var min = kiri> = kanan? Kanan: kiri;
// Nilai maksimum sisi kiri dan kanan akan berlaku
// Jika nilai saat ini lebih besar dari atau sama dengan nilai ini, tidak melakukan apa -apa
if (arg [i] <min) {
hitung += min - arg [i];
}
}
Console.log (Count);
}
getWaterCounts ([2,5,1,2,3,4,7,7,6,9]); // 11
Meringkaskan
Hehe, bukankah implementasinya cukup sederhana? Bahkan, selama Anda bersedia berpikir, Anda dapat menggunakan JS untuk mengimplementasikan banyak hal menyenangkan.