Tawarikh Pengekodan Skrip: Perkataan Songsang dalam Rentetan

Pernyataan Masalah:

Memandangkan rentetan input s, terbalikkan susunan perkataan. Perkataan ditakrifkan sebagai urutan aksara bukan ruang. Perkataan dalam s akan dipisahkan oleh sekurang-kurangnya satu ruang. Kembalikan rentetan perkataan dalam susunan terbalik yang digabungkan dengan satu ruang.

Perhatikan bahawa s mungkin mengandungi ruang hadapan atau belakang atau berbilang ruang antara dua perkataan. Rentetan yang dikembalikan seharusnya hanya mempunyai satu ruang yang memisahkan perkataan. Jangan sertakan sebarang ruang tambahan.

Contoh 1:

• Input: s = "langit biru"
• Output: "biru ialah langit"

Contoh 2:

• Input: s = " hello world "
• Keluaran: "hello dunia"
• Penjelasan: Rentetan terbalik anda tidak seharusnya mengandungi ruang hadapan atau belakang.

Contoh 3:

• Input: s = "contoh yang baik"
• Output: "contoh yang baik a"
• Penjelasan: Anda perlu mengurangkan berbilang ruang antara dua perkataan kepada satu ruang dalam rentetan terbalik.

Kekangan:

• 1 <= s.panjang <= 10^4
• s mengandungi huruf Inggeris (huruf besar dan huruf kecil), digit dan ruang ' '.
• Terdapat sekurang-kurangnya satu perkataan dalam s.

Proses Pemikiran Awal:

Untuk menyelesaikan masalah ini, kita perlu:

1. Pisah rentetan menjadi perkataan.
2. Terbalikkan susunan perkataan.
3. Sambungkan perkataan kembali bersama-sama dengan satu ruang antara setiap perkataan.

Penyelesaian Asas:

Kod:

function reverseWordsBruteForce(s: string): string {
    // Split the string by spaces and filter out empty strings
    let words = s.trim().split(/\s+/);

    // Reverse the array of words
    words.reverse();

    // Join the words with a single space
    return words.join(' ');
}

Analisis Kerumitan Masa:

• Kerumitan Masa: O(n), dengan n ialah panjang rentetan. Pemisahan, pembalikan dan penyatuan semuanya mengambil masa linear.
• Kerumitan Angkasa: O(n), dengan n ialah panjang rentetan. Kami menyimpan perkataan dalam tatasusunan dan hasil akhir dalam rentetan.

Had:

Penyelesaian ini cekap memandangkan kekangan. Walau bagaimanapun, ia menggunakan ruang tambahan untuk susunan perkataan.

Penyelesaian Dioptimumkan:

Jika jenis data rentetan boleh berubah dan kita perlu menyelesaikannya di tempat dengan ruang tambahan O(1), kita boleh menggunakan teknik dua penuding untuk membalikkan perkataan dalam rentetan asal.

Kod:

function reverseWordsOptimized(s: string): string {
    // Trim the string and convert it to an array of characters
    let chars = s.trim().split('');

    // Helper function to reverse a portion of the array in place
    function reverse(arr: string[], left: number, right: number) {
        while (left < right) {
            [arr[left], arr[right]] = [arr[right], arr[left]];
            left++;
            right--;
        }
    }

    // Reverse the entire array of characters
    reverse(chars, 0, chars.length - 1);

    // Reverse each word in the reversed array
    let start = 0;
    for (let end = 0; end <= chars.length; end++) {
        if (end === chars.length || chars[end] === ' ') {
            reverse(chars, start, end - 1);
            start = end + 1;
        }
    }

    // Join the characters back into a string and split by spaces to remove extra spaces
    return chars.join('').split(/\s+/).join(' ');
}

Analisis Kerumitan Masa:

• Kerumitan Masa: O(n), dengan n ialah panjang rentetan. Setiap aksara diproses beberapa kali berterusan.
• Kerumitan Angkasa: O(1), kerana kami mengubah suai tatasusunan di tempatnya dan hanya menggunakan jumlah ruang tambahan yang tetap.

Penambahbaikan Daripada Penyelesaian Asas:

• Penyelesaian yang dioptimumkan mengurangkan kerumitan ruang dengan melakukan operasi di tempat pada susunan aksara.

Kes Edge dan Ujian:

Kes Tepi:

1. Rentetan mengandungi ruang hadapan dan belakang.
2. Rentetan mengandungi berbilang ruang antara perkataan.
3. Rentetan mengandungi hanya satu perkataan.
4. Panjang rentetan adalah pada had minimum atau maksimum.

Kes Ujian:

console.log(reverseWordsBruteForce("the sky is blue")); // "blue is sky the"
console.log(reverseWordsBruteForce("  hello world  ")); // "world hello"
console.log(reverseWordsBruteForce("a good   example")); // "example good a"
console.log(reverseWordsBruteForce("singleWord")); // "singleWord"
console.log(reverseWordsBruteForce("   ")); // ""

console.log(reverseWordsOptimized("the sky is blue")); // "blue is sky the"
console.log(reverseWordsOptimized("  hello world  ")); // "world hello"
console.log(reverseWordsOptimized("a good   example")); // "example good a"
console.log(reverseWordsOptimized("singleWord")); // "singleWord"
console.log(reverseWordsOptimized("   ")); // ""

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 membelah, membalikkan dan mencantumkan perkataan.
3. Optimumkan untuk Kebolehbacaan: Gunakan logik yang jelas dan padat untuk memastikan kod mudah diikuti.
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: Membalikkan susunan aksara dalam setiap perkataan ayat.

2. Teknik Dua Mata:

   • Masalah menggunakan dua penunjuk boleh membantu mengoptimumkan penyelesaian.
   • Contoh: Mengalih keluar pendua daripada tatasusunan yang diisih.

3. Algoritma Di Tempat:

   • Masalah di mana operasi perlu dilakukan di tempat dengan ruang tambahan yang terhad.
   • Contoh: Memutar tatasusunan ke kanan dengan k langkah.

Kesimpulan:

• Masalah menterbalikkan perkataan dalam rentetan 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 logik yang jelas dan mengoptimumkan kebolehbacaan memastikan penyelesaiannya mudah diikuti.
• 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 Tawarikh Pengekodan Skrip: Perkataan Songsang dalam Rentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!