# 对以下字符串进行压缩编码
更多描述
这是一道大厂常考的代码题
- 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)
Author
编写函数 encode 实现该功能
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
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
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
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
@haiifeng 注意标记下 js 的语法高亮
Author
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
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
最基础功能的实现:
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
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
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 }
Author
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
// 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
好像没看到用正则的解法，我来补充一下😗 感觉用正则来实现，修改编码条件也挺简单的
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
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
const encode = (str) => str.replace(/([a-zA-Z])\1+/g, (all, p1) => p1 + all.length)
Author
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;
};