Mampatan Rentetan III

3163. Mampatan Rentetan III

Kesukaran: Sederhana

Topik: Rentetan

Memandangkan perkataan rentetan, mampatkannya menggunakan algoritma berikut:

• Mulakan dengan comp rentetan kosong. Walaupun perkataan tidak kosong, gunakan operasi berikut:
  • Alih keluar awalan panjang maksimum perkataan yang diperbuat daripada aksara tunggal c berulang paling banyak 9 kali.
  • Tambahkan panjang awalan diikuti oleh c ke comp.

Kembalikan rentetan komp.

Contoh 1:

• Input: perkataan = "abcde"
• Output: "1a1b1c1d1e"
• Penjelasan: Pada mulanya, comp = "". Gunakan operasi 5 kali, pilih "a", "b", "c", "d", dan "e" sebagai awalan dalam setiap operasi.
  • Untuk setiap awalan, tambahkan "1" diikuti dengan aksara untuk dikomp.

Contoh 2:

• Input: perkataan = "aaaaaaaaaaaaaaaabb"
• Output: "9a5a2b"
• Penjelasan: Pada mulanya, comp = "". Gunakan operasi 3 kali, pilih "aaaaaaaa", "aaaaa", dan "bb" sebagai awalan dalam setiap operasi.
  • Untuk awalan "aaaaaaaaa", tambahkan "9" diikuti dengan "a" kepada comp.
  • Untuk awalan "aaaaa", tambahkan "5" diikuti dengan "a" kepada comp.
  • Untuk awalan "bb", tambahkan "2" diikuti dengan "b" kepada comp.

Kekangan:

• 1 <= word.length <= 2 * 10⁵
• perkataan hanya terdiri daripada huruf kecil Inggeris.

Petunjuk:

1. Setiap kali, hanya potong aksara yang sama dalam awalan sehingga maksimum 9 kali. Selalunya lebih baik untuk memotong awalan yang lebih besar.

Penyelesaian:

Kita boleh menggunakan pendekatan tamak untuk memampatkan rentetan dengan mengambil awalan terpanjang yang mungkin bagi aksara berulang (sehingga 9 kejadian pada satu masa) dan kemudian menambahkan panjang awalan bersama-sama dengan aksara pada hasil.

Berikut ialah penyelesaian langkah demi langkah:

1. Memulakan Pembolehubah:

   • comp (rentetan termampat) bermula sebagai rentetan kosong.
   • Gunakan penunjuk atau indeks i untuk menjejaki kedudukan dalam perkataan.

2. Gelung melalui perkataan:

   • Sementara masih terdapat aksara dalam perkataan, cari awalan terpanjang bagi aksara berulang yang tidak melebihi 9 aksara.
   • Kira berapa kali aksara semasa berulang berturut-turut, sehingga maksimum 9.

3. Tambahkan pada Rentetan Mampat:

   • Tambahkan kiraan diikuti dengan watak untuk dikomp.
   • Alihkan penunjuk i ke hadapan mengikut bilangan aksara yang diproses.

4. Keputusan Pulangan:

   • Selepas memproses keseluruhan rentetan, kembalikan komp rentetan termampat.

Mari laksanakan penyelesaian ini dalam PHP: 3163. Mampatan Rentetan III

  
  
  Penjelasan:




Gelung Mengira: Kami menggunakan gelung sementara di dalam gelung utama untuk mengira aksara berturut-turut (sehingga 9) bagi setiap aksara unik dalam perkataan.

Melampirkan Keputusan: Selepas mengira setiap jujukan, kami menambahkan kiraan dan aksara terus ke kompaun.

Kemas Kini Penunjuk: Penunjuk gelung utama i bergerak ke hadapan mengikut bilangan aksara yang dikira, dengan berkesan mengurangkan saiz rentetan yang tinggal dalam setiap lelaran.



  
  
  Analisis Kerumitan




Kerumitan Masa: O(n), dengan n ialah panjang perkataan. Setiap watak diproses sekali.

Kerumitan Angkasa: O(n) untuk hasil termampat yang disimpan dalam komp.


Penyelesaian ini cekap dan mengendalikan kes tepi, seperti urutan yang lebih pendek daripada 9 aksara atau satu kejadian bagi setiap aksara.

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 Mampatan Rentetan III. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!