对以下字符串进行压缩编码

更多描述这是一道大厂常考的代码题

Input: ‘aaaabbbccd’
Output: ‘a4b3c2d1’，代表 a 连续出现四次，b连续出现三次，c连续出现两次，d连续出现一次

有以下测试用例

//=> a4b3c2
encode("aaaabbbcc");
 
//=> a4b3a4
encode("aaaabbbaaaa");
 
//=> a2b2c2
encode("aabbcc");

如果代码编写正确，则可继续深入：

如果只出现一次，不编码数字，如 aaab -> a3b
如果只出现两次，不进行编码，如 aabbb -> aab3
如果进行解码数字冲突如何解决

Issue 欢迎在 Gtihub Issue 中回答此问题: Issue 419

Author 回答者: shfshanyue

编写函数 encode 实现该功能

代码见【Q412】对以下字符进行压缩编码 - codepen

function encode(str) {
  const l = [];
  let i = 0;
  for (const s of str) {
    const len = l.length;
    const lastChar = len > 0 ? l[len - 1][0] : undefined;
    if (lastChar === s) {
      l[len - 1][1]++;
    } else {
      l.push([s, 1]);
    }
  }
  return l.map((x) => x.join("")).join("");
}
 
// 另外一种思路的解法
function encode(str) {
  const l = [];
  let i = -1;
  let lastChar;
  for (const char of str) {
    if (char !== lastChar) {
      lastChar = char;
      i++;
      l[i] = [char, 1];
    } else {
      l[i][1]++;
    }
  }
  return l.flat().join("");
}

测试通过

> encode('aaab')
< "a3b1"

但是面试官往往会继续深入

如果只出现一次，不编码数字，如 aaab -> a3b
如果只出现两次，不进行编码，如 aabbb -> aab3
如果进行解码，碰到数字如何处理？

以下是除数字外的进一步编码

function encode(str) {
  const l = [];
  let i = -1;
  let lastChar;
  for (const char of str) {
    if (char !== lastChar) {
      lastChar = char;
      i++;
      l[i] = [char, 1];
    } else {
      l[i][1]++;
    }
  }
  return l
    .map(([x, y]) => {
      if (y === 1) {
        return x;
      }
      if (y === 2) {
        return x + x;
      }
      return x + y;
    })
    .join("");
}

Author 回答者: LiJinWD

const encode = function(input) { let obj = {} for(const key of input) { if(obj[key]) { obj[key]++ } else { obj[key] = 1 } } return Object.entries(obj).flat().join(”) }

Author 回答者: LiJinWD

