前言
本系列文章为《程序员面试金典》刷题笔记。
题目位置:字符串压缩 题集:程序员面试金典
题目
字符串压缩。利用字符重复出现的次数,编写一种方法,实现基本的字符串压缩功能。比如,字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短,则返回原先的字符串。你可以假设字符串中只包含大小写英文字母(a至z)。
示例1:
输入:"aabcccccaaa"
输出:"a2b1c5a3"
示例2:
输入:"abbccd"
输出:"abbccd"
解释:"abbccd"压缩后为"a1b2c2d1",比原字符串长度更长。
提示:
字符串长度在[0, 50000]范围内。
思路
字符串长度也不算长,int
还是能存下的,遇到这种题目怎么着也得遍历一遍。我最直接的思路就是定义变量来记数,先保存第一个字符,长度初始化为1。
count := 1
res :=string(S[0])
从第一个字符开始遍历
for i:=1;i<len(S);i++{
......
每次当前字符和前一个字符比较,只要和上一个不同就保存记录下来,然后计数器重置为1。
if S[i] == S[i-1]{
count ++
}else{
res = res + strconv.Itoa(count) + string(S[i])
count = 1
}
最后要注意边界,如果是字符串长度是0-2
个长度的,压缩了也没有意义,直接返回了。
if len(S)<= 2{
return S
}
完整代码见下一节代码(优化前)
看结果:
天啊,内存消耗是小了,但是速度也太慢了。算法已经这么简化了,要优化速度只能从go
语言的特性来了,大概率是追加字符串浪费了很多时间。
golang
里面的字符串都是不可变的,每次运算都会产生一个新的字符串,所以会产生很多临时的无用的字符串,不仅没有用,还会给 gc 带来额外的负担,所以性能比较差
这里引入到bytes.Buffer
类型,可以当成可变字符使用,对内存的增长也有优化,如果能预估字符串的长度,还可以用 buffer.Grow()
接口来设置 capacity
(容量)
用法举例:
var buffer bytes.Buffer
buffer.WriteString(hello)
buffer.WriteString(",")
buffer.WriteString(world)
_ = buffer.String()
代码见下一节,优化后。
棒极了,写完提交github睡觉。
代码
优化
Go
func compressString(S string) string {
if len(S)<= 2{
return S
}
count := 1
res :=string(S[0])
for i:=1;i<len(S);i++{
if S[i] == S[i-1]{
count ++
}else{
res = res + strconv.Itoa(count) + string(S[i])
count = 1
}
}
res = res + strconv.Itoa(count)
if len(res) < len(S){
return res
}else{
return S
}
}
优化后
Go
func compressString(S string) string {
if len(S)<= 2{
return S
}
count := 1
var res bytes.Buffer
res.WriteString(string(S[0]))
for i:=1;i<len(S);i++{
if S[i] == S[i-1]{
count ++
}else{
res.WriteString(strconv.Itoa(count))
res.WriteString(string(S[i]))
count = 1
}
}
res.WriteString( strconv.Itoa(count) )
resStr := res.String()
if len(resStr) < len(S){
return resStr
}else{
return S
}
}