第 114 题：找出字符串中连续出现最多的字符和个数 #220
Comments
|
|
暴力版 function getStrMaxLengthObj (str) {
if (!str) { return {} }
let strObj = {}
let res = {}
let max = 0
let currentLetter = ''
for (let i = 0; i < str.length; i ++) {
let item = str[i]
if (currentLetter === item) {
strObj[item] += 1
} else {
currentLetter = item
strObj[item] = 1
}
if (strObj[item] > max) {
max = strObj[item]
res = {}
res[item] = max
} else if (strObj[item] === max) {
res[item] = max
}
}
return res
}
console.log(getStrMaxLengthObj('abbkejsbcccwqaa')) //- {c:3} |
一次遍历function findLongest(str) {
if (!str) return {}
let count = 0
let maxCount = 0
let cur = str[0]
let res = {}
for (let i = 0; i < str.length; i++) {
const s = str[i]
if (s === cur) {
count++
if (count > maxCount) {
res = { [s]: count }
maxCount = count
}
if (count === maxCount) {
res[s] = count
}
} else {
count = 1
cur = s
}
}
return res
}时间复杂度O(n), 空间复杂度O(1) |
function getMax(str) {
let c = "";
let res = Array.from(str).reduce((acc, cur) => {
if (c == cur) {
acc[cur] = acc[cur] ? acc[cur] + 1 : 2;
} else {
acc[cur] = 1;
}
c = cur;
return acc;
}, {});
let max = Math.max.apply(null, Object.values(res));
let ret = {};
for (let k in res) {
if (res[k] == max) {
ret[k] = max;
}
}
return ret;
}
console.log(getMax("abbkejsbcccwqaa")); //{c: 3}
console.log(getMax("abcaakjbb")); //{a: 2, b: 2} |
const func = (str) => {
let temp = '-1'
let count = 0
let maxCount = 0
// 传入的字段串增加一位，防止以连续字母结尾的统计出错
str += '-1'
const res = {}
while(str.length > 0) {
// 相同字符串，统计+1
if (temp === str[0]) {
count ++
res[temp] = count
} else {
// 遇到不同，比较当前连续的字符是否是最长的
if (res[temp] >= maxCount) {
maxCount = res[temp]
} else {
delete res[temp]
}
count = 1
temp = str[0]
}
str = str.substring(1)
}
return res
}
// const str = 'abbkejsbcccwqaa'
const str = 'abcaakjbb'
const res = func(str)
console.log('res', res) |
function findChar(char) {
let obj = {};
let reg = /(\w)\1/g;
char.match(reg).map(str = >Object.keys(obj).indexOf(str) > -1 ? obj[str] = obj[str] + str.length: obj[str] = str.length);
return obj
}
findChar('abbkejsbbcccwqaa'); |
|
'aaasdofjaopfjopaiiisjssfopiasdfffff'.match(/(.)\1+/g)得到的结果是 ["aaa", "iii", "ss", "fffff"]从这个数组里面找长度最长的元素并转化成需要的结果应该简单了吧 |
|
|
习惯了用正则处理一些字符串的问题，感觉还可以优化，期待大佬版本
function searchLongChar(str, max = 0, obj = {}) {
// 提取重复串组合
let arr = str.match(/(\w)\1+/g);
if(arr==null) return;
arr.map(v => {
let l = v.length;
if (max <= l) {
// 重置数组
if (max < l) obj = {};
// 赋值
obj[v.substr(-1)] = max = l;
}
})
return obj;
} |
Closed
|
Object.fromEntries 是 ES10 语法，使用高版本的浏览器或者 NodeJs 版本运行 function func(str) {
let obj = str.split("").reduce((pre, cur) => {
pre[cur] ? pre[cur]++ : pre[cur] = 1
return pre
}, {})
let maxNum = Math.max(...Object.values(obj)) // 获取最多的次数
let entries = Object.entries(obj).filter(([_, value]) => value === maxNum) // 过滤出出现最多次数的键值对
return Object.fromEntries(entries) // 将键值对转换为对象（ES10 语法）
}
console.log(func('abcaakjbb'))
console.log(func('abbkejsbcccwqaa')) |
|
全面通用~~~ |
是连续出现最多，不是出现最多 |
|
上面的麻烦学学markdown语法再发好吗？看着难受
function getMaxCharacters(str) {
const map = {}
var arr = str.match(/(\w)\1+/g)
var max = arr[0].length
arr.map(v => max = Math.max(max, v.length))
const maxArr = arr.filter(v => v.length === max)
maxArr.forEach(v => {
map[v[0]] = v.length
})
return map
}
getMaxCharacters('abcaakjbb') // { a: 2, b: 2 } |
const str = 'abbkejsbcccwqaa'
function fn(str) {
let i = 0
let result = {}
let prev = ''
let max = 0
while(i < str.length) {
const cur = str[i]
if (prev === cur) {
if (result[prev]) {
result[prev]++
} else {
result[prev] = 2
}
max = Math.max(result[prev], max)
}
prev = str[i]
i++
}
return Object.keys(result).reduce((prev, key) => {
const val = result[key]
if (val === max) {
prev[key] = val
}
return prev
}, {})
}
console.log(fn(str)) |
强行使用map保存了每个连续字符串的个数，然后在使用遍历找到出现次数最多的一个或者多个function searchMaxStr(str) {
let map = new Map();
let result = {}//保存最后的结果
let middle = str[0];
let count = 0;
for (let i = 0, length = str.length; i < length; i++) {
let temp = str[i];
if (temp == middle) {
count++;
if (map.has(temp)) {
if (count > map.get(temp)) {
map.set(temp, count)
}
} else {
map.set(temp, count)
}
} else {
count = 0;
i = i - 1;
middle = temp;
}
}
let bianli = 0;
for (let key of map.keys()) {
value = map.get(key)
if (bianli < value) {
bianli = value;
if (Object.keys(result) != 0) {
result = {}
} else {
result[key] = value;
}
}
if (bianli == value) {
result[key] = value
}
}
return result;
} |
|
|
// 'abcaakjbb' => {'a':2,'b':2}
// 'abbkejsbcccwqaa' => {'c':3}
// 注意：题目说的是连续出现，注意连续二字
function getMaxTimes(str) {
var maxMap = {};
let currentTimes = 0;
let maxTimes = 0;
let char;
let nextChar;
for (let i = 0, len = str.length; i < len; ) {
char = str[i];
// 检查下一个...
let j = 0;
do {
j++;
nextChar = str[i + j];
currentTimes++;
} while (nextChar === char);
maxMap[char] = currentTimes;
// 顺便记录下最大出现次数
if (currentTimes > maxTimes) maxTimes = currentTimes;
currentTimes = 0;
i += j;
}
// 去掉无用的记录
Object.keys(maxMap).forEach(k => {
if (maxMap[k] !== maxTimes) delete maxMap[k];
});
return maxMap;
}
console.log(getMaxTimes('abcaakjbb'));
console.log(getMaxTimes('abbkejsbcccwqaa')); |
|
空间复杂度: O(1)；时间复杂度: O(N) function getMaxContinuousStrLen(str) {
if (typeof str !== 'string' || !str.length) {
return ['', 0]
}
const length = str.length
let last = str[0],
times = 1,
maxTimes = 0,
maxChar = ''
for (let i = 1; i < length; ++i) {
if (str[i] === last) {
++times
} else {
if (times > maxTimes) {
maxChar = last
maxTimes = times
}
times = 1
last = str[i]
}
}
if (times > maxTimes) {
maxChar = last
maxTimes = times
}
return [maxChar, maxTimes]
}
// 测试代码
console.log(getMaxContinuousStrLen('b')) //[ 'b', 1 ]
console.log(getMaxContinuousStrLen('abb')) //[ 'b', 2 ]
console.log(getMaxContinuousStrLen('abbkejsbcccwqaa')) // [ 'c', 3 ]
console.log(getMaxContinuousStrLen('abcaakjbb')) // [ 'a', 2 ] |
function findTargetStr(str) {
return (str.match(/(.)\1*/g) || []).reduce((res, cur) =>
(
cur.length > res.max ?
(res.r = { [cur[0]]: cur.length }, res.max = cur.length) :
(cur.length === res.max && (res.r[cur[0]] = res.max)
), res), { r: {}, max: 0 }).r
} |
const findMaxConstantString = str => {
const result = []
str.replace(/(\S\w)(\1)+/g, matched => {
result.push({[matched[0]]:matched.length})
})
return Object.assign(...result.filter( oRes => Object.values(oRes)[0] === Math.max(...result.map(counter =>Object.values(counter)[0]))))
}
// 好多大佬。。。献上我的渣渣版本 好多地方还可以优化 |
|
function getMax(){ 菜鸟版本 |
const a = 'abcaakjbb'; const b = 'abbkejsbcccwqaa'
function findLetter (str = '') {
const res = str.match(/(.)\1+/g).reduce((acc, next) => {
const maxLen = Math.max(Object.values(acc))
const nextObj = { [next.charAt(0)]: next.length }
const newAcc = maxLen > next.length ? acc : (maxLen === next.length ? Object.assign(acc, nextObj) : nextObj)
return newAcc
}, {})
return res
}
console.log(findLetter(b)) // { c: 3 }
console.log(findLetter(a)) // { a: 2, b: 2 } |
function searchMaxStr(str) {
const result = {}
const continuous = str.match(/(\w)\1+/g)
const max = continuous.reduce((max, curStr) => curStr.length > max ? curStr.length : max, 0)
continuous.forEach(item => {
if (item.length === max) {
result[item] = max
}
})
return result
}
searchMaxStr('abcaakjbb')
searchMaxStr('abbkejsbcccwqaa') |
var s = 'awo[eigoawjeogpawkegak11111111111wef,.xcmvjawoegjawjegoaiwjsdm,.vmkadjsfawgefo eighaerg4a5g4'
function func(s){
var Obj = s.split('').reduce((acct, cur) => {
let item = acct[cur];
item = item ? item + 1 : 1
return { ...acct, [cur]: item }
}, {})
var max = Math.max(...Object.values(Obj))
return Object.keys(Obj).reduce((acct, cur) => Obj[cur] === max ? { ...acct, [cur]: Obj[cur] }:acct,
{})
}
func(s) |
看大佬们都使用正则表达式进行匹配，小弟就不用正则来个版本主要思路如下：
const findMaxRepeatString = str => {
if (typeof str !== 'string') return {};
const strToObj = Array.prototype.reduce.call(
str,
(pre, next) => {
let track = pre.temp[next];
if (!track) {
pre.temp = {
[next]: 1,
};
return pre;
}
track = ++pre.temp[next];
if (track < 2) return pre;
const v = track - (pre[next] || 0);
pre[next] = v >= 1 ? track : pre[next];
return pre;
},
{ temp: {} }
);
delete strToObj.temp;
const max = Math.max(...Object.values(strToObj));
if (max < 2) return {};
return Object.keys(strToObj)
.filter(key => strToObj[key] === max)
.reduce((pre, key) => {
pre[key] = strToObj[key];
return pre;
}, {});
};
findMaxRepeatString ('aa11bbbppbbb'); // { b: 3 } |
function count(str) {
if (!str) return {};
let hashMap = {};
let i = 1;
let cur = str[0];
for (let j = 1; j < str.length; j++) {
let temp = str[j];
if (temp === cur) {
i++;
hashMap[temp] = i;
} else {
i = 1;
cur = temp;
}
}
let res = Object.keys(hashMap).map(key => hashMap[key]);
res = Math.max(...res);
for (let key in hashMap) {
if (hashMap[key] < res) {
delete hashMap[key]
}
}
return hashMap
} |
/*
第 114 题：编程题，找出字符串中连续出现最多的字符和个数（蘑菇街）
'abcaakjbb' => {'a':2,'b':2}
'abbkejsbcccwqaa' => {'c':3}
*/
function sequenceChar(str){
const chars = str.split('');
let count = 0;
let max = 0
let res = {};
chars.reduce((pre,cur,index)=>{
if(pre===cur){
count++;
if(count>max){
res = {[pre]:count}
max = count;
}
if(count === max){
res[pre] = count;
}
}else{
count=1;
res[pre] = 1;
if(index===chars.length-1){
res[chars[index]] = count;
}
}
return cur;
});
return res;
}
console.log(sequenceChar('abkejsbcwqa')); |
function getMaxStr(str) {
let map = {}
let resultArr = []
let max = Number.NEGATIVE_INFINITY
let k = 1
for (let i = 1; i < str.length; i++) {
if (str[i] == str[i-1]) {
k++
if (k > max) {
resultArr = [str[i]]
}
if (k == max) {
resultArr.push(str[i])
}
// max = k
max = Math.max(k, max)
} else {
k = 1
}
}
console.log(resultArr, max)
for (let i = 0; i < resultArr.length; i++) {
map[resultArr[i]] = max
}
return map
} |
|
function findNum(str){ 一次遍历完成，复杂度O(n) |
// 编程题，找出字符串中 **连续** 出现最多的字符和个数（蘑菇街）
const str1 = 'abcaakjbb'
const result1 = { a: 2, b: 2 }
const str2 = 'abbkejsbcccwqaa'
const result2 = { c: 3 }
function findMax(str) {
let map = {}
let pre = ''
let preLen = 0
let cur = ''
let curLen = 0
for (let i = 0; i < str.length; i++) {
const s = str[i]
const next = str[i + 1]
if (s === next) {
cur = s
curLen = curLen ? ++curLen : 2
} else {
if (curLen > preLen) {
if (pre === cur) {
preLen = curLen
map[cur] = curLen
} else {
map = {
[cur]: curLen
}
pre = cur
preLen = curLen
}
}
if (curLen === preLen) {
if (pre !== cur) {
map[cur] = curLen
}
}
cur = ''
curLen = 0
}
}
console.log(map)
return map
}
const find1 = findMax(str1)
console.log(JSON.stringify(find1) === JSON.stringify(result1))
const find2 = findMax(str2)
console.log(JSON.stringify(find2) === JSON.stringify(result2)) |
可以简化很多计算量！ |
|
Map集合连续出现次数 const getMaxNum = (str) => {
let arr = str.split('');
var map = new Map;
var lastMsg = '';
// arr.forEach(item => map.set(item, map.has(item) ? map.get(item) + 1 : 1))
arr.forEach(item => {
map.set(item, lastMsg === item ? map.get(item) + 1 : 1);
lastMsg = item;
});
return [...map].reduce((pre, item) => {
return item[1] > pre[0][1] ? [item] : item[1] === pre[0][1] ? pre.concat([item]) : pre;
}, [['', 0]]).reduce((pre, item) => {
return (pre[item[0]] = item[1]) && pre;
}, {});
}; |
|
function maxChar (str) {
var has = {}
for (var i = 0; i < str.length; i++) {
if (str[i] === str[i+1]) {
has[str[i]] = has[str[i]] ? has[str[i]] + 1 : 2
}
}
var max = 0, map = {}, keys = []
for (var k in has) {
if (has[k] >= max) {
max = has[k]
keys.push(k)
}
}
for (var i = keys.length - 1; i >= 0; i--) {
if (has[keys[i]] >= max) {
map[keys[i]] = has[keys[i]]
}
}
return map
} |
function getMaxTimes(str) {
if (!str) return {};
let res = {};
let m = 0; // 最大次数
let i = 1; // 当前元素次数
let j = 1; // 当前迭代位置
while (j < str.length) {
if (str[j] === str[j - 1]) {
i++;
} else {
if (i > m) {
res = { [str[j - 1]]: i };
m = i;
} else if (i === m) {
res[str[j - 1]] = i;
}
i = 1;
}
j++;
}
// 处理最后的元素
j = str.length - 1;
if (i > m) {
res = { [str[j]]: i };
} else if (i === m) {
res[str[j]] = i;
}
return res;
} |
function maxSeq(str) {
let _str = str+'*'
let temp = {}
let res = {}
let max = 0
for(let i=0;i<_str.length;i++){
const letter = _str[i]
if(temp[letter]){
temp[letter]++
}else{
const key = Object.keys(temp)[0]
const value = temp[key]
if(i > 0){
if(max<value){
max = value
res = {
[key]: value
}
}else if(max===value){
for(let i in res){
if(res[i]<max){
delete res[i]
}
}
res[key] = value
}
}else{
res[letter] = 1
max = 1
}
temp={
[letter]: 1
}
}
}
return res
} |
function getMax(str) {
let l = 0,
r = 0;
const map = {};
let maxCount = 0,
count = 0;
while (r <= str.length) {
const char = str[r];
if (char !== str[l]) {
// 若字符和前面不相同，结束统计，更新最大值，窗口左端右移到当前位置，重置 count
if (count >= maxCount) {
maxChar = str[r-1];
maxCount = count;
if (map[maxCount]) {
map[maxCount].push(str[r-1]);
} else {
map[maxCount] = [str[r-1]];
}
}
count = 0;
l = r;
continue;
}
// 若字符和前面相同，继续统计，移动窗口右端点
count ++;
r ++;
}
const maxChars = map[maxCount];
const result = {};
maxChars.forEach(c => {
result[c] = maxCount;
});
return result;
}关于字符串和数组的“连续”问题，一般可以用滑动窗口来解决。 |
|
双指针 一次遍历 除开输出 空间O(1) ` ` |
function max (str) {
let max = 0
let char
let prevchar
const map = {}
for (let c of str) {
map[c] = map[c] ? (prevchar === c ? map[c] + 1 : 1) : 1
if (map[c] > max) {
max = map[c]
char = c
}
prevchar = c
}
return { [char]: max }
} |
|
我写了个最low的，花了1.5小时。。。虽然周围很吵，但是一开始确实没思路 卧槽，我看错了，没注意是连续！！！以下代码找的是所有 const findTheMostFrequentStr = (str) => {
let keys = [], values = []
for (let i = 0; i < str.length; i++) {
const index = keys.indexOf(str[i])
if (index === -1) {
keys.push(str[i])
values.push(1)
} else {
values[index] += 1
}
}
let obj = {}
values.reduce((p, n, index) => {
if (p === n) {
obj[keys[index]] = n
if (index === 1) {
obj[keys[0]] = n
}
return n
}
if (p < n) {
obj = {}
obj[keys[index]] = n
return n
}
if (p > n) {
if (values[index - 1] === p) {
obj[keys[index - 1]] = p
}
return p
}
})
return obj
}连续的low版实现（不会正则，第一次忘了Math.max）const findTheMostFrequentStr = (str) => {
let keys = [], values = []
for (let i = 0; i < str.length; i++) {
let index = keys.indexOf(str[i])
if (index === -1) {
keys.push(str[i])
values.push(1)
} else {
// 判断是否连续
const start = str.indexOf(str[i]) // 先找到目标在字符第一次出现的位置
if (str.substring(start, i + 1).split('').every(item => item === str[i])) {
values[index] += 1
}
}
}
const max = Math.max(...values)
let obj = {}
values.forEach((val, index) => {
if (val === max) {
obj[keys[index]] = max
}
})
return obj
} |
var entry = 'abcaakjbb'
function change(str){
let left = right = 0,res = {},maxLen = 0
while(right < str.length){
if(str[left] === str[right + 1]){
right++
}else{
let len = right - left + 1
if(len > maxLen){
maxLen = len
res = {}
res[str[left]] = len
}else if(len == maxLen){
res[str[left]] = len
}
left = ++right
}
}
return res
}
console.log(change(entry)) |
// 找出 字符串中连续出现 最多的字符
function countChar(str) {
var len = str.length
if (len == 0) {
return 0
}
if (len == 1) {
return 0
}
var map = {}
var max = 2
var index = 0
var next = 1
while (next <= len) {
if (str[index] != str[next]) {
var leng = next - index
if (!map[str[index]] || leng > map[str[index]]) {
if (leng > max) {
map = {}
max = leng
}
if (leng >= max) {
map[str[index]] = leng
}
}
index = next
next++
} else {
next++
}
}
return Object.keys(map).length ? map : 0
} |
function getMaxCharacters(str) {
const map = {}
var arr = str.match(/(\w)\1+/g)
var max = arr[0].length
const maxArr = arr.filter(v => v.length === max)
maxArr.forEach(v => {
map[v] = v.length
})
return map
}最终简化版 |
let str = 'abbkejsbcccwqaa'
function getMaxSame(str) {
const len = str.length
let result = {}
const temp = {}
for (let i = 0; i < len - 1; i++) {
const char = str[i]
if (char === str[i + 1]) {
if (temp[char]) {
temp[char] = temp[char] + 1
} else {
temp[char] = 2
}
} else {
}
}
// 找到最大的
let temp2
for (let key in temp) {
const value = temp[key]
if (!temp2) {
temp2 = value
result[key] = value
continue
}
if (value > temp2) {
temp2 = value
result = {}
result[key] = temp2
} else if (value === temp2) {
result[key] = value
}
}
console.log(temp)
return result
}
console.log(getMaxSame(str)) |
function getRepetCount(str) {
let maxChars = '';
let maxCount = 0;
let length = str.length;
let count = 1;
for (let index = 1; index < length; index++) {
const cur = str[index];
const pre = str[index - 1];
if (cur === pre) {
count++;
} else {
if (count > maxCount) {
maxCount = count;
maxChars = pre;
}
count = 1;
}
}
return {
[maxChars]: maxCount
}
}
|
function getRepetCount(string) {
const list = string.match(/(.)\1*/g)
let max = 0
let object = {}
for (const str of list) {
if (str.length > max) {
max = str.length
object = {}
}
object[str] = str.length
}
return object
} |
let strss = 'abcaakjbbb'const find11 = (str) => { |
function getMax(str){
let max = 0
const arr = str.split('') // 切割为数组
const obj = {} // 记录长度
arr.forEach(key =>{
if(!(key in obj)){
obj[key] = 0
}
obj[key]++
max = Math.max(max,obj[key]) // 记录最大值
})
return Object.entries(obj).filter(item => max == item[1]).reduce((prv,[key,val])=>{
// 转化长度键值对 过滤长度与max相同的值 根据过滤的值创建对象并返回
prv[key] = val
return prv
},{})
}
console.log(getMax('abcaakjbb'))
function getMax(str){
let max = 0
let arr = []
let s = str
const strs = [...new Set(str.split(''))] // 切割转数组 => 转set去冲 => 转数组
strs.forEach(key =>{ // 遍历去冲的数据
let len = s.length // 获取字符串的长度
s = s.replaceAll(key,'') // 替换字符串
const diff = len - s.length // 计算替换了几个字符
switch (true){
case diff > max: // 如果替换的字符大于max
max = diff // 覆盖max
arr = [key] // arr 重置
break
case diff == max: // 如果等于max
arr.push(key) // 推入arr中
break
}
})
return arr.reduce((prv,key)=>{ // 聚合数据
prv[key] = max
return prv
},{})
} |
function find(str) {
var res = {}
// preChar：记录上一个字符，count：记录当前字符已连续次数，maxCount：表示最大连续字符次数
var preChar = '', count = 0, maxCount = 0
for(let i = 0; i< str.length; i++) {
var cur = str[i]
// 字符连续则累加，否则重置为 1
if(cur === preChar) {
count++
} else {
count = 1
}
preChar = cur
if(count === maxCount) {
// 多个字符连续次数相同的情况
res[cur] = count
} else if(count > maxCount){
maxCount = count
// 清空
res = {}
res[cur] = count
}
}
return res
}
find('abcaakjbb') // {a: 2, b: 2}
find('abbkejsbcccwqaa') // {c: 3} |
// 双指针
function resolve (str) {
let i = 0;
let max = 0;
const map = {};
const result = {};
while (i<str.length) {
j = i + 1;
while (j<=str.length) {
if (str[i] !== str[j]) {
if (!map[str[i]]) {
map[str[i]] = 0;
}
map[str[i]] = Math.max(map[str[i]], j - i);
max = Math.max(max, j - i);
break;
}
j++;
}
i++;
}
for (let key in map) {
if (map[key] === max) {
result[key] = max;
}
}
return result;
}
resolve('abcaakjbb') |
|
|
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
and others
注意：题目说的是连续出现，注意连续二字
The text was updated successfully, but these errors were encountered: