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

0%