前言
本系列文章为《程序员面试金典》刷题笔记。
题目位置：字符串压缩
题集：程序员面试金典
题目
字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串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 } }
