【数据结构与算法】(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')

<div> <button style='padding: 10px 20px; color: #00b1fb;' class='rotate-btn' onclick='run()'>运行</button> <br> <b>findContinuousChar1 run time：</b> <span style='color: red;' class='box1-ms'>0</span> <hr> <b>findContinuousChar2 run time：</b> <span style='color: red;' class='box2-ms'>0</span> <hr> </div> <script> function findContinuousChar1(str){ const res = { 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

}

// 求连续最多的字符和次数 双指针 function findContinuousChar2(str){ const res = { 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

}

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

let s1 = performance.now()
findContinuousChar1(str)
document.querySelector('.box1-ms').innerText = performance.now() - s1 + ' ms'

let s2 = performance.now()
findContinuousChar2(str)
document.querySelector('.box2-ms').innerText = performance.now() - s2 + ' ms'

} </script>

五、算法复杂度

欢迎访问：天问博客