Início / coding / Perguntas / 77812206
Accepted
Sougata Mukherjee
Asked: 2024-01-14 00:30:15 +0800 CST

preciso de algumas soluções fáceis com código curto na compactação de string em js

  • 772

Aqui eu criei um programa para compactação de strings, então para input chars = ["a","a","b","b","c","c","c"] estamos obtendo uma saída como 6 caracteres ["a","2","b","2","c","3"]. Então criei um programa usando a abordagem de array, que também é muito demorada e complexa. Existe alguma solução usando a abordagem de dois ponteiros ou recursão para resolver esse programa com muito pouco código e eficiência? Você pode fornecer isso com um código muito curto? O código é fornecido abaixo.

var compress = function(chars) {
 if (!chars.length) {
    return 0;
  }
   let j = 0;                 
  let cur = chars[0];        
  let counter = 0;         
   for (let i = 0; i <= chars.length; i++) {
  
    if (chars[i] === cur) {
      counter++;              
    } else {
      // Otherwise, add the current character and count to the compressed array
      chars[j] = cur;        
      if (counter > 1) {
        const s = counter.toString();
        for (let k = 0; k < s.length; k++) {
          chars[++j] = s[k];  
        }
      }
      j++;                  
      cur = chars[i];      
      counter = 1;           
    }
   }
   return j
};
console.log(compress ('aaaabbc'))//a4b2c
javascript

5 respostas

  1. Best Answer

    Aqui está a solução usando dois ponteiros. O conceito chave aqui é: NÃO PASSE DUAS VEZES PARA CADA ELEMENTO DA ENTRADA .

    Complexidade:

    • tempo: O (n)
    • espaço: O(n)
    const compress = (str) => {
  const result = [];
  for (let i = 0; i < str.length; ) {
    let j = i;
    while (str[j] == str[i]) {
      j++;
    }
    result.push(`${str[i]}${j - i == 1 ? '' : j - i}`);
    i = j;
  }
  return result.join('');
};
    • 1

  2. Você pode usar replacena entrada e usar uma expressão regular para corresponder a cada ocorrência de uma sequência repetida (de tamanho 2 ou mais). Em seguida, use o argumento de retorno de chamada para substituir pela versão codificada:

    const compress = chars => chars.replace(/(.)\1+/g, ({length},ch) => ch+length);

console.log(compress ('aaaabbc'))//a4b2c

    Observe que se sua entrada tiver dígitos, a saída poderá ser ambígua. Por exemplo, se a saída for "a20", você poderá se perguntar se a entrada foi "aaaaaaaaaaaaaaaaaaaa" ou "aa0".

    • 1

  3. Um liner: você pode usar Array::reduce():

    const result = ["a","a","b","b","c","c","c"]
  .reduce((r, c) => (r[r.length - 2] === c ? r[r.length - 1]++ : r.push(c, 1), r), []);

console.log(JSON.stringify(result));

    • 1

  4. Você poderia iterar os caracteres e pegar duas variáveis ​​para o caractere real e contar. A contagem começa com uma string vazia e finalmente é incrementada para obter um valor de contagem, se o valor for verdadeiro. Caso contrário, apenas o caractere será adicionado à sequência de resultados.

    const
    compress = chars => {
        if (!chars.length) return '';
        let result = '',
            char = '',
            count = '';

        for (const c of chars) {
            if (c === char) {
                count++;
                continue;
            }
            result += char + (count && ++count);
            char = c;
            count = '';
        }
        return result + char + (count && ++count);
    };

console.log(compress('aaaabbc')); //a4b2c

    • 1

  5. Abordagem de dois ponteiros ligeiramente modificada para evitar incrementos de contador. Eu rotulei as variáveis ​​para que você possa seguir o código facilmente.

    var compress = function(chars) {
    let result = '';
    let currChar = 0;
    while(currChar < chars?.length) {
        let nextChar = currChar+1;
        while ((nextChar < chars.length) && (chars[currChar] === chars[nextChar]))
            nextChar++;
        let repeatFactor = nextChar-currChar;
        result += chars[currChar] + (repeatFactor > 1 ? (''+repeatFactor).trim() : '');
        currChar=nextChar;
    }
    return result;
}

    Espero que você ache isso útil.

    • 0

relate perguntas