Subrentetan Terpanjang Tanpa Ulangan
Jejaki kedudukan terakhir dalam tetingkap.
Subrentetan Terpanjang Tanpa Ulangan ialah pelajaran Competitive Programming Academy percuma di CoddyKit. Ini ialah pelajaran 3 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 Competitive Programming Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Competitive Programming Academy merangkumi sejumlah 4 pelajaran.
Masalah Tetingkap Klasik
Cari subrentetan terpanjang tanpa aksara berulang. Ini ialah contoh kegemaran tetingkap gelongsor yang muncul dalam hampir setiap sistem penilai. 🔤
Perangkap Kaedah Kasar
Memeriksa setiap subrentetan untuk mencari pendua memerlukan kira-kira O(n^2) atau lebih teruk. Untuk rentetan panjang, kaedah itu terlalu perlahan, jadi imbasan yang lebih bijak diperlukan.
Tetingkap Aksara Unik
Simpan tetingkap yang sentiasa mengandungi aksara berbeza. Kembangkan dari kanan dan apabila ulangan muncul, kecilkan dari kiri sehingga ulangan itu hilang.
Ingat Kedudukan Terakhir
Simpan indeks terakhir bagi setiap aksara dalam kamus. Dengan ini, Anda boleh mengetahui serta-merta tempat ulangan kali terakhir dilihat semasa mengimbas.
last = {}
left = 0
best = 0Imbas Setiap Aksara
Ulang dengan kanan merentasi rentetan sambil membaca indeks dan aksara pada setiap langkah. Ini menggerakkan tetingkap ke hadapan satu kedudukan pada satu-satu masa.
for right, ch in enumerate(s):Lompatkan Penuding Kiri
Jika aksara itu pernah dilihat di dalam tetingkap semasa, gerakkan kiri ke kedudukan sejurus selepas kedudukan terakhirnya. Ini menghapuskan pendua dalam satu pergerakan.
if ch in last and last[ch] >= left:
left = last[ch] + 1Kemas Kini dan Ukur
Catat kedudukan baharu aksara ini, kemudian tetingkap dari kiri hingga kanan bebas daripada pendua. Panjangnya ialah kanan tolak kiri tambah satu.
last[ch] = right
best = max(best, right - left + 1)Mengapa Pengawal Itu Penting
Pemeriksaan last[ch] >= left amat penting. Tanpanya, kedudukan lama di luar tetingkap akan tersilap mengheret kiri ke belakang.
Masa Linear, Ruang Linear
Setiap aksara dilawati sekali dan kiri hanya bergerak ke hadapan, jadi imbasan ialah O(n). Kamus menggunakan ruang untuk menyimpan aksara yang berbeza.
Kes Tepi yang Perlu Diliputi
Rentetan kosong menghasilkan sifar, manakala rentetan dengan satu huruf berulang menghasilkan satu. Sahkan kedua-duanya sebelum menghantar jawapan untuk mengelakkan WA yang mengejutkan.
Corak yang Boleh Digunakan Semula
Peta aksara yang kali terakhir dilihat bersama penuding kiri yang melompat boleh diperluas kepada banyak masalah keberbezaan, seperti tetingkap dengan paling banyak satu ulangan.
Semakan Pantas
Anda menjejaki indeks terakhir setiap aksara semasa mengimbas subrentetan unik yang terpanjang.
Ringkasan
Gelongsorkan tetingkap aksara unik, simpan setiap kedudukan terakhir, dan lompatkan kiri melepasi ulangan. Ini menyelesaikan masalah klasik tersebut dalam O(n). ✅
Pelajari Python 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
- 30
- Pelajaran
- 120
Soalan Lazim
Adakah pelajaran “Subrentetan Terpanjang Tanpa Ulangan” percuma?
Ya — teks penuh “Subrentetan Terpanjang Tanpa Ulangan” 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 Competitive Programming Academy, tingkat taraf kepada CoddyKit PRO. Kursus Competitive Programming Academy merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Subrentetan Terpanjang Tanpa Ulangan”?
Jejaki kedudukan terakhir dalam tetingkap. Anda berlatih Competitive Programming Academy 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 Competitive Programming Academy?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Competitive Programming Academy 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 3 daripada 4.
Berapa lamakah pelajaran “Subrentetan Terpanjang Tanpa Ulangan” 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 Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy 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