上题目
给你一个字符串 s
,返回该字符串中连续最多的字符和连续次数。
示例:
输入: s = "abbcccddddeeeeedcba" 输出: {char: 'e', length: 5} 解释: 子字符串 "eeeee" 长度为 5 ,只包含字符 'e' 。
常规思路 - 双层循环
使用双层循环,遍历出所有的连续字符的case,比较长度,获取到连续最多的字符和连续次数。
边看代码,边看逻辑
// 定义结果 interface IRes { char: string; length: number; } /** * @method findMaxContinuousChar1 * @description 获取字符串中最多连续字符和次数 - 双层循环 * @param s * @returns */ function findMaxContinuousChar1(s: string): IRes { // 定义结果初始值 const res: IRes = { char: '', length: 0, }; // 获取字符串长度 const len = s.length; // 临界点判断 if (len === 0) return res; // 遍历字符串 for (let i = 0; i < len; i++) { // 用于记录重复字符的长度 let tmpMaxContinuousCharLenth = 0; // s[i] 当前字符 for (let j = i; j < len; j++) { // s[j] 是从i索引开始的字符,与s[i]进行比对,如果不一致了,说明已经不是重复字符了 if (s[j] !== s[i]) { // 不相等时,s[j]已经是一个新字符了 // 移动当前i索引位置 -> 到最新一个字符j索引位置 i = j - 1; // 最外层循环还要执行++,所以这里是j - 1 // 打断当前循环,已经没有意义了 break; } else { // 相等 - 将repeat tmpMaxContinuousCharLenth++; } } // j的循环执行完毕有两种情况: // 1. s[j] !== s[i],被break打断 // 2. s[j]和s[i]一直相等,一直到字符串的末尾,如 'aaeee'、'eeee'这种情况 // 统一判断处理 if (tmpMaxContinuousCharLenth > res.length) { res.length = tmpMaxContinuousCharLenth; // 注意这里必须是s[i],这是标志的原起始字符 res.char = s[i]; } } // 返回最终结果 return res; }
功能测试:
const s1: string = 'abbcccddddeeeeedcba'; const s2: string = 'aabbbbbbbb'; const res1 = findMaxContinuousChar1(s1); const res2 = findMaxContinuousChar1(s2); console.log(res1); // {char: 'e', length: 5} console.log(res2); // {char: 'b', length: 8}
效果非常OK!
算法复杂度:
- 空间复杂度: 临时变量tmpMaxContinuousCharLenth的声明,最多O(n)O(n)O(n)。
- 时间复杂度:可能会有很多小伙伴认识时间复杂度是两层循环 O(n2)O(n^2)O(n2),其实不是。在程序中我们执行了一个“跳步”操作
i = j - 1
,也就是将重复字符的位置给跳过了,实际上执行的还是O(n)O(n)O(n)。
双指针的妙用
使用专门的指针变量j
指向每一个不重复字符的第一个索引位置,在字符串s = 'abbbcdd'
中,指针j
依次指向第一个a
、b
、c
、d
的索引位置。遍历外层循环时,当s[i] !== s[j]
时,将j
指向新的一个不重复的字符索引位置。
/** * @method findMaxContinuousChar2 * @description 获取字符串中最多连续字符和次数 - 双指针 * @param s string * @returns IRes */ function findMaxContinuousChar2(s: string): IRes { // 定义结果初始值 const res: IRes = { char: '', length: 0, }; // 获取字符串长度 const len = s.length; // 临界点判断 if (len === 0) return res; // 定义指针j,指向每一个不重复的字符 // 初始时,执行索引0位置字符 let j = 0; // 使用临时变量,记录连续字符长度 let tmpMaxContinuousCharLenth = 0; for (let i = 0; i < len; i++) { // 二者相同 if (s[i] === s[j]) { tmpMaxContinuousCharLenth++; } // 不同或者是已经到了最后一位 if (s[i] !== s[j] || i === len - 1) { // 说明已经字符不同了,则计算当前重复的字符s[j]的长度 if (tmpMaxContinuousCharLenth > res.length) { res.length = tmpMaxContinuousCharLenth; // 注意s[j]记录的是每次的不重复字符初始值 res.char = s[j]; } // 这里是为了处理,当i指向了最后一个索引位置len - 1时,再执行i--操作会造成死循环 if (i < len - 1) { // 比对完成后,将索引j指向当前的最新一个字符 j = i; // 从当前位置重新开始遍历,外层循环要执行i++,所以这里后退一下 i--; } // 重置操作,将标记数量重置为0 tmpMaxContinuousCharLenth = 0; } } // 返回记过 return res; }
功能测试:
const s3: string = 'abbcccddddeeeeedcba'; const s4: string = 'aabbbbbbbb'; const res3 = findMaxContinuousChar2(s3); const res4 = findMaxContinuousChar2(s4); console.log(res3); // {char: 'e', length: 5} console.log(res4); // {char: 'b', length: 8}
同样,都是满足需求的。
算法复杂度:
- 空间复杂度: 临时变量tmpMaxContinuousCharLenth的声明只声明了一次,不随字符串
s
长度变化,复杂度为O(1)O(1)O(1)。
- 时间复杂度:只有一层for循环,复杂度为O(n)O(n)O(n)肯定是无疑了!