【LeetCode】压缩字符串 Java 题解
题目描述
给你一个字符数组 chars ,请使用下述算法压缩:
从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 :
如果这一组长度为 1 ,则将字符追加到 s 中。否则,需要向 s 追加字符,后跟这一组的长度。压缩后得到的字符串 s 不应该直接返回 ,需要转储到字符数组 chars 中。需要注意的是,如果组长度为 10 或 10 以上,则在 chars 数组中会被拆分为多个字符。
请在 修改完输入数组后 ,返回该数组的新长度。
你必须设计并实现一个只使用常量额外空间的算法来解决此问题。
复制代码
思路分析
今天的每日一题,依旧是字符串问题,根据题意,压缩算法已经给出,我们需要根据压缩算法实现代码。
首先,使用朴素解法,将字符串完成压缩,使用 StringBuilder 提升效率。压缩完成之后,在对原数组进行复写,返回结果。
但是题目要求只使用常量额外空间,因此,朴素解法不符合要求。采用双指针的方式优化代码。
代码
朴素解法
复制代码
双指针解法
复制代码
总结
朴素解法时间复杂度是 O(n),空间复杂度是 O(n)
双指针解法时间复杂度是 O(n),空间复杂度是 O(1)
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/ae14d3b9de3472f0a5425b6c3】。文章转载请联系作者。
评论