前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >边做算法边学go语言之程序员面试金典面试题 01.06. 字符串压缩

边做算法边学go语言之程序员面试金典面试题 01.06. 字符串压缩

作者头像
机智的程序员小熊
发布2020-03-25 11:30:03
6450
发布2020-03-25 11:30:03
举报
文章被收录于专栏:技术面面观

前言

本系列文章为《程序员面试金典》刷题笔记。

题目位置:https://leetcode-cn.com/problems/compress-string-lcci/ 题集:https://leetcode-cn.com/problemset/lcci/ 代码位置:https://coding3min.com/pzqu/LeetCode

题目

字符串压缩。利用字符重复出现的次数,编写一种方法,实现基本的字符串压缩功能。比如,字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短,则返回原先的字符串。你可以假设字符串中只包含大小写英文字母(a至z)。

示例1:

代码语言:javascript
复制
 输入:"aabcccccaaa"
 输出:"a2b1c5a3"

示例2:

代码语言:javascript
复制
 输入:"abbccd"
 输出:"abbccd"
 解释:"abbccd"压缩后为"a1b2c2d1",比原字符串长度更长。

提示:

代码语言:javascript
复制
字符串长度在[0, 50000]范围内。
思路

字符串长度也不算长,int还是能存下的,遇到这种题目怎么着也得遍历一遍。我最直接的思路就是定义变量来记数,先保存第一个字符,长度初始化为1。

代码语言:javascript
复制
count := 1
res :=string(S[0])

从第一个字符开始遍历

代码语言:javascript
复制
for i:=1;i<len(S);i++{
    ......

每次当前字符和前一个字符比较,只要和上一个不同就保存记录下来,然后计数器重置为1。

代码语言:javascript
复制
if S[i] == S[i-1]{
    count ++
}else{
    res = res + strconv.Itoa(count) + string(S[i])
    count = 1
 }

最后要注意边界,如果是字符串长度是0-2个长度的,压缩了也没有意义,直接返回了。

代码语言:javascript
复制
 if len(S)<= 2{
        return S
    }

完整代码见下一节代码(优化前)

看结果:

天啊,内存消耗是小了,但是速度也太慢了。算法已经这么简化了,要优化速度只能从go语言的特性来了,大概率是追加字符串浪费了很多时间。

golang 里面的字符串都是不可变的,每次运算都会产生一个新的字符串,所以会产生很多临时的无用的字符串,不仅没有用,还会给 gc 带来额外的负担,所以性能比较差

这里引入到bytes.Buffer类型,可以当成可变字符使用,对内存的增长也有优化,如果能预估字符串的长度,还可以用 buffer.Grow()接口来设置 capacity(容量)

用法举例:

代码语言:javascript
复制
 var buffer bytes.Buffer
        buffer.WriteString(hello)
        buffer.WriteString(",")
        buffer.WriteString(world)
        _ = buffer.String()

代码见下一节,优化后。

棒极了,写完提交github睡觉。

代码

优化 Go

代码语言:javascript
复制
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

代码语言:javascript
复制
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
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-03-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 机智的程序员小熊 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
  • 思路
  • 代码
相关产品与服务
文件存储
文件存储(Cloud File Storage,CFS)为您提供安全可靠、可扩展的共享文件存储服务。文件存储可与腾讯云服务器、容器服务、批量计算等服务搭配使用,为多个计算节点提供容量和性能可弹性扩展的高性能共享存储。腾讯云文件存储的管理界面简单、易使用,可实现对现有应用的无缝集成;按实际用量付费,为您节约成本,简化 IT 运维工作。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档