Rumah > Artikel > pembangunan bahagian belakang > Siri Bercakap dengan Anda #2
Hari ini kami akan memulakan gambaran keseluruhan kami tentang konsep yang digunakan untuk menangani pelbagai masalah algoritma. Pemahaman tentang konsep tertentu mungkin memberi anda intuisi dari sudut mana untuk mula memikirkan kemungkinan penyelesaian.
Terdapat konsep yang berbeza tetapi tidak terlalu banyak di luar sana. Hari ini saya akan melaburkan perhatian anda ke dalam konsep tingkap gelongsor.
Konsep tingkap gelongsor adalah sedikit lebih terlibat, daripada pada pandangan pertama. Saya akan menunjukkannya dalam contoh praktikal. Buat masa ini, perlu diingat, idea konsep ialah kita akan mempunyai beberapa tetingkap yang perlu kita alihkan. Mari kita mulakan dari contoh dengan segera.
Andaikan anda mempunyai tatasusunan integer dan saiz subarray yang dipratakrifkan. Anda diminta untuk mencari subarray sedemikian (aka tetingkap) yang mana jumlah nilai akan menjadi maksimum antara lain.
array = [1, 2, 3] window_size = 2 # conceptually subarray_1 = [1, 2] --> sum 3 subarray_2 = [2, 3] --> sum 5 maximum_sum = 5
Nah, kelihatan agak mudah:
(1) tingkap gelongsor saiz 2
(2) 2 subbarray
(3) kira jumlah setiap
(4) cari maks antara mereka
Mari kita laksanakan.
def foo(array: List[int], size: int) -> int: maximum = float("-inf") for idx in range(size, len(array)+1): left, right = idx-size, idx window = array[left:right] maximum = max(maximum, sum(window)) return maximum
Nampaknya kami baru sahaja menggunakan konsep tingkap gelongsor dengan cekap. Sebenarnya, tidak betul-betul. Kita mungkin mendapat "bukti" itu dengan memahami kerumitan masa penyelesaian.
Kerumitannya ialah O(l)*O(w), dengan l ialah jumlah tetingkap dalam tatasusunan dan w ialah jumlah elemen dalam tetingkap. Dalam erti kata lain, kita perlu merentasi l tingkap dan untuk setiap tetingkap l-th kita perlu mengira jumlah elemen w.
Apa yang dipersoalkan di sini? Mari kita gambarkan secara konseptual lelaran untuk menjawab soalan.
array = [1, 2, 3, 4] window_size = 3 iterations 1 2 3 4 5 |___| |___| |___|
Jawapannya ialah walaupun kita meluncurkan tatasusunan, pada setiap lelaran kita perlu "mengira semula" elemen k-1 yang telah dikira pada lelaran sebelumnya.
Pada asasnya, pandangan ini sepatutnya mencadangkan kita untuk bertanya soalan:
"adakah terdapat cara untuk memanfaatkan pengiraan daripada langkah sebelumnya?"
Jawapannya ya. Kita boleh mendapatkan jumlah elemen tetingkap dengan menambah dan menolak yang pertama dan seterusnya selepas elemen tetingkap. Biar saya masukkan idea ini ke dalam kod.
def foo(array: List[int] = None, size: int = 0) -> int window_start, max_, window_sum_ = 0, float("-inf"), 0 for window_end in range(len(array)): if window_end > size - 1: window_sum_ -= array[window_start] window_start += 1 window_sum_ += array[window_end] max_ = max(max_, window_sum_) return max_ assert foo(array=[1, 2, 3, 4], size=3) == 9
Di sini kita mungkin melihat, apabila kita membina subarray panjang saiz, kita mula menolak elemen pertama daripada jumlah tetingkap, perkara yang membolehkan kita menggunakan semula pengiraan daripada langkah sebelumnya.
Sekarang, kami mungkin mengatakan kami menggunakan konsep tetingkap gelongsor dengan cekap manakala kami mendapat bukti yang memeriksa kerumitan masa, yang dikurangkan daripada O(l*w) kepada O(l), di mana l ialah jumlah tingkap yang kami akan slaid.
Idea utama yang ingin saya ketengahkan, konsep tetingkap gelongsor bukan sekadar menghiris yang boleh dilelang dengan tetingkap saiz tertentu.
Izinkan saya memberi anda beberapa masalah, di mana kita akan belajar cara mengesan masalah itu mungkin melibatkan konsep tetingkap gelongsor serta apa sebenarnya yang mungkin anda lakukan dengan tetingkap itu sendiri.
Memandangkan saya bercakap di sini hanya tentang konsep, saya akan melangkau "cara mengira sesuatu di dalam tetingkap".
Masalah satu
Memandangkan tatasusunan, cari purata semua subarray bersebelahan saiz K di dalamnya.
Baik, sekarang kita mungkin mentakrifkan pendekatan dengan cara: lelaran ke atas tatasusunan input dengan tetingkap saiz K. Pada setiap lelaran kira purata tetingkap ...
Masalah dua
Diberi tatasusunan nombor positif dan nombor positif K, cari jumlah maksimum bagi mana-mana subray bersebelahan saiz K.
Sekarang: lintasi tatasusunan input dengan tetingkap bersaiz K. Pada setiap lelaran kira jumlah tetingkap ...
Masalah tiga
Diberi tatasusunan nombor positif dan nombor positif S, cari panjang subarray bersebelahan terkecil yang jumlahnya lebih besar daripada atau sama dengan S.
Sekarang, kita mungkin mentakrifkan pendekatan dengan cara: "pertama, ulangi tatasusunan input dan bina tetingkap pertama sedemikian, yang akan memenuhi syarat (jumlah ialah >= hingga S). Setelah selesai, alihkan tetingkap, tetingkap pengurusan mula dan tamat ..."
Masalah empat
Diberi rentetan, cari panjang subrentetan terpanjang di dalamnya dengan tidak lebih daripada K aksara yang berbeza.
Pendekatan di sini lebih terlibat, jadi saya akan melangkaunya di sini.
Masalah lima
Memandangkan tatasusunan integer di mana setiap integer mewakili pokok buah-buahan, anda diberi dua bakul dan matlamat anda adalah untuk meletakkan bilangan maksimum buah-buahan dalam setiap bakul. Satu-satunya sekatan ialah setiap bakul boleh mempunyai satu jenis buah sahaja.
Anda boleh bermula dengan mana-mana pokok, tetapi anda tidak boleh melangkau pokok sebaik sahaja anda bermula. Anda akan memetik satu buah daripada setiap pokok sehingga anda tidak boleh, iaitu, anda akan berhenti apabila anda perlu memilih daripada jenis buah ketiga.
Tulis fungsi untuk mengembalikan bilangan maksimum buah dalam kedua-dua bakul.
Nampak tidak begitu ketara, mari kita mudahkan syaratnya dahulu.
Terdapat tatasusunan input. Tatasusunan mungkin mengandungi hanya 2 digit yang berbeza (baldi). Anda diminta untuk mencari subarray bersebelahan sedemikian yang panjangnya akan menjadi maksimum.
Kini lebih mudah untuk melihat kami mungkin bekerja dengan konsep tingkap gelongsor.
Masalah enam
Memandangkan rentetan dan corak, ketahui sama ada rentetan itu mengandungi sebarang pilihatur corak.
Pertama, kami mempunyai 2 tali, asli dan corak. Kami tahu kami entah bagaimana membandingkan asal dan corak, apa yang membawa kepada idea itu, kami perlu membina tetingkap saiz corak dan seterusnya melakukan semakan pilih atur. Ini bermakna, kita mungkin menggunakan konsep tingkap gelongsor.
Apabila anda berurusan dengan tingkap gelongsor, ingat soalan berikut:
Atas ialah kandungan terperinci Siri Bercakap dengan Anda #2. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!