Taip Pengekodan Tawarikh: Mampatan Rentetan

Pernyataan Masalah:

Memandangkan tatasusunan aksara aksara, mampatkannya menggunakan algoritma berikut:

• Mulakan dengan rentetan kosong s.
• Untuk setiap kumpulan aksara berulang berturut-turut dalam aksara:
  • Jika panjang kumpulan ialah 1, tambahkan aksara pada s.
  • Jika tidak, tambahkan watak diikuti dengan panjang kumpulan.

Rentetan termampat s tidak seharusnya dikembalikan secara berasingan, sebaliknya, disimpan dalam aksara tatasusunan aksara input. Ambil perhatian bahawa panjang kumpulan yang 10 atau lebih lama akan dibahagikan kepada berbilang aksara dalam aksara.

Selepas anda selesai mengubah suai tatasusunan input, kembalikan panjang tatasusunan baharu.

Anda mesti menulis algoritma yang hanya menggunakan ruang tambahan yang berterusan.

Contoh 1:

• Input: aksara = ["a","a","b","b","c","c","c"]
• Output: Kembali 6, dan 6 aksara pertama tatasusunan input hendaklah: ["a","2","b","2","c","3"]
• Penjelasan: Kumpulan tersebut ialah "aa", "bb", dan "ccc". Ini memampatkan kepada "a2b2c3".

Contoh 2:

• Input: aksara = ["a"]
• Output: Kembali 1, dan aksara pertama tatasusunan input hendaklah: ["a"]
• Penjelasan: Satu-satunya kumpulan ialah "a", yang kekal tidak dimampatkan kerana ia adalah satu aksara.

Contoh 3:

• Input: aksara = ["a","b","b","b","b","b","b","b","b","b","b ","b","b"]
• Output: Kembali 4, dan 4 aksara pertama tatasusunan input hendaklah: ["a","b","1","2"]
• Penjelasan: Kumpulan tersebut ialah "a" dan "bbbbbbbbbbbb". Ini memampatkan kepada "ab12".

Kekangan:

• 1 <= chars.length <= 2000
• chars[i] ialah huruf kecil Inggeris, huruf besar Inggeris, digit atau simbol.

Proses Pemikiran Awal:

Untuk menyelesaikan masalah ini, kita perlu mengulangi tatasusunan sambil menjejaki watak semasa dan kiraannya. Apabila kami menemui watak baharu, kami menambahkan aksara semasa dan kiraannya (jika lebih daripada 1) pada tatasusunan. Kami perlu memastikan bahawa kami melakukan ini di tempat untuk memenuhi keperluan kerumitan ruang.

Penyelesaian Asas (Brute Force):

Penyelesaian brute force melibatkan mencipta tatasusunan baharu untuk menyimpan versi termampat tatasusunan input. Ini tidak cekap ruang tetapi membantu kami memahami langkah-langkah yang terlibat.

Kod:

function compressBruteForce(chars: string[]): number {
    const n = chars.length;
    let compressed: string[] = [];
    let i = 0;

    while (i < n) {
        let char = chars[i];
        let count = 0;

        while (i < n && chars[i] === char) {
            i++;
            count++;
        }

        compressed.push(char);
        if (count > 1) {
            compressed.push(...count.toString().split(''));
        }
    }

    for (let j = 0; j < compressed.length; j++) {
        chars[j] = compressed[j];
    }

    return compressed.length;
}

Analisis Kerumitan Masa:

• Kerumitan Masa: O(n), dengan n ialah panjang tatasusunan. Kami mengulangi tatasusunan sekali untuk mengira aksara dan sekali untuk menulis hasilnya.
• Kerumitan Ruang: O(n), kerana kami menggunakan ruang tambahan untuk tatasusunan termampat.

Had:

Penyelesaian brute force tidak cekap ruang dan tidak memenuhi kekangan menggunakan hanya ruang tambahan yang berterusan.

Penyelesaian Dioptimumkan:

Penyelesaian yang dioptimumkan melibatkan pengubahsuaian tatasusunan input yang sedia ada untuk menyimpan versi termampat. Kami menggunakan dua penunjuk: satu untuk membaca tatasusunan input dan satu untuk menulis output termampat.

Kod:

function compress(chars: string[]): number {
    let writeIndex = 0;
    let i = 0;

    while (i < chars.length) {
        let char = chars[i];
        let count = 0;

        // Count the number of consecutive repeating characters
        while (i < chars.length && chars[i] === char) {
            i++;
            count++;
        }

        // Write the character
        chars[writeIndex] = char;
        writeIndex++;

        // Write the count if greater than 1
        if (count > 1) {
            let countStr = count.toString();
            for (let j = 0; j < countStr.length; j++) {
                chars[writeIndex] = countStr[j];
                writeIndex++;
            }
        }
    }

    return writeIndex;
}




