百词斩算法面试题--字符串压缩-阿里云开发者社区

开发者社区> 负债程序猿> 正文

百词斩算法面试题--字符串压缩

简介: 输入aabcccccaaa,写个算法输出a2b1c5a3
+关注继续查看

题目忘了,大概是说,输入aabcccccaaa,写个算法输出a2b1c5a3

实现:

@Slf4j
public class DepressForBaiCiZhan {
    public static String doDepress(String str) {
        //字符串为空直接返回
        if ("".equals(str)) return str;
        StringBuilder buffer = new StringBuilder();
        //用第n个字符去和第n+1个字符对比
        char c = str.charAt(0);
        //记录字符出现次数,默认为1
        int repeat = 1;
        for (int i = 1; i < str.length(); i++) {
            if (c == str.charAt(i)) {
                //如果第n个字符和第n+1个字符相等,则出现次数+1
                repeat++;
            } else {
                //如果第n个字符和第n+1个字符不相等,则拼接在字符串后面
                buffer.append(c).append(repeat);
                //拼接完后重置当前字符串
                c = str.charAt(i);
                //重置字符出现次数
                repeat = 1;
            }
        }
        //最后一组在for循环里是没有拼接的,这里再来拼接
        return buffer.append(c).append(repeat).toString();
    }

    public static void main(String[] args) {
        log.info("我爱百词斩=======>{}",doDepress("我爱百词斩"));//我爱百词斩=======>我1爱1百1词1斩1
        log.info("我爱百百词词斩斩==>{}",doDepress("我爱百百词词斩斩"));//我爱百百词词斩斩==>我1爱1百2词2斩2
        log.info("aabcccccaaa===>{}",doDepress("aabcccccaaa"));//aabcccccaaa===>a2b1c5a3
    }
}

解析:


这个题最开始我理解错了,最开始是利用hashMap键的唯一性,导致输出是a5b1c5(这个算法在这里传送门),然而人家要的是a2b1c5a3,后面改了下算法,也是动态字符串拼接,需要维护一个当前对比字符,一个字符出现次数,用第n个字符去和第n+1个字符对比,相等则出现次数+1,不相等则拼接在字符串后面,注意一点就是,因为我这里是先拼接再重置当前字符串和出现次数,所以最后一组字符是没拼接的,需要在返回前单独拼接。


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
什么是机器学习| 学习笔记
快速学习什么是机器学习
6 0
总结与回顾| 学习笔记
快速学习总结与回顾
4 0
无监督学习算法(上)| 学习笔记
快速学习无监督学习算法(上)
5 0
Elasticsearch最佳实践建议
本文主要是总结了Elasticsearch从安装、配置到应用程序使用、运维、性能优化的最佳实践的建议,希望能对于Elasticsearch的开发和运维提供一些帮助。
7 0
有监督学习算法(下)| 学习笔记
快速学习有监督学习算法(下)
3 0
有监督学习算法(上)| 学习笔记
快速学习有监督学习算法(上)
3 0
无监督学习算法(下)| 学习笔记
快速学习无监督学习算法(下)
8 0
云计算大数据及人工智能| 学习笔记
快速学习云计算大数据及人工智能
6 0
总结与回顾(1)| 学习笔记
快速学习总结与回顾(1)
8 0
其他学习算法| 学习笔记
快速学习其他学习算法
5 0
+关注
负债程序猿
知道的越多,不知道的越多
118
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载