前言：
现时兄弟们对“java字符压缩算法”大概比较关怀，兄弟们都想要知道一些“java字符压缩算法”的相关文章。那么小编同时在网络上收集了一些关于“java字符压缩算法””的相关内容，希望各位老铁们能喜欢，各位老铁们一起来了解一下吧！题目难度: 简单
原题链接[1]
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串 aabcccccaaa 会变为 a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a 至 z）。
示例 1:
输入："aabcccccaaa" 输出："a2b1c5a3"
示例 2:
输入："abbccd" 输出："abbccd" 解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。
提示：
字符串长度在[0, 50000]范围内。
题目思考需要维护哪些变量?解决方案思路分析题目, 我们只需要维护当前字符 cur 和其出现次数 cnt 即可首先判断原始字符串是否为空, 不为空的话就可以将当前字符初始化为头一个字符了, 同时 cnt 初始化为 1如果遍历到的字符和当前字符不同, 就把当前字符连带其次数追加到结果中, 同时重置 cur 和 cnt; 相同则 cur 不变, cnt 加 1特别注意遍历结束后, 也需要将当前字符及其次数追加到结果中最后若结果长度没有更短, 就用原始字符串复杂度时间复杂度 O(N): 需要遍历字符串一遍空间复杂度 O(1): 只使用了几个变量代码
class Solution: def compressString(self, S: str) -> str: # 简单模拟, 注意判断S是否为空, 不为空的话初始化cnt和cur为1和S[0] # 注意循环结束后一定要加当前cnt, 注意比较前后字符串长度 if not S: return '' res = '' cnt = 1 cur = S[0] for c in S[1:]: if c != cur: res += cur + str(cnt) cnt = 1 cur = c else: cnt += 1 res += cur + str(cnt) return res if len(res) < len(S) else S参考资料
[1]
原题链接:
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
标签： #java字符压缩算法