const encode = function(input, n) { let obj = {} for(const key of input) { if(obj[key]) { obj[key]++ } else { obj[key] = 1 } } return Object.entries(obj).flat().join(”) // 如果只出现一次，不编码数字 // return Object.entries(obj).flat().join(”).replace(/1/gi, ”) // 如果只出现N次，不进行编码, N是参数 /_ let objArr = Object.entries(obj); objArr.forEach(item => { if(item[1] == n) { item[1] = (new Array(n - 1)).fill(item[0]).join(”) } }) return objArr.flat().join(”) _/ }

encode(‘aaaabbbccd’, 2)

Author 回答者: haiifeng

var doEncode = (str, nums = 0) => {
  const res = str.split("").reduce((sum, cur) => {
    sum[cur] ? sum[cur]++ : (sum[cur] = 1);
    return sum;
  }, {});
  const filteredArr = Object.entries(res).filter((item) => item[1] > nums);
  //const filteredArr= Object.entries(res).map(item=>{item[1]=item[1]>nums?item[1]:'';return item});
  return filteredArr.flat().join("");
};
doEncode("aaaabbbccd"); //"a4b3c2d1"
doEncode("aaaabbbccd", 1); //"a4b3c2"
doEncode("aaaabbbccd", 2); //"a4b3"

Author 回答者: shfshanyue

@haiifeng 注意标记下 js 的语法高亮

Author 回答者: haotie1990

function encodeString(string) {
  let result = "";
  let stack = [];
  if (!string || !string.length) {
    return result;
  }
  const strArray = string.split("");
  const pick = () => stack[stack.length - 1];
  const concat = () =>
    (result = result + pick() + (stack.length > 1 ? stack.length : ""));
 
  stack.push(strArray.shift());
 
  while (strArray.length) {
    const letter = strArray.shift();
    if (pick() !== letter) {
      concat();
      stack.length = 0;
    }
    stack.push(letter);
  }
  if (stack.length) {
    concat();
  }
  return result;
}
 
console.log(encodeString("aaaabbbccd"));
console.log(encodeString("aaaabbbcc"));
console.log(encodeString("aaaabbbaaaa"));
console.log(encodeString("aabbcc"));

exercism 上出现了这个题目

export default class RunLengthEncoding {
  static encode(input: string): string {
    if (input === "") {
      return input;
    }
 
    const encoding: string[] = [];
 
    for (let i = 0; i < input.length; i++) {
      let charCount = 1;
 
      while (input[i] === input[i + 1]) {
        charCount++;
        i++;
      }
 
      if (charCount === 1) {
        // 出现一次不编码数字
        encoding.push(input[i]);
      } else {
        encoding.push(input[i] + charCount);
      }
    }
 
    return encoding.join("");
  }
 
  static decode(input: string): string {
    if (input === "") {
      return input;
    }
 
    const decoding: string[] = [];
 
    for (let i = 0; i < input.length; i++) {
      let charCode = input.charCodeAt(i);
      let charCount: string | number = "";
 
      while (charCode > 47 && charCode < 58) {
        // 0 ~ 9
        charCount += input[i];
        i++;
        charCode = input.charCodeAt(i);
      }
 
      if (charCount === "") {
        charCount += "1";
      }
 
      charCount = Number(charCount);
 
      while (charCount) {
        decoding.push(input[i]);
        charCount--;
      }
    }
 
    return decoding.join("");
  }
}

Author 回答者: Asarua

function encode(str, ignore) {
  const container = new Map();
  for (const s of str) {
    container.set(s, (container.get(s) ?? 0) + 1);
  }
  return Array.from(container.entries()).reduce((ret, [char, num]) => {
    if (num === ignore) {
      ret += char.repeat(num);
    } else {
      ret += char + num;
    }
    return ret;
  }, "");
}

Author 回答者: hwb2017

最基础功能的实现:

const encode = (str) => {
  const encodedArray = Array.from(str).reduce((a, b) => {
    if (a.length === 0) {
      a.push(b, 1);
      return a;
    }
    let lastChar = a[a.length - 2];
    if (lastChar === b) {
      a[a.length - 1] += 1;
    } else {
      a.push(b, 1);
    }
    return a;
  }, []);
  return encodedArray.join("");
};

Author 回答者: 3N26

function solution(s, limit) {
  const n = s.length;
  let res = "";
  for (let i = 0, cnt = 0; i < n; i += cnt) {
    cnt = 1;
    while (s[i] === s[i + cnt]) cnt++;
    res += cnt > limit ? s[i] + cnt : s[i].repeat(cnt);
  }
  return res;
}

Author 回答者: LiJinWD

}

const encode1 = word => { return word.replace(/1/gi, ”) }

const encode2 = word => { let one = word.substring(0, 1) let newWord = ” for(item of word) { newWord += item == 2 ? one : item one = item } return newWord }

Author 回答者: yuli-lovely

function encode(str) {
  let prefix = ""; //初识节点
  let num = 0; //计数器
  let result = ""; //结果
  for (let i = 0; i < str.length; i++) {
    if (i == 0) {
      prefix = str[i];
    }
 
    if (prefix != str[i] || i == str.length - 1) {
      if (i == str.length - 1) {
        num++;
      }
      if (num == 1 || num == 2) {
        result = result + prefix.repeat(num);
      } else {
        result = result + prefix + num;
      }
 
      prefix = str[i];
      num = 0;
    }
    num++;
  }
  return result;
}

Author 回答者: yuli-lovely

// number<10--适用下面
function decode(str) {
  let result = "";
  for (let i = 1; i <= str.length; i++) {
    console.log();
    if (typeof parseInt(str[i]) === "number") {
      result = result + str[i - 1].repeat(parseInt(str[i]));
    }
  }
  return result;
}
//全场景适用
function decode2(str) {
  let datas = Array.from(str.matchAll(/[a-z][0-9]*/g));
  let result = "";
  for (elem of datas) {
    elem = elem[0];
    result = result + elem[0];
    if (elem.length > 1) {
      result = result + elem[0].repeat(parseInt(elem.substr(1)) - 1);
    }
  }
  return result;
}

