第96题 获取字符串中连续最多的字符以及次数
题目：输入
abbcccddeeee1234，计算得到：连续最多的字符是e，次数是4次
思路分析
- 嵌套循环：传统思路
- 找出每个字符的连续次数，并记录
- 时间复杂度是
O(n)，而不是O(n^2)，因为有“跳步”
- 双指针
- 定义指针
i和j，j不动，i继续移动 - 如果
i和j的值一直相等，则i继续移动 - 直到
i和j的值不相等，记录处理，让j追上i，继续第一步
- 定义指针
求连续最多的字符和次数（嵌套循环）
// 数据结构
interface IRes {
char: string
length: number
}
/**
* 求连续最多的字符和次数（嵌套循环）
* @param str str
*/
function findContinuousChar1(str) {
// { char: 'e', length: 4}
const res = {
char: '', // 连续最多的字符
length: 0 // 连续最多的字符次数
}
const length = str.length
if (length === 0) return res
let tempLength = 0 // 临时记录当前连续字符的长度
// 时间复杂度 O(n)
// 思路图解 
for (let i = 0; i < length; i++) {
tempLength = 0 // 每次循环都重置
for (let j = i; j < length; j++) {
if (str[i] === str[j]) {
tempLength++
}
// 不相等，或者已经到了最后一个元素
if (str[i] !== str[j] || j === length - 1) {
// 去判断tempLength跟上次的保存的res.length 当tempLength大于res.length时，更新res值
if (tempLength > res.length) {
res.char = str[i]
res.length = tempLength
}
// 外层循环还在继续
if (i < length - 1) {
// aaabbcccddeeee11223 对比完成后，把 i 跳到 j 的位置 (从第一个a的位置跳到第一个b的位置)
// i j => i指向a j指向b str[i] !== str[j]
// i = j - 1
i = j - 1 // 对比完连续的字符a后，跳步，让i追上j，如j=11，则j=10
}
break // 跳出j的这层循环
}
}
}
return res
}
求连续最多的字符和次数（双指针）
- 定义指针
i和j，j不动，i继续移动 - 如果
i和j的值一直相等，则i继续移动 - 直到
i和j的值不相等，记录处理，让j追上i，继续第一步
/**
* 求连续最多的字符和次数（双指针）
* @param str str
*/
function findContinuousChar2(str) {
const res = {
char: '',
length: 0
}
const length = str.length
if (length === 0) return res
let tempLength = 0 // 临时记录当前连续字符的长度
// 定义指针`i`和`j`，`j`不动，`i`继续移动
let i = 0
let j = 0
// O(n)
// 
for (; i < length; i++) {
// 如果`i`和`j`的值一直相等，则`i`继续移动
if (str[i] === str[j]) {
tempLength++ // 累加次数
}
// 如果`i`和`j`的值一直相等，则`i`继续移动
if (str[i] !== str[j] || i === length - 1) {
// 不相等，或者 i 到了字符串的末尾
if (tempLength > res.length) {
res.char = str[j] // 这里取str[j]
res.length = tempLength
}
tempLength = 0 // reset
if (i < length - 1) {
j = i // 让 j “追上” i
i-- // 先i--，因为会在下一次循环中i++会重新加回来，否则i和j会错开
}
}
}
return res
}
// 功能测试
const str = 'aabbcccddeeee11223'
console.info(findContinuousChar2(str))
// 性能测试
let str = ''
for (let i = 0; i < 100 * 10000; i++) {
str += i.toString()
}
// 循环方式
console.time('findContinuousChar1')
findContinuousChar1(str)
console.timeEnd('findContinuousChar1') // 219ms
// 双指针方式
console.time('findContinuousChar2')
findContinuousChar2(str)
console.timeEnd('findContinuousChar2') // 228ms
其他方式
- 正则表达式-效率非常低，慎用
- 累计各个元素的连续长度，最后求最大值--徒增空间复杂度
- 算法题尽量用过“低级”代码，慎用语法糖或高级API
// 累计各个元素的连续长度，最后求最大值--徒增空间复杂度
// obj随str的长度增加而增加，徒增空间复杂度O(n)
var str = 'aabbbcccccdddddddd';
var obj = {}; //创建一个对象
for(var i=0;i < str.length; i++){//每一个字符都要知道次数，所以要循环
var char = str.charAt(i);//返回指定索引处的字符
if(obj[char]){
obj[char]++
}else{
obj[char] = 1;
}
}
console.log(obj);//{a:2,b:3,c:5,d:8}
// 正则表达式-效率非常低，慎用
// 先获取次数最多的字符和次数的变量，对原始字符串进行排序（字符串转为数组，数组进行排序后转为字符串），正则匹配到重复内容，再进行判断
var value = '';
// 出现的次数的变量
var index = 0;
//原始字符串改为计算好的字符串（排序）
var str = 'aabbbcccccdddddddd';
//字符串转换为数组
var arr = str.split('');
//数组进行排序再改为字符串
var str = arr.sort().join('');
//正则匹配到了重复内容
var reg = /(\w)\1+/g;
//判断
str.replace(reg,function(val,item){
if(index<val.length){
index = val.length;
value = item;
}
})
console.log('出现次数做多的字符是:'+value,'出现的次数是:'+index); // d 8