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

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

上题目


给你一个字符串 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)肯定是无疑了!


相关文章
|
6月前
|
存储 编译器 C语言
函数指针&&数组指针&&数组传参的本质&&字符指针(进阶篇)
函数指针&&数组指针&&数组传参的本质&&字符指针(进阶篇)
127 0
|
6月前
|
存储 C++
使用字符指针变量和字符数组的比较
使用字符指针变量和字符数组的比较
63 0
C4.
|
6月前
|
存储 程序员 C语言
C语言中如何通过指针引用字符串
C语言中如何通过指针引用字符串
C4.
70 0
|
6月前
|
C语言
C语言----字符数组&&指针
C语言----字符数组&&指针
49 0
|
6月前
【每日一题Day301】LC2337移动片段得到字符串 | 双指针 计分
【每日一题Day301】LC2337移动片段得到字符串 | 双指针 计分
51 0
|
6月前
|
算法 C语言
通过指针引用字符串
通过指针引用字符串
73 1
|
2月前
|
存储 人工智能 C语言
C语言程序设计核心详解 第八章 指针超详细讲解_指针变量_二维数组指针_指向字符串指针
本文详细讲解了C语言中的指针,包括指针变量的定义与引用、指向数组及字符串的指针变量等。首先介绍了指针变量的基本概念和定义格式,随后通过多个示例展示了如何使用指针变量来操作普通变量、数组和字符串。文章还深入探讨了指向函数的指针变量以及指针数组的概念,并解释了空指针的意义和使用场景。通过丰富的代码示例和图形化展示,帮助读者更好地理解和掌握C语言中的指针知识。
|
6月前
|
存储 C语言
字符指针变量与字符数组的比较
字符指针变量与字符数组的比较
51 3
|
6月前
|
存储 C语言
字符指针作为函数参数
字符指针作为函数参数
61 2
|
6月前
DAY-2 | 哈希表、指针与区间划分:字符种数统计问题
```markdown ## 题干 [牛客网链接](https://www.nowcoder.com/practice/eb94f6a5b2ba49c6ac72d40b5ce95f50) ## 题解 1. **查表法(哈希表)**:利用数组标记出现过的 ASCII 值小于127的字符,首次出现计数,重复则忽略。 2. **指针与区间划分(回头法)**:遍历字符串,对每个字符检查其前所有字符是否重复,重复则不计数。 ## 方法总结 - 哈希表在去重问题中非常实用,可多做相关练习。 - 使用`continue`时注意避免死循环,确保循环变量会改变。 - 多回顾此类问题以巩固理解。 ```
44 2