0%

leetcode day2

此题来自LeetCode,系中等难度的算法题

题目

给定一个字符串,找出不含有重复字符的最长子串的长度。

示例:

给定 "abcabcbb" ,没有重复字符的最长子串是 "abc" ,那么长度就是3。

给定 "bbbbb" ,最长的子串就是 "b" ,长度是1。

给定 "pwwkew" ,最长子串是 "wke" ,长度是3。请注意答案必须是一个子串,"pwke" 是 子序列 而不是子串。

解答

暴力法

一开始我使用的是完全的暴力法,首先定义一个函数用于查找一个字符串中是否含有重复字符(两重循环),再在主函数中将一个字符串的每个子串都遍历一遍重复字符函数(两重循环)

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
func lengthOfLongestSubstring(s string) int {
var sLen int
for i := 0; i < len(s); i++ {
for j := i + 1; j <= len(s); j++ {
if hasRepeatChar(s[i:j]) {
slen := j - i
if sLen < slen {
sLen = slen
}
}
}
}
return sLen
}

func notHasRepeatChar(str string) bool {
for i := 0; i < len(str); i++ {
for j := 0; j < len(str); j++ {
if str[i] == str[j] && i != j {
return false
}
}
}
return true
}

这种暴力法的时间复杂度貌似是O(n^4),解析大小为32k的文本花了约32秒-.-

接下来我们来对该算法进行优化:

初步优化

首先,检测重复字符的算法过于复杂,我们可以使用一个set集合将遍历到的字符储存起来,当出现重复时,则说明有重复字符

1
2
3
4
5
6
7
8
9
10
11
12
13
type Set map[byte]struct{}

func isUnique(str string) bool {
set := make(Set)
for i := 0; i < len(str); i++ {
if _, ok := set[str[i]]; ok {
return false
} else {
set[str[i]] = struct{}{}
}
}
return true
}

emm…运行后慢了整整十倍,不应该啊,此问题待以后解决…

再次优化

其次,当查找子串时,可以当子串检测到重复字符时终止此次循环:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func lengthOfLongestSubstring(s string) int {
var sLen int
for i := 0; i < len(s); i++ {
for j := i + 1; j <= len(s); j++ {
if isUnique(s[i:j]) {
slen := j - i
if sLen < slen {
sLen = slen
}
} else {
break
}
}
}
return sLen
}

跑完花了6秒,比起一开始好了许多,但如果用notHasRepeatChar函数的话只需2秒-.-

进一步

如果要更进一步的优化的话,可以采取滑动窗口机制:我们使用 Set将字符存储在当前窗口[i,j)(最初j=i)中.然后我们向右侧滑动索引j,如果它不在Set中,就继续滑动j.直到s[j]已经存在于Set中
此时,我们找到的没有重复字符的最长子字符串将会以索引i开头.如果我们对所有的i这样做,就可以得到答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func lengthOfLongestSubstring(s string) int {
sLen:=len(s)
set:=make(Set)
var ans,i,j int
for i<sLen&&j<sLen{
if _,ok:=set[s[j]];!ok{
set[s[j]]=struct{}{}
j++
if ans<j-i{
ans=j-i
}
}else{
delete(set,s[i])
i++
}
}
return ans
}

只花了0.02秒!!!

极限优化

如果s[j]在[i,j)范围内有与j’重复的字符,我们不需要逐渐增加i.我们可以直接跳过[i,j′]范围内的所有元素,并将i变为j’+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}

func lengthOfLongestSubstring(s string) int {
sLen := len(s)
set := make(map[byte]int)
var ans, i, j int
for ; j < sLen; j++ {
if _, ok := set[s[j]]; ok {
if i < set[s[j]] {
i = set[s[j]] + 1
}
}
ans = max(ans, j-i+1)
set[s[j]] = j
}
return ans
}

0.01秒…

小结

在这次练习中,我了解到了字符串的基本搜索方法,以及滑动窗口方法的使用,不过可能连算法的入门都算不上233