2182. Bina Rentetan Dengan Had Ulangan
Kesukaran: Sederhana
Topik: Jadual Hash, Rentetan, Tamak, Timbunan (Baris Gilir Keutamaan), Mengira
Anda diberi rentetan s dan integer repeatLimit. Bina rentetan baharu repeatLimitedString menggunakan aksara s supaya tiada huruf muncul melebihi ulanganHadkan masa berturut-turut. Anda tidak perlu menggunakan semua aksara daripada s.
Kembalikan leksikografi terbesar repeatLimitedString mungkin.
Rentetan a adalah leksikografi lebih besar daripada rentetan b jika dalam kedudukan pertama di mana a dan b berbeza, rentetan a mempunyai huruf yang muncul kemudian dalam abjad daripada huruf yang sepadan dalam b. Jika aksara min(a.length, b.length) pertama tidak berbeza, maka rentetan yang lebih panjang ialah rentetan leksikografi yang lebih besar.
Contoh 1:
Contoh 2:
Kekangan:
Petunjuk:
Penyelesaian:
Kami menggunakan pendekatan tamak untuk mengutamakan aksara leksikografik yang lebih besar sambil memastikan tiada aksara yang melebihi repeatLimit secara berturut-turut. Pendekatan ini menggunakan baris gilir keutamaan (timbunan maks) untuk memproses aksara dalam tertib menurun secara leksikografi dan memastikan tiada aksara muncul lebih daripada kali repeatLimit berturut-turut.
Mari laksanakan penyelesaian ini dalam PHP: 2182. Bina Rentetan Dengan Had Ulangan
<?php /** * @param String $s * @param Integer $repeatLimit * @return String */ function repeatLimitedString($s, $repeatLimit) { ... ... ... /** * go to ./solution.php */ } // Test Cases echo repeatLimitedString("cczazcc", 3) . "\n"; // Output: zzcccac echo repeatLimitedString("aababab", 2) . "\n"; // Output: bbabaa ?> <h3> Penjelasan: </h3> <ol> <li> <p><strong>Kiraan Kekerapan:</strong></p> <ul> <li>Lelaran melalui rentetan s untuk mengira kejadian setiap aksara.</li> <li>Simpan frekuensi dalam tatasusunan bersekutu $freq.</li> </ul> </li> <li> <p><strong>Isih dalam Susunan Menurun:</strong></p> <ul> <li>Gunakan krsort() untuk mengisih aksara mengikut susunan leksikografik dalam susunan <strong>menurun</strong>.</li> </ul> </li> <li> <p><strong>Bina Hasilnya:</strong></p> <ul> <li>Tambahkan aksara terbesar dari segi leksikografi ($char) pada rentetan hasil secara berterusan.</li> <li>Jika aksara mencapai repeatLimit, hentikan menambahkannya buat sementara waktu.</li> <li>Gunakan baris gilir sementara untuk menahan aksara yang masih mempunyai baki kiraan tetapi dilangkau buat sementara waktu.</li> </ul> </li> <li> <p><strong>Kendalikan Had Ulangan:</strong></p> <ul> <li>Jika aksara semasa telah mencapai repeatLimit, gunakan aksara leksikografi terbesar seterusnya daripada baris gilir.</li> <li>Masukkan semula aksara sebelumnya ke dalam peta kekerapan untuk meneruskan pemprosesannya kemudian.</li> </ul> </li> <li> <p><strong>Kes Tepi:</strong></p> <ul> <li>Watak mungkin tidak menghabiskan kiraan penuh mereka pada mulanya.</li> <li>Selepas mengendalikan aksara sandaran daripada baris gilir, aksara semasa meneruskan pemprosesan.</li> </ul> </li> </ol> <h3> <strong>Cara Ia Berfungsi</strong> </h3> <ol> <li> <strong>Kiraan Watak</strong>: $freq menjejaki kejadian untuk semua aksara.</li> <li> <strong>Timbunan Maks</strong>: SplPriorityQueue digunakan sebagai timbunan maks, dengan aksara diutamakan oleh nilai ASCIInya (urutan menurun).</li> <li> <strong>Pembinaan Rentetan</strong>: <ul> <li>Jika aksara semasa telah mencapai repeatLimitnya, ambil aksara terbesar seterusnya.</li> <li>Gunakan aksara terbesar seterusnya sekali dan masukkan semula aksara sebelumnya ke dalam timbunan untuk kegunaan masa hadapan.</li> </ul> </li> <li> <strong>Keputusan Akhir</strong>: Rentetan yang terhasil ialah rentetan leksikografi terbesar yang memenuhi kekangan repeatLimit.</li> </ol> <h3> <strong>Contoh Panduan</strong> </h3> <p><strong>Input:</strong><br><br> s = "cczazcc", repeatLimit = 3</p> <p><strong>Langkah:</strong></p> <ol> <li><p>Kiraan kekerapan:<br><br> ['a' => 1, 'c' => 4, 'z' => 2]</p></li> <li><p>Isih mengikut tertib menurun:<br><br> ['z' => 2, 'c' => 4, 'a' => 1]</p></li> <li> <p>Tambah aksara sambil menghormati repeatLimit:</p> <ul> <li>Tambah 'z' → "zz" (kiraan z = 0)</li> <li>Tambah 'c' 3 kali → "zzccc" (c count = 1)</li> <li>Tambah 'a' → "zzccca" (kiraan = 0)</li> <li>Tambahkan baki 'c' → "zzcccac"</li> </ul> </li> </ol> <p><strong>Output:</strong> "zzcccac"</p> <h3> <strong>Kerumitan Masa</strong> </h3> <ul> <li> <strong>Pengiraan Kekerapan Watak</strong>: <em><strong>O(n)</strong></em>, dengan <em><strong>n</strong></em> ialah panjang rentetan.</li> <li> <strong>Kendalian Timbunan</strong>: <em><strong>O(26 log 26)</strong></em>, kerana timbunan boleh memuatkan sehingga 26 aksara.</li> <li> <strong>Kerumitan Keseluruhan</strong>: <em><strong>O(n 26 log 26) ≈ O(n)</strong></em>.</li> </ul> <h3> <strong>Kerumitan Angkasa</strong> </h3> <ul> <li> <em><strong>O(26)</strong></em> untuk tatasusunan frekuensi.</li> <li> <em><strong>O(26)</strong></em> untuk timbunan.</li> </ul> <h3> <strong>Kes Ujian</strong> </h3> <pre class="brush:php;toolbar:false"><?php /** * @param String $s * @param Integer $repeatLimit * @return String */ function repeatLimitedString($s, $repeatLimit) { ... ... ... /** * go to ./solution.php */ } // Test Cases echo repeatLimitedString("cczazcc", 3) . "\n"; // Output: zzcccac echo repeatLimitedString("aababab", 2) . "\n"; // Output: bbabaa ?>
Pelaksanaan ini berfungsi dengan cekap dalam kekangan.
Pautan Kenalan
Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!
Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:
Atas ialah kandungan terperinci Bina Rentetan Dengan Had Ulangan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!