经典算法题：给一个字符串，获取字符串中连续最多的字符及次数，下边就分别用 嵌套循环+跳步 和 双指针 的思路来实现。
#一、问题示例
示例 1：
- 输入：
Hello World - 输出：
{char: 'l', length: 2}
示例 2：
- 输入：
www - 输出：
{char: 'w', length: 3}
#二、代码演示
- 嵌套循环 + 跳步
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
}
- 双指针
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')
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'
}
#五、算法复杂度
| 方法 | 时间复杂度 |
|---|---|
| 嵌套循环 + 跳步 | O(nn) |
| for 双指针 | O(n) |
欢迎访问：天问博客
目录