<h3>
  
  
  Analisis Kerumitan Masa:
</h3>

<ul>
<li>
<strong>Kerumitan Masa:</strong> O(n), dengan n ialah panjang tatasusunan. Kami mengulangi tatasusunan sekali untuk mengira aksara dan sekali untuk menulis hasilnya.</li>
<li>
<strong>Kerumitan Angkasa:</strong> O(1), kerana kami hanya menggunakan jumlah ruang tambahan yang tetap untuk pembolehubah.</li>
</ul>

<h3>
  
  
  Penambahbaikan Daripada Penyelesaian Asas:
</h3>

<ul>
<li>Penyelesaian yang dioptimumkan mengurangkan kerumitan ruang kepada O(1) dengan mengubah suai tatasusunan input di tempatnya.</li>
</ul>

<h2>
  
  
  Kes Edge dan Ujian:
</h2>

<h3>
  
  
  Kes Tepi:
</h3>

<ol>
<li> Tatasusunan mengandungi hanya satu aksara.</li>
<li> Tatasusunan tidak mengandungi aksara berulang berturut-turut.</li>
<li> Tatasusunan mengandungi sejumlah besar aksara berulang berturut-turut.</li>
</ol>

<h3>
  
  
  Kes Ujian:
</h3>



<pre class="brush:php;toolbar:false">console.log(compressBruteForce(["a","a","b","b","c","c","c"])); // 6, ["a","2","b","2","c","3"]
console.log(compressBruteForce(["a"])); // 1, ["a"]
console.log(compressBruteForce(["a","b","b","b","b","b","b","b","b","b","b","b","b"])); // 4, ["a","b","1","2"]
console.log(compressBruteForce(["a","a","a","a","a","a","a","a","a","a"])); // 3, ["a","1","0"]
console.log(compressBruteForce(["a","b","c"])); // 3, ["a","b","c"]

console.log(compress(["a","a","b","b","c","c","c"])); // 6, ["a","2","b","2","c","3"]
console.log(compress(["a"])); // 1, ["a"]
console.log(compress(["a","b","b","b","b","b","b","b","b","b","b","b","b"])); // 4, ["a","b","1","2"]
console.log(compress(["a","a","a","a","a","a","a","a","a","a"])); // 3, ["a","1","0"]
console.log(compress(["a","b","c"])); // 3, ["a","b","c"]

Strategi Penyelesaian Masalah Umum:

1. Fahami Masalah: Baca pernyataan masalah dengan teliti untuk memahami keperluan dan kekangan.
2. Kenal pasti Operasi Utama: Tentukan operasi utama yang diperlukan, seperti mengira aksara berturut-turut dan mengubah suai tatasusunan di tempatnya.
3. Optimumkan untuk Kecekapan: Gunakan algoritma dan struktur data yang cekap untuk meminimumkan kerumitan masa dan ruang.
4. Uji Dengan Teliti: Uji penyelesaian dengan pelbagai kes, termasuk kes tepi, untuk memastikan ketepatan.

Mengenalpasti Masalah Serupa:

1. Manipulasi Rentetan:

   • Masalah di mana anda perlu mengubah suai rentetan berdasarkan keadaan tertentu.
   • Contoh: Mengalih keluar pendua daripada rentetan.

2. Algoritma Di Tempat:

   • Masalah di mana operasi perlu dilakukan di tempat dengan ruang tambahan yang terhad.
   • Contoh: Mengalih keluar elemen daripada tatasusunan tanpa ruang tambahan.

Kesimpulan:

• Masalah memampatkan tatasusunan aksara boleh diselesaikan dengan cekap menggunakan kedua-dua pendekatan kekerasan dan pendekatan di tempat yang dioptimumkan.
• Memahami masalah dan membahagikannya kepada bahagian yang boleh diurus adalah penting.
• Menggunakan algoritma yang cekap memastikan penyelesaian adalah optimum untuk input yang besar.
• Pengujian dengan pelbagai kes tepi memastikan keteguhan.
• Mengenal corak dalam masalah boleh membantu menggunakan penyelesaian yang serupa untuk cabaran lain.

Dengan mempraktikkan masalah dan strategi sedemikian, anda boleh meningkatkan kemahiran menyelesaikan masalah anda dan lebih bersedia untuk pelbagai cabaran pengekodan.

Atas ialah kandungan terperinci Taip Pengekodan Tawarikh: Mampatan Rentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!