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

[shfshanyue]

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

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

有以下测试用例

//=> a4b3c2
encode('aaaabbbcc')

//=> a4b3a4
encode('aaaabbbaaaa')

//=> a2b2c2
encode('aabbcc')

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

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

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

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

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

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

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

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

[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)

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

[shfshanyue]

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

[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'));

[ghost]

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("");
  }
}

[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
  }, '')
}

[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("")
}

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

[LiJinWD]

const encode = word => { if(!word) return ""; let ary = word.split(''); let group = {} let result = "" group[ary[0]] = 1 for(let i = 1, j = ary.length; i <= j; i++) { if(ary[i - 1] != ary[i]) { result += Object.entries(group).flat().join('') group = {} group[ary[i]] = 1 } else { group[ary[i]]++ } } return result

}

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 }

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

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

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

[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

    }

[xyuh111]

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

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

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

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

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

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

[loveminxo]

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