Author 回答者: litingyes

好像没看到用正则的解法，我来补充一下:kissing: 感觉用正则来实现，修改编码条件也挺简单的

function encode(str) {
  let res = "";
  const reg = /(\w)\1*/g;
  const matchs = str.match(reg);
  matchs.forEach((item) => {
    if (item.length > 1) {
      res += item[0] + item.length;
    } else {
      res += item[0];
    }
  });
 
  return res;
}

Author 回答者: fanfankill

function encode(str) {
  //
  let index = 0;
  let result = "";
  while (index < str.length) {
    let count = 1;
    result += str[index];
    while (str[index] == str[index + 1]) {
      index++;
      count++;
    }
    index++;
    result += count;
  }
  console.log(result);
  return result;
}

Author 回答者: xyuh111

const encode = (str) => str.replace(/([a-zA-Z])\1+/g, (all, p1) => p1 + all.length)

Author 回答者: coderWxs

const encode = (str) => {
  let hash = {};
  for (const s of str) {
    hash[s] = hash[s] + 1 || 1;
  }
  let s = "";
  for (const [key, value] of Object.entries(hash)) {
    //如果只出现一次，不编码数字
    if (value === 1) {
      s = s + key;
    } else if (value === 2) {
      //如果只出现两次，不进行编码
      s = s + key + key;
    } else {
      s = s + key + value;
    }
  }
  return s;
};

Author 回答者: Hazel-Lin

// => a4b3c2
console.log(encode("aaaabbbcc"));
 
// => a4b3a4
console.log(encode("aaaabbbaaaa"));
 
// => a2b2c2
console.log(encode("aabbcc"));
 
// =>a3b
console.log(encode("aaab"));
 
function encode(str) {
  const list = str.split("");
  let res = "";
  let count = 1;
 
  for (let i = 0; i < list.length; i++) {
    if (list[i] !== list[i + 1]) {
      if (count === 1) {
        res += list[i];
      } else {
        res += list[i] + count;
      }
      count = 1;
    } else {
      count++;
    }
  }
  return res;
}

Author 回答者: Ghaining

function encode(str) {
  var result = "";
  var count = 1;
  for (var i = 0; i < str.length; i++) {
    if (str[i] === str[i + 1]) {
      count++;
    } else {
      result += str[i] + count;
      count = 1;
    }
  }
  console.log(result);
}

Author 回答者: nqsjd178559344

// todo 对以下数字进行编码压缩

function encode(string, count = 0) {
  const array = string.split("");
  let resultArray = [];
  for (let index = 0; index < array.length; index++) {
    let charCount = 1;
    while (array[index] === array[index + 1]) {
      index++;
      charCount++;
    }
    resultArray.push([array[index], charCount]);
  }
 
  return resultArray.reduce((pre, [item, _count]) => {
    if (count >= _count) {
      pre += item.repeat(_count);
    } else {
      pre += `${item}${_count}`;
    }
    return pre;
  }, "");
}

// todo 如果进行解码，碰到数字如何处理？

function decode(string) {
  let res = "";
  const array = string.split("");
  for (let index = 0; index < array.length; index++) {
    const element = array[index];
    const count = Number(element);
    if (isNaN(count)) {
      res += element;
    } else {
      //   将前一个字符重复count-1次
      res += array[index - 1].repeat(count - 1);
    }
  }
 
  return res;
}

Author 回答者: Charry-C

双指针法

function BestenCode(input, min) {
  let slow = 0;
  let arr = [],
    Output = "";
  for (let i = 1; i <= input.length; i++) {
    if (input[i] !== input[slow]) {
      arr.push(input.slice(slow, i));
      slow = i;
    }
  }
  arr.forEach((e) => {
    if (e.length <= min) {
      Output = Output + e;
    } else {
      Output = Output + e[0] + e.length;
    }
  });
  return Output;
}

Author 回答者: loveminxo

这是来自QQ邮箱的假期自动回复邮件。你好，我最近正在休假中，无法亲自回复你的邮件。我将在假期结束后，尽快给你回复。

【Q288】如何求数组中的 TOP k 【Q673】求给定数组中 N 个数相加之和为 sum 所有可能集合