12、字符串中连续最多的字符以及次数

字符串中连续最多的字符以及次数

• 如, 输入 ‘ abbcccddeeee1234’ , 计算得到：

• 连续最多的字符是 ‘e’ , 4 次

传统思路

• 嵌套循环，找出每个字符的连接次数，并记录
• 看似时间复杂度是O(n^2)
• 但实际时间复杂度是多少？——O(n),因为有“跳步”

代码实现

export interface IRes {
  curChar: string
  length: number
}

export function findContinousChar1 (str:string):IRes {
  const res:IRes = {
    curChar: '',
    length: 0
  }

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

  let charLength = 0 // 记录当前连续长度最大的字符长度
  // O(n)
  for (let i = 0; i < len; i++) {
    charLength = 0 // 重置

    for (let j = i; j < len; j++) {
      if (str[i] === str[j]) {
        charLength++ // 连续相同 +1
      }

      if (str[i] !== str[j] || j === len -1) {
        // 不相等或者已经到了最后一个字符
        if (charLength > res.length) {
          res.curChar = str[i]
          res.length = charLength
        }

        if (i < len -1) {
          i = j -1 // 跳步，让i直接跳到j的当前位置，继续下一步的循环
        }

        break
      }      
    }
  }

  return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

功能测试

const str = "abbcccddeeee1234"
const res = findContinousChar1(str)
console.info(res)
1
2
3

打印结果

{ curChar: 'e', length: 4 }
1

单元测试

describe('查找连续字符最大长度',() => {
  it('正常情况', () => {
    const str = "abbcccddeeee1234"
    const res = findContinousChar1(str)
    expect(res).toEqual({ curChar: 'e', length: 4 })

  })

  it('空字符串', () => {
    const res = findContinousChar1('')
    expect(res).toEqual({ curChar: '', length: 0 })
  })

  it('非连续字符串', () => {
    const str = "abc"
    const res = findContinousChar1(str)
    expect(res).toEqual({ curChar: 'a', length: 1 })
  })

  it('连续字符串', () => {
    const str = "aaa"
    const res = findContinousChar1(str)
    expect(res).toEqual({ curChar: 'a', length: 3 })
  })
})
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

优化——双指针思想

• 定义指针i 和 j 。j不动， i 就行移动
• 如果i 和 j的值一直相等，则i继续移动
• 直到i和j的值不相等，记录处理，让j追上i。继续新一轮的计算

代码实现

export function findContinousChar2 (str:string):IRes {
  const res:IRes = {
    curChar: '',
    length: 0
  }

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

  let charLength = 0 // 记录当前连续长度最大的字符长度

  let i = 0
  let j = 0

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

  if (str[i] !== str[j] || i === len -1) {
    // 不相等或者已经到了最后一个字符
    if (res.length < charLength) {
      res.curChar = str[j]
      res.length = charLength
    }

    charLength = 0 // 重置

    if (i < len -1) {
      j = i // 让j “追上” i，开始新一轮的计算
      i-- // 细节，让i和j保存新一轮的同步
    }
  }
  
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

功能测试

const str = "abbcccddeeee1234"
const res = findContinousChar2(str)
console.info(res)
1
2
3

打印结果

{ curChar: 'e', length: 4 }
1

单元测试

describe('查找连续字符最大长度',() => {
  it('正常情况', () => {
    const str = "abbcccddeeee1234"
    const res = findContinousChar2(str)
    expect(res).toEqual({ curChar: 'e', length: 4 })

  })

  it('空字符串', () => {
    const res = findContinousChar2('')
    expect(res).toEqual({ curChar: '', length: 0 })
  })

  it('非连续字符串', () => {
    const str = "abc"
    const res = findContinousChar2(str)
    expect(res).toEqual({ curChar: 'a', length: 1 })
  })

  it('连续字符串', () => {
    const str = "aaa"
    const res = findContinousChar2(str)
    expect(res).toEqual({ curChar: 'a', length: 3 })
  })
})
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

性能比较

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

console.time('findContinousChar1')
findContinousChar1(str1)
console.timeEnd('findContinousChar1')

console.time('findContinousChar2')
findContinousChar2(str1)
console.timeEnd('findContinousChar2')
1
2
3
4
5
6
7
8
9
10
11
12

打印结果

findContinousChar1: 128.688ms
findContinousChar2: 120.392ms
1
2

两个函数执行时间相差无几，由此可见这里的嵌套循环的复杂度确实是O(n) 而不是 O(n ^ 2), 不过双指针在代码层次可以较清晰的计算出时间复杂度。

总结

• 要注意实际复杂度，不要被代码表面迷惑
• 双指针常用于解决嵌套循环
• 算法题慎用正则表达式（实际工作可以用）