Siri Bercakap dengan Anda #2

Pengenalan

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.

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.

Gambaran Keseluruhan Masalah

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.

1. Tingkap gelongsor ? - subarray bersebelahan kata kunci pertama, bermakna kita harus menjaga tingkap, yang akan mewakili subarray bersebelahan.
2. Adakah kita tahu saiz tingkap gelongsor? - yeap, K, kami mendapat saiz tingkap, yang sepatutnya panjang K.
3. Apakah sebenarnya yang kita patut urus/semak dalam tetingkap gelongsor? - cari purata bagi...

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.

1. Tingkap gelongsor ? - subarray bersebelahan sekali lagi, kata kunci pertama, bermakna kita harus menjaga tingkap, yang akan mewakili subarray bersebelahan.
2. Adakah kita tahu saiz tingkap gelongsor? - yeap, K, kami mendapat saiz tingkap, yang sepatutnya panjang K.
3. Apakah sebenarnya yang kita patut urus/semak dalam tetingkap gelongsor? - .. jumlah ...

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.

1. Tingkap gelongsor ? - subarray bersebelahan sekali lagi, kata kunci pertama, bermakna kita harus menjaga tingkap, yang akan mewakili subarray bersebelahan.
2. Adakah kita tahu saiz tingkap gelongsor? - sebenarnya tidak, kita perlu memikirkannya.
3. Apakah sebenarnya yang kita patut urus/semak dalam tetingkap gelongsor? - ... jumlah ialah >= kepada 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.

1. Tingkap gelongsor ? - subrentetan terpanjang, kata kunci pertama, bermakna kita harus menjaga tingkap, yang akan mewakili subrentetan.
2. Adakah kita tahu saiz tingkap gelongsor? - tidak, kita perlu memikirkannya.
3. Apakah sebenarnya yang kita patut urus/semak dalam tetingkap gelongsor? - ... jumlah 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.

1. Tingkap gelongsor ? - subaray bersebelahan
2. Adakah kita tahu saiz tingkap gelongsor? - tidak, kita perlu memikirkannya.
3. Apakah sebenarnya yang kita patut urus/semak dalam tetingkap gelongsor? - ... sama ada digit berbeza dan panjang tetingkap ...

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.

Outro

Apabila anda berurusan dengan tingkap gelongsor, ingat soalan berikut:

• adakah anda faham saiz tingkap
• adakah anda faham cara membina tetingkap
• adakah anda faham cara mengalih/mengecilkan tingkap
• adakah anda faham apakah tetingkap yang sah/tidak sah
• adakah anda faham cara menjadikan tetingkap yang tidak sah itu sah

Atas ialah kandungan terperinci Siri Bercakap dengan Anda #2. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!