Chroniques de codage dactylographié : compression de chaînes

Énoncé du problème :

Étant donné un tableau de caractères, compressez-le en utilisant l'algorithme suivant :

• Commencez par une chaîne vide s.
• Pour chaque groupe de caractères répétitifs consécutifs dans les caractères :
  • Si la longueur du groupe est 1, ajoutez le caractère à s.
  • Sinon, ajoutez le caractère suivi de la longueur du groupe.

La chaîne compressée s ne doit pas être renvoyée séparément, mais plutôt être stockée dans le tableau de caractères d'entrée chars. Notez que les longueurs de groupe de 10 ou plus seront divisées en plusieurs caractères en caractères.

Une fois que vous avez terminé de modifier le tableau d'entrée, renvoyez la nouvelle longueur du tableau.

Vous devez écrire un algorithme qui utilise uniquement un espace supplémentaire constant.

Exemple 1 :

• Entrée : caractères = ["a","a","b","b","c","c","c"]
• Sortie : renvoie 6, et les 6 premiers caractères du tableau d'entrée doivent être : ["a","2","b","2","c","3"]
• Explication : Les groupes sont "aa", "bb" et "ccc". Ceci se compresse en "a2b2c3".

Exemple 2 :

• Entrée : caractères = ["a"]
• Sortie : renvoie 1 et le premier caractère du tableau d'entrée doit être : ["a"]
• Explication : Le seul groupe est "a", qui reste non compressé puisqu'il s'agit d'un seul caractère.

Exemple 3 :

• Entrée : chars = ["a","b","b","b","b","b","b","b","b","b","b ","b","b"]
• Sortie : renvoie 4, et les 4 premiers caractères du tableau d'entrée doivent être : ["a","b","1","2"]
• Explication : Les groupes sont "a" et "bbbbbbbbbbbb". Ceci se compresse en "ab12".

Contraintes :

• 1 <= chars.length <= 2000
• chars[i] est une lettre anglaise minuscule, une lettre anglaise majuscule, un chiffre ou un symbole.

Processus de réflexion initial :

Pour résoudre ce problème, nous devons parcourir le tableau tout en gardant une trace du caractère actuel et de son nombre. Lorsque nous rencontrons un nouveau caractère, nous ajoutons le caractère actuel et son nombre (s'il est supérieur à 1) au tableau. Nous devons nous assurer que nous le faisons en place pour répondre aux exigences de complexité spatiale.

Solution de base (force brute) :

La solution par force brute consiste à créer un nouveau tableau pour stocker la version compressée du tableau d'entrée. Ce n'est pas efficace en termes d'espace mais nous aide à comprendre les étapes à suivre.

Code:

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;
}

Analyse de la complexité temporelle :

• Complexité temporelle : O(n), où n est la longueur du tableau. Nous parcourons le tableau une fois pour compter les caractères et une fois pour écrire le résultat.
• Complexité spatiale : O(n), car nous utilisons de l'espace supplémentaire pour le tableau compressé.

Limites:

La solution par force brute n'est pas économe en espace et ne répond pas à la contrainte d'utiliser uniquement un espace supplémentaire constant.

Solution optimisée :

La solution optimisée consiste à modifier le tableau d'entrée en place pour stocker la version compressée. Nous utilisons deux pointeurs : un pour lire le tableau d'entrée et un pour écrire la sortie compressée.

Code:

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>
  
  
  Analyse de la complexité temporelle :
</h3>

<ul>
<li>
<strong>Complexité temporelle :</strong> O(n), où n est la longueur du tableau. Nous parcourons le tableau une fois pour compter les caractères et une fois pour écrire le résultat.</li>
<li>
<strong>Complexité spatiale :</strong> O(1), car nous n'utilisons qu'une quantité constante d'espace supplémentaire pour les variables.</li>
</ul>

<h3>
  
  
  Améliorations par rapport à la solution de base :
</h3>

<ul>
<li>La solution optimisée réduit la complexité spatiale à O(1) en modifiant le tableau d'entrée en place.</li>
</ul>

<h2>
  
  
  Cas extrêmes et tests :
</h2>

<h3>
  
  
  Cas extrêmes :
</h3>

<ol>
<li>Le tableau ne contient qu'un seul caractère.</li>
<li>Le tableau ne contient aucun caractère répétitif consécutif.</li>
<li>Le tableau contient un grand nombre de caractères répétitifs consécutifs.</li>
</ol>

<h3>
  
  
  Cas de tests :
</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"]

Stratégies générales de résolution de problèmes :

1. Comprendre le problème : Lisez attentivement l'énoncé du problème pour comprendre les exigences et les contraintes.
2. Identifier les opérations clés : Déterminez les opérations clés nécessaires, telles que compter les caractères consécutifs et modifier le tableau en place.
3. Optimiser pour l'efficacité : Utilisez des algorithmes et des structures de données efficaces pour minimiser la complexité temporelle et spatiale.
4. Testez minutieusement : Testez la solution avec divers cas, y compris les cas extrêmes, pour garantir son exactitude.

Identifier des problèmes similaires :

1. Manipulation de chaînes :

   • Problèmes pour lesquels vous devez modifier des chaînes en fonction de conditions spécifiques.
   • Exemple : Supprimer les doublons d'une chaîne.

2. Algorithmes sur place :

   • Problèmes où les opérations doivent être effectuées sur place avec un espace supplémentaire limité.
   • Exemple : Suppression d'éléments d'un tableau sans espace supplémentaire.

Conclusion:

• Le problème de la compression d'un tableau de caractères peut être résolu efficacement en utilisant à la fois une approche par force brute et une approche optimisée sur place.
• Comprendre le problème et le décomposer en parties gérables est crucial.
• L'utilisation d'algorithmes efficaces garantit que la solution est optimale pour les entrées importantes.
• Les tests avec différents cas extrêmes garantissent la robustesse.
• Reconnaître les schémas des problèmes peut aider à appliquer des solutions similaires à d'autres défis.

En pratiquant de tels problèmes et stratégies, vous pouvez améliorer vos compétences en résolution de problèmes et être mieux préparé à relever divers défis de codage.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!