极客时间返利平台,你可以在上边通过山月的链接购买课程,并添加我的微信 (shanyue94) 领取返现。

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

更多描述

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

  • 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 (opens new window)

编写函数 encode 实现该功能

代码见 【Q412】对以下字符进行压缩编码 - codepen (opens new window)

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

Author

回答者: LiJinWD (opens new window)

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 (opens new window)

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 (opens new window)

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"

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

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 (opens new window) 上出现了这个题目

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 (opens new window)

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 (opens new window)

最基础功能的实现:

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 (opens new window)

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 (opens new window)

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 }

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

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

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;
}
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 (opens new window)

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

Last Updated: 6/26/2022, 10:48:10 AM