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


字数:1.1k 阅读时长:5分钟 阅读:85

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

数据结构与算法 · 获取连续最多的字符和次数

一、问题示例

示例 1:

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

示例 2:

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

二、代码演示

  1. 嵌套循环 + 跳步
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
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
}
  1. 双指针

数据结构与算法 · 双指针

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

三、单元测试

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

/*
* @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,
})
})
})

四、性能测试

1
2
3
4
5
6
7
8
9
10
11
12
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 许可协议进行许可。转载请注明出处!
欢迎留言,提问 ^_^
个人邮箱: tw.email@qq.com
notification icon
博客有更新,将会发送通知给您!