Bina Rentetan Dengan Had Ulangan

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:

• Input: s = "cczazcc", repeatLimit = 3
• Output: "zzcccac"
• Penjelasan: Kami menggunakan semua aksara daripada s untuk membina repeatLimitedString "zzcccac".
  • Huruf 'a' muncul paling banyak 1 kali berturut-turut.
  • Huruf 'c' muncul paling banyak 3 kali berturut-turut.
  • Huruf 'z' muncul paling banyak 2 kali berturut-turut.
  • Oleh itu, tiada huruf yang muncul lebih daripada repeatLimit kali berturut-turut dan rentetan ialah repeatLimitedString yang sah.
  • Rentetan ialah repeatLimitedString terbesar dari segi leksikografi, jadi kami mengembalikan "zzcccac".
  • Perhatikan bahawa rentetan "zzcccca" secara leksikografi lebih besar tetapi huruf 'c' muncul lebih daripada 3 kali berturut-turut, jadi ia bukan repeatLimitedString yang sah.

Contoh 2:

• Input: s = "aababab", repeatLimit = 2
• Output: "bbabaa"
• Penjelasan: Kami hanya menggunakan beberapa aksara daripada s untuk membina "bbabaa" repeatLimitedString.
  • Huruf 'a' muncul paling banyak 2 kali berturut-turut.
  • Huruf 'b' muncul paling banyak 2 kali berturut-turut.
  • Oleh itu, tiada huruf yang muncul lebih daripada repeatLimit kali berturut-turut dan rentetan ialah repeatLimitedString yang sah.
  • Rentetan ialah repeatLimitedString terbesar dari segi leksikografi yang mungkin jadi kami mengembalikan "bbabaa".
  • Perhatikan bahawa rentetan "bbabaaa" secara leksikografi lebih besar tetapi huruf 'a' muncul lebih daripada 2 kali berturut-turut, jadi ia bukan repeatLimitedString yang sah.

Kekangan:

• 1 <= repeatLimit <= s.panjang <= 10⁵
• s terdiri daripada huruf kecil Inggeris.

Petunjuk:

1. Mula membina rentetan dalam susunan aksara menurun.
2. Apabila repeatLimit dicapai, pilih aksara terbesar seterusnya.

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.

Penjelasan Penyelesaian

1. Kira Aksara: Kira kekerapan setiap aksara dalam rentetan s menggunakan tatasusunan.
2. Timbunan Maks: Gunakan timbunan maksimum (baris gilir keutamaan) untuk mengisih dan mengekstrak aksara dalam susunan leksikografi menurun.
3. Pembinaan Tamak:
   • Tambah aksara terbesar yang tersedia sehingga masa repeatLimit.
   • Jika repeatLimit untuk aksara semasa dicapai, tukar kepada aksara terbesar seterusnya, masukkan sekali, dan kemudian masukkan semula aksara pertama ke dalam timbunan untuk kegunaan selanjutnya.
4. Pengendalian Tepi: Urus dengan betul apabila watak tidak boleh digunakan lagi.

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
?>

Kes Tepi

1. s mengandungi hanya satu aksara unik (cth., "aaaaaaa", repeatLimit = 2): Output hanya akan merangkumi seberapa banyak aksara yang dibenarkan secara berturut-turut.
2. repeatLimit = 1: Output berselang seli antara aksara yang tersedia.
3. Semua aksara dalam s adalah unik: Output diisih mengikut tertib menurun.

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:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Bina Rentetan Dengan Had Ulangan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!