主页 / coding / 问题 / 77812206
Accepted
Sougata Mukherjee
Asked: 2024-01-14 00:30:15 +0800 CST

需要一些简单的解决方案，在 js 中使用短代码进行字符串压缩

  • 772

在这里，我创建了一个用于字符串压缩的程序，因此对于输入 chars = ["a","a","b","b","c","c","c"] 我们得到像 6 这样的输出字符 [“a”、“2”、“b”、“2”、“c”、“3”]。所以我使用数组方法创建了一个程序，该程序也非常冗长且复杂。有没有使用两指针或递归方法以很少的代码和效率来解决该程序的解决方案？您能提供非常短的代码吗？代码如下。

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 个回答

  1. Best Answer

    这是使用两个指针的解决方案。这里的关键概念是：不要为输入中的每个元素传递两次。

    复杂：

    • 时间：O(n)
    • 空间：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. replace您可以在输入上使用，并使用正则表达式来匹配重复序列（大小为 2 或更大）的每次出现。然后使用回调参数将其替换为编码版本：

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

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

    请注意，如果您的输入包含数字，则输出可能不明确。例如，如果输出是“a20”，您可能想知道输入是“aaaaaaaaaaaaaaaaaaaa”还是“aa0”。

    • 1

  3. 一个衬垫：您可以使用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. 您可以迭代字符并为实际字符和计数采用两个变量。计数以空字符串开始，如果该值是真值，则最终递增以获取计数值。如果不是，则仅将该字符添加到结果字符串中。

    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. 稍微修改两指针方法以避免计数器增量。我已经标记了变量，以便您可以轻松地遵循代码。

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

    希望您会发现这很有用。

    • 0

相关问题