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

发表于 更新于 分类于
字符串中连续出现最多的字符，以及次数

题目如下

  • 字符串中连续出现最多的字符，以及次数

补充

  • 正则表达式——效率非常低，慎用
  • 累计各个元素的连续长度，最后求最大值——徒增空间复杂度
  • 算法题尽量使用“低级”代码，慎用语法糖或者高级API

思路如下

  • 传统思路
    • 嵌套循环，找出每个字符的连接次数，并记录
    • 看似时间复杂度是O(n^2)
    • 但实际时间复杂度是多少——O(n) 因为有 “跳步”
  • 双指针
    • 定义指针i和j。j不动，i继续移动
    • 如果i和j的值一直相等，则i继续移动
    • 直到i和j的值不相等，记录处理，让j追上i。继续第一步
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/**
 * @description 连续字符
 * @author sola-grj
 */

interface IRes {
    char: string
    length: number
}

/**
 * 求连续最多的字符和次数（嵌套循环）
 * @param str str
 */
export function findContinuousChar1(str: string): IRes {
  const res = {
    char:'',
    length:0
  }
  
  const length = str.length
  if(length === 0) return res
  
  let tempLength = 0
  
  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
        }
        // 跳步 此时导致整个的时间复杂度为O(n)
        if(i < length - 1){
          i = j - 1
        }
        
        break
      }
    }
  }
  return res
}

/**
 * 求连续最多的字符和次数（双指针）
 * @param str str
 */
export function findContinuousChar2(str: string): IRes {
  const res = {
    char:'',
    length:0
  }
  
  const length = str.length
  if(length === 0) return res
  
  let tempLength = 0
  let i = 0
  let j = 0
  for(;i < length;i++){
    if(str[j] === str[i]){
      tempLength++
    }
    
    if(str[j] !== str[i] || i === length - 1){
      if(tempLength > res.length){
        res.char = str[j]
        res.length = tempLength
      }
      tempLength = 0
      
      if(i < length - 1){
        j = i
        i--
      }
    }
  }
  return res
}

// 性能测试
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

单元测试

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
/**
 * @description 连续字符 test
 * @author sola-grj
 */

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 })
    })
})