双指针的妙用 - 字符串中连续最多的字符和连续次数

简介: 双指针的妙用 - 字符串中连续最多的字符和连续次数

上题目


给你一个字符串 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依次指向第一个abcd的索引位置。遍历外层循环时,当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)肯定是无疑了!


相关文章
C4.
|
2天前
|
存储 程序员 C语言
C语言中如何通过指针引用字符串
C语言中如何通过指针引用字符串
C4.
21 0
|
7月前
|
C语言
C语言之字符串的连接使用指针和调用函数两种方法
C语言之字符串的连接使用指针和调用函数两种方法
210 0
|
9月前
|
存储 C语言
C语言之指针(指针数组以及指针的指针和字符串)
C语言之指针(指针数组以及指针的指针和字符串)
72 0
|
2天前
利用两个指针的差值求字符串长度
利用两个指针的差值求字符串长度
21 0
|
10月前
|
人工智能 大数据 BI
指针及其应用2——数组指针、字符串指针
指针及其应用2——数组指针、字符串指针
|
5月前
|
C++
LeetCode | 双法妙解压缩字符串【遍历统计 + 双指针】
LeetCode | 双法妙解压缩字符串【遍历统计 + 双指针】
28 0
|
8月前
指针-字符串替换
指针-字符串替换
|
8月前
|
存储 人工智能 C语言
8.4 【C语言】通过指针引用字符串
8.4 【C语言】通过指针引用字符串
75 0
|
10月前
|
C语言
C语言:使用指针使字符串逆序
题目: 链接:字符逆序__牛客网 来源:牛客网 将一个字符串str的内容颠倒过来,并输出。
219 0

热门文章

最新文章