【数据结构与算法】(14)：获取连续最多的字符和次数

经典算法题：给一个字符串，获取字符串中连续最多的字符及次数，下边就分别用 嵌套循环+跳步 和 双指针 的思路来实现。

一、问题示例

示例 1：

• 输入：Hello World
• 输出：{char: 'l', length: 2}

示例 2：

• 输入：www
• 输出：{char: 'w', length: 3}

二、代码演示

1. 嵌套循环 + 跳步

interface IRes {
  char: string
  length: number
}

// 求连续最多的字符和次数 嵌套循环 + 跳步

export function findContinuousChar1(str: string): IRes{
  const res: IRes = {
    char: '',
    length: 0
  }
  const len = str.length
  if (len === 0) return res

  let tempLen = 0 // 临时记录当前连续字符的长度

  for (let i = 0; i < len; i++) {
    tempLen = 0 // 重置

    for (let j = i; j < len; j++) {
      if (str[i] === str[j]) {
        tempLen ++
      }

      if (str[i] !== str[j] || j === len - 1) {
        // 不相等，或者已经到了最后一个元素，判断最大值
        if (tempLen > res.length) {
          res.char = str[i]
          res.length = tempLen
        }

        if (i < len - 1) {
          i = j - 1 // 跳步
        }

        break
      }
    }
  }

  return res
}

2. 双指针

interface IRes {
  char: string
  length: number
}

// 求连续最多的字符和次数 双指针
export function findContinuousChar2(str: string): IRes{
  const res: IRes = {
    char: '',
    length: 0
  }
  const len = str.length
  if (len === 0) return res

  let tempLen = 0 // 临时记录当前连续字符的长度

  let i = 0
  let j = 0

  for (; i < len; i++) {

    if (str[i] === str[j]) {
      tempLen ++
    }

    if (str[i] !== str[j] || i === len - 1) {
      // 不相等、或者 i 到了字符串的末尾
      if (tempLen > res.length) {
        res.char = str[j]
        res.length = tempLen
      }
      tempLen = 0 // 重置

      if (i < len - 1) {
        j = i // 让 j 追上 i
        i --
      }
    }
  }

  return res
}

三、单元测试

/*
* @description 连续字符 test
* */
import { findContinuousChar1, findContinuousChar2 } from '../continuous-char.ts'

describe('连续字符和长度 嵌套循环 跳步', () => {
  it('正常情况', () => {
    const str = 'Hello World'
    const res = findContinuousChar1(str)
    expect(res).toEqual({
      char: 'l',
      length: 2,
    })
  })
  it('空字符串', () => {
    const res = findContinuousChar1('')
    expect(res).toEqual({
      char: '',
      length: 0,
    })
  })
  it('无连续字符', () => {
    const str = 'world'
    const res = findContinuousChar1(str)
    expect(res).toEqual({
      char: 'w',
      length: 1,
    })
  })
  it('全部都是连续字符', () => {
    const str = 'www'
    const res = findContinuousChar1(str)
    expect(res).toEqual({
      char: 'w',
      length: 3,
    })
  })
})

describe('连续字符和长度 双指针', () => {
  it('正常情况', () => {
    const str = 'Hello World'
    const res = findContinuousChar2(str)
    expect(res).toEqual({
      char: 'l',
      length: 2,
    })
  })
  it('空字符串', () => {
    const res = findContinuousChar2('')
    expect(res).toEqual({
      char: '',
      length: 0,
    })
  })
  it('无连续字符', () => {
    const str = 'world'
    const res = findContinuousChar2(str)
    expect(res).toEqual({
      char: 'w',
      length: 1,
    })
  })
  it('全部都是连续字符', () => {
    const str = 'www'
    const res = findContinuousChar2(str)
    expect(res).toEqual({
      char: 'w',
      length: 3,
    })
  })
})

四、性能测试

let str = ''
for (let i = 0; i < 100 * 10000; i++) {
  str += `${i}`
}

console.time('findContinuousChar1')
console.log(findContinuousChar1(str))
console.timeEnd('findContinuousChar1')

console.time('findContinuousChar2')
console.log(findContinuousChar2(str))
console.timeEnd('findContinuousChar2')

运行


findContinuousChar1 run time： 0

---

findContinuousChar2 run time： 0

---

五、算法复杂度

方法	时间复杂度
嵌套循环 + 跳步	O(nn)
for 双指针	O(n)

---

欢迎访问：天问博客

本文作者： Tiven
发布时间： 2023-07-22
最后更新： 2023-07-24
本文标题： 【数据结构与算法】(14)：获取连续最多的字符和次数
本文链接： https://www.tiven.cn/p/c085dbd0/
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！