Énoncé du problème :

Étant donné un tableau de caractères, compressez-le à l'aide de 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.

Les chaînes compressées ne doivent pas être renvoyées séparément, mais plutôt stockées 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 dans chars.

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 : caractères = ["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[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 implique la création d'un nouveau tableau pour stocker la version compressée du tableau d'entrée. Cela n'est pas efficace en termes d'espace, mais nous aide à comprendre les étapes impliquées.

Code:

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

    while (i  1) {
            compressed.push(...count.toString().split(''));
        }
    }

    for (let j = 0; j 




  
  
  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  1) {
            let countStr = count.toString();
            for (let j = 0; j 




  
  
  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é de l'espace : O(1), car nous n'utilisons qu'une quantité constante d'espace supplémentaire pour les variables.

Améliorations par rapport à la solution de base :

• La solution optimisée réduit la complexité de l'espace à O(1) en modifiant le tableau d'entrée en place.

Cas extrêmes et tests :

Cas extrêmes :

1. Le tableau ne contient qu'un seul caractère.
2. Le tableau ne contient aucun caractère répétitif consécutif.
3. Le tableau contient un grand nombre de caractères répétitifs consécutifs.

Cas de tests :

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 de manière approfondie : 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 : Suppression des 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 intrants importants.
• Les tests avec différents cas extrêmes garantissent la robustesse.
• Reconnaître les modèles de 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.