前端知识体系

# 连续最多的字符

# 题目

给一个字符串，找出连续最多的字符，以及次数。
例如字符串 'aabbcccddeeee11223' 连续最多的是 e ，4 次。

# 传统方式

嵌套循环，找出每个字符的连续次数，并记录比较。

时间复杂度看似是 O(n^2)，因为是嵌套循环。 但实际上它的时间复杂度是 O(n)，因为循环中有跳转。

# 双指针

画图解释，参考视频讲解。

只有一次循环，时间复杂度是 O(n)

性能测试，发现两者时间消耗一样，循环次数也一样。

# 其他方式

这个题目网上还有其他的答案

  • 正则表达式 —— 正则表达式的效率非常低，可进行性能测试（代码 x-reg.ts ）
  • 使用数组累计各个字符串的长度，然后求出最大值 —— 增加空间复杂度，面试官不会喜欢

【注意】算法尽量用基础代码实现，尽量不要用现成的 API 或语法糖 —— 方便，但你不好直观判断时间复杂度

# 答案

上述两种方式（嵌套循环和双指针）都可以，参考 continuous-char.ts

interface IRes {
    char: string
    length: number
}

/**
 * 求连续最多的字符和次数（嵌套循环）
 * @param str str
 */
export function findContinuousChar1(str: string): IRes {
    const res: IRes = {
        char: '',
        length: 0
    }

    const length = str.length
    if (length === 0) return res

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

    // O(n)
    for (let i = 0; i < length; i++) {
        tempLength = 0 // 重置

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

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

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

                break
            }
        }
    }

    return res
}

/**
 * 求连续最多的字符和次数（双指针）
 * @param str str
 */
export function findContinuousChar2(str: string): IRes {
    const res: IRes = {
        char: '',
        length: 0
    }

    const length = str.length
    if (length === 0) return res

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

    // O(n)
    for (; i < length; i++) {
        if (str[i] === str[j]) {
            tempLength++
        }

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

            if (i < length - 1) {
                j = i // 让 j “追上” i
                i-- // 细节
            }
        }
    }

    return res
 }

// // 功能测试
// const str = 'aabbcccddeeee11223'
// console.info(findContinuousChar2(str))

// let str = ''
// for (let i = 0; i < 100 * 10000; i++) {
//     str += i.toString()
// }

// console.time('findContinuousChar1')
// findContinuousChar1(str)
// console.timeEnd('findContinuousChar1') // 219ms

// console.time('findContinuousChar2')
// findContinuousChar2(str)
// console.timeEnd('findContinuousChar2') // 228ms

# 单元测试

import { findContinuousChar1, findContinuousChar2 } from './continuous-char'

describe('连续字符和长度', () => {
    it('正常情况', () => {
        const str = 'aabbcccddeeee11223'
        const res = findContinuousChar1(str)
        expect(res).toEqual({ char: 'e', length: 4 })
    })
    it('空字符串', () => {
        const res = findContinuousChar1('')
        expect(res).toEqual({ char: '', length: 0 })
    })
    it('无连续字符', () => {
        const str = 'abc'
        const res = findContinuousChar1(str)
        expect(res).toEqual({ char: 'a', length: 1 })
    })
    it('全部都是连续字符', () => {
        const str = 'aaa'
        const res = findContinuousChar1(str)
        expect(res).toEqual({ char: 'a', length: 3 })
    })
})

# 划重点

  • 注意实际的时间复杂度，不要被代码所迷惑
  • 双指针的思路（常用于解决嵌套循环）

← 快速排序 →