Kira Tetingkap yang Memenuhi Peraturan
Helah paling banyak-K ditolak paling banyak-(K-1).
Kira Tetingkap yang Memenuhi Peraturan ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Mengira, Bukan Mengukur
Kadangkala Anda perlu mengira sublarik yang memenuhi peraturan, bukannya mencari yang terpanjang. Satu helah kecil menjadikannya kerja tetingkap gelongsor yang mudah. 🔢
Cabaran Tepat-K
Mengira sublarik dengan tepat K kejadian sesuatu secara langsung adalah janggal. Sempadannya sentiasa berubah, lalu satu tetingkap yang kemas sukar dibina.
Susun Semula kepada Paling Banyak
Mengira sublarik dengan paling banyak K kejadian jauh lebih mudah menggunakan satu tetingkap. Apabila Anda mengembangkan kanan, setiap kiri yang sah menghasilkan satu sublarik untuk dikira.
Helah Penolakan
Tepat K bersamaan atMost(K) tolak atMost(K - 1). Dua kiraan mudah digabungkan untuk mendapatkan kiraan sukar yang sebenarnya diperlukan.
answer = at_most(k) - at_most(k - 1)Bina Fungsi Pembantu
Tulis satu fungsi yang mengira sublarik dengan paling banyak k kejadian. Fungsi itu menggelongsorkan tetingkap dan mengecilkannya apabila kiraan melebihi k.
def at_most(k):
left = 0
total = 0Kecilkan Apabila Berlaku Pelanggaran
Kembangkan kanan dan kemas kini tetingkap. Selagi tetingkap mengandungi lebih daripada k, gerakkan kiri ke hadapan untuk mengembalikannya dalam julat.
while count > k:
# remove a[left]
left += 1Tambah Kiraan Tetingkap
Selepas membetulkan tetingkap, setiap sublarik yang berakhir di kanan dan bermula dari kiri atau selepasnya adalah sah. Tambahkan kanan tolak kiri tambah satu.
total += right - left + 1Mengapa Kiraan Itu Berfungsi
Bagi kanan yang tetap, kedudukan mula yang sah ialah kiri, kiri+1, hingga kanan. Itu tepat right - left + 1 sublarik, dan semuanya memenuhi syarat paling banyak k.
Gabungkan Dua Panggilan
Jalankan fungsi pembantu dua kali dan tolakkan hasilnya. Setiap panggilan ialah O(n), jadi keseluruhan kiraan tepat-K masih linear.
return at_most(k) - at_most(k - 1)Kendalikan Kes Tepi
Apabila k ialah sifar, atMost(k - 1) akan menggunakan negatif satu. Kendalikan kes itu supaya fungsi pembantu tetap memulangkan kiraan sifar yang munasabah.
Tempat Ia Digunakan
Idea at-most tolak at-most ini sesuai untuk mengira sublarik dengan tepat K nilai berbeza, K nombor ganjil atau apa-apa sifat per tetingkap yang monoton.
Semakan Pantas
Anda mahu mengira sublarik dengan tepat K unsur yang berbeza.
Ringkasan
Mengira tepat K hanyalah atMost(K) tolak atMost(K - 1). Setiap fungsi pembantu menggelongsorkan tetingkap dalam O(n), jadi keseluruhan kiraan kekal linear. ✅
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Kira Tetingkap yang Memenuhi Peraturan” percuma?
Ya — teks penuh “Kira Tetingkap yang Memenuhi Peraturan” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Kira Tetingkap yang Memenuhi Peraturan”?
Helah paling banyak-K ditolak paling banyak-(K-1). Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “Kira Tetingkap yang Memenuhi Peraturan” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Jumlah Tetingkap Saiz Tetap
- Tetingkap Berubah dengan Dua Penuding
- Subrentetan Terpanjang Tanpa Ulangan
- Kira Tetingkap yang Memenuhi Peraturan