Declaração do problema:

Dada uma matriz de caracteres, compacte-a usando o seguinte algoritmo:

• Comece com uma string vazia s.
• Para cada grupo de caracteres repetidos consecutivos em chars:
  • Se o comprimento do grupo for 1, anexe o caractere a s.
  • Caso contrário, acrescente o caractere seguido do comprimento do grupo.

As strings compactadas não devem ser retornadas separadamente, mas sim armazenadas na matriz de caracteres de entrada chars. Observe que comprimentos de grupo maiores que 10 serão divididos em vários caracteres em chars.

Depois de modificar a matriz de entrada, retorne o novo comprimento da matriz.

Você deve escrever um algoritmo que use apenas espaço extra constante.

Exemplo 1:

• Entrada: caracteres = ["a","a","b","b","c","c","c"]
• Saída: Retorna 6, e os primeiros 6 caracteres da matriz de entrada devem ser: ["a","2","b","2","c","3"]
• Explicação: Os grupos são "aa", "bb" e "ccc". Isso é compactado para "a2b2c3".

Exemplo 2:

• Entrada: caracteres = ["a"]
• Saída: Retorna 1, e o primeiro caractere da matriz de entrada deve ser: ["a"]
• Explicação: O único grupo é "a", que permanece descompactado por ser um único caractere.

Exemplo 3:

• Entrada: caracteres = ["a","b","b","b","b","b","b","b","b","b","b ","b","b"]
• Saída: Retorna 4, e os primeiros 4 caracteres da matriz de entrada devem ser: ["a","b","1","2"]
• Explicação: Os grupos são "a" e "bbbbbbbbbbbb". Isso é compactado para "ab12".

Restrições:

• 1
• chars[i] é uma letra minúscula em inglês, uma letra maiúscula, um dígito ou um símbolo em inglês.

Processo de pensamento inicial:

Para resolver este problema, precisamos percorrer o array enquanto controlamos o caractere atual e sua contagem. Quando encontramos um novo caractere, acrescentamos o caractere atual e sua contagem (se for maior que 1) ao array. Precisamos garantir que faremos isso para atender aos requisitos de complexidade do espaço.

Solução Básica (Força Bruta):

A solução de força bruta envolve a criação de um novo array para armazenar a versão compactada do array de entrada. Isso não economiza espaço, mas nos ajuda a entender as etapas envolvidas.

Código:

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 




  
  
  Análise de complexidade de tempo:

• Complexidade de tempo: O(n), onde n é o comprimento da matriz. Iteramos pela matriz uma vez para contar caracteres e uma vez para escrever o resultado.
• Complexidade do espaço: O(n), pois usamos espaço extra para o array compactado.

Limitações:

A solução de força bruta não economiza espaço e não atende à restrição de usar apenas espaço extra constante.

Solução otimizada:

A solução otimizada envolve a modificação da matriz de entrada para armazenar a versão compactada. Usamos dois ponteiros: um para ler o array de entrada e outro para escrever a saída compactada.

Código:

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

    while (i  1) {
            let countStr = count.toString();
            for (let j = 0; j 




  
  
  Análise de complexidade de tempo:

• Complexidade de tempo: O(n), onde n é o comprimento da matriz. Iteramos pela matriz uma vez para contar caracteres e uma vez para escrever o resultado.
• Complexidade do espaço: O(1), pois usamos apenas uma quantidade constante de espaço extra para variáveis.

Melhorias em relação à solução básica:

• A solução otimizada reduz a complexidade do espaço para O(1) modificando a matriz de entrada no local.

Casos extremos e testes:

Casos extremos:

1. A matriz contém apenas um caractere.
2. A matriz não contém caracteres repetidos consecutivos.
3. A matriz contém um grande número de caracteres repetidos consecutivos.

Casos de teste:

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"]

Estratégias gerais de resolução de problemas:

1. Entenda o problema: Leia atentamente a declaração do problema para entender os requisitos e restrições.
2. Identificar operações principais: Determine as operações principais necessárias, como contar caracteres consecutivos e modificar a matriz no local.
3. Otimize para eficiência: Use algoritmos e estruturas de dados eficientes para minimizar a complexidade de tempo e espaço.
4. Teste Completamente: Teste a solução com vários casos, incluindo casos extremos, para garantir a correção.

Identificando problemas semelhantes:

1. Manipulação de strings:

   • Problemas em que você precisa modificar strings com base em condições específicas.
   • Exemplo: Removendo duplicatas de uma string.

2. Algoritmos no local:

   • Problemas em que as operações precisam ser realizadas em local com espaço extra limitado.
   • Exemplo: Removendo elementos de um array sem espaço extra.

Conclusão:

• O problema de compactação de uma matriz de caracteres pode ser resolvido com eficiência usando uma abordagem de força bruta e uma abordagem otimizada no local.
• Compreender o problema e dividi-lo em partes gerenciáveis ​​é crucial.
• O uso de algoritmos eficientes garante que a solução seja ideal para grandes entradas.
• Testes com vários casos extremos garantem robustez.
• Reconhecer padrões em problemas pode ajudar a aplicar soluções semelhantes a outros desafios.

Ao praticar esses problemas e estratégias, você pode melhorar suas habilidades de resolução de problemas e estar mais bem preparado para vários desafios de codificação.