前端知识体系

Appearance

大纲

对字符串进行压缩编码 ​

这是一道大厂常考的代码题

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

有以下测试用例

js
//=> a4b3c2
encode('aaaabbbcc')

//=> a4b3a4
encode('aaaabbbaaaa')

//=> a2b2c2
encode('aabbcc')

编写函数 encode 实现该功能

js
function encode(str) {
  // ...
}

追问 ​

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

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

解决方案 ​

js
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('')
}

// 方案三
function encode3(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('');
};
encode3('aaaabbbccd'); // 'a4b3c2d1'
encode3('aaaabbbccd', 1); // 'a4b3c2'
encode3('aaaabbbccd', 2); // 'a4b3'

追问 ​

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

解决方案

js
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('')
}

解码

js
function decode(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
}