Menghitung Window yang Memenuhi Aturan
Trik at-most-K dikurangi at-most-(K-1)
Menghitung Window yang Memenuhi Aturan adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Menghitung, Bukan Mengukur
Terkadang Anda harus menghitung sublarik yang memenuhi suatu aturan, bukan mencari yang terpanjang. Trik sederhana mengubahnya menjadi pekerjaan jendela geser yang mudah. 🔢
Tantangan Tepat-K
Menghitung sublarik yang memiliki tepat K dari sesuatu secara langsung terasa rumit. Batasnya terus berubah, sehingga sulit membuat satu jendela yang rapi.
Merumuskan Ulang sebagai Paling Banyak
Menghitung sublarik dengan jumlah paling banyak K jauh lebih mudah menggunakan satu jendela. Saat Anda memperluas kanan, setiap posisi kiri yang valid menghasilkan satu sublarik yang dapat dihitung.
Trik Pengurangan
Tepat K sama dengan atMost(K) dikurangi atMost(K - 1). Dua hitungan mudah digabungkan untuk memperoleh hitungan rumit yang sebenarnya Anda inginkan.
answer = at_most(k) - at_most(k - 1)Buat Fungsi Pembantu
Tulislah satu fungsi yang menghitung sublarik dengan jumlah paling banyak k. Fungsi ini menggeser jendela dan mengecilkannya setiap kali hitungannya melebihi k.
def at_most(k):
left = 0
total = 0Kecilkan Saat Melanggar Aturan
Perluas kanan dan perbarui jendela. Selama jumlahnya lebih banyak daripada k, geser kiri maju untuk mengembalikannya ke dalam batas.
while count > k:
# remove a[left]
left += 1Tambahkan Hitungan Jendela
Setelah jendela diperbaiki, setiap sublarik yang berakhir di kanan dan memiliki titik awal dari kiri hingga kanan adalah valid. Tambahkan kanan dikurangi kiri ditambah satu.
total += right - left + 1Mengapa Hitungan Itu Benar
Untuk kanan yang tetap, titik awal yang valid adalah kiri, kiri+1, hingga kanan. Jadi, terdapat tepat kanan - kiri + 1 sublarik, dan semuanya memenuhi kondisi paling banyak k.
Gabungkan Dua Pemanggilan
Jalankan fungsi pembantu dua kali lalu kurangkan. Setiap pemanggilan membutuhkan O(n), sehingga hitungan tepat-K secara keseluruhan tetap linear.
return at_most(k) - at_most(k - 1)Tangani Kasus Tepi
Saat k bernilai nol, atMost(k - 1) akan menggunakan negatif satu. Tangani kasus tersebut agar fungsi pembantu tetap mengembalikan hitungan nol yang masuk akal.
Penerapannya
Gagasan paling banyak dikurangi paling banyak ini cocok untuk menghitung sublarik dengan tepat K nilai berbeda, K bilangan ganjil, atau sifat per jendela monoton lainnya.
Pemeriksaan Cepat
Anda ingin menghitung sublarik yang memiliki tepat K elemen berbeda.
Ringkasan
Menghitung tepat K cukup dilakukan dengan atMost(K) dikurangi atMost(K - 1). Setiap fungsi pembantu menggeser jendela dalam O(n), sehingga keseluruhan hitungan tetap linear. ✅
Belajar Coding Interview Prep dengan tutor AI — gratis
Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Menghitung Window yang Memenuhi Aturan” gratis?
Ya — teks lengkap “Menghitung Window yang Memenuhi Aturan” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Menghitung Window yang Memenuhi Aturan”?
Trik at-most-K dikurangi at-most-(K-1) Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “Menghitung Window yang Memenuhi Aturan” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Jumlah Window Berukuran Tetap
- Window Variabel dengan Two Pointer
- Substring Terpanjang Tanpa Pengulangan
- Menghitung Window yang Memenuhi Aturan