发布于2020-03-17 11:00 阅读(2080) 评论(0) 点赞(17) 收藏(4)
题目描述:
字符串压缩。利用字符重复出现的次数,编写一种方法,实现基本的字符串压缩功能。比如,字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短,则返回原先的字符串。你可以假设字符串中只包含大小写英文字母(a至z)。
示例1:
输入:"aabcccccaaa"
输出:"a2b1c5a3"
示例2:
输入:"abbccd"
输出:"abbccd"
解释:“abbccd"压缩后为"a1b2c2d1”,比原字符串长度更长。
提示:字符串长度在[0, 50000]范围内。
解题思路1:
代码1:
class Solution(object):
def compressString(self, S):
if len(S) == 0: # 当 S = ""时
return S
j = 0
countj = 1
temp = []
temp2 = []
for i in range(len(S)-1):
if S[i] == S[i+1]:
countj += 1
else:
temp.append(countj)
j += 1
countj = 1
temp.append(countj) # 依次统计相同字符出现的次数
k = 0
for i in range(len(S)-1):
if S[i] != S[i+1]:
k = i+1
temp2.append(S[i])
temp2.append(S[k]) # 依次去重相邻字符
temp3 = []
for i in range(len(temp)):
temp3.append(temp2[i]+str(temp[i]))
temp3 = ''.join(list(temp3)) # 将列表转换为字符串
return temp3 if len(temp3) < len(S) else S
s = Solution()
S = "aabcccccaaa"
print(s.compressString(S))
解题思路2:
字符串压缩的方式就是将连续出现的相同字符按照 字符 + 出现次数 压缩。如果压缩后的字符串长度变短,则返回压缩后的字符串,否则保留原来的字符串,所以我们模拟这个过程构建字符串即可。
代码2:
来源于:力扣官网
class Solution:
def compressString(self, S: str) -> str:
if not S:
return ""
ch = S[0]
ans = ''
cnt = 0
for c in S:
if c == ch:
cnt += 1
else:
ans += ch + str(cnt)
ch = c
cnt = 1
ans += ch + str(cnt)
return ans if len(ans) < len(S) else S
s = Solution()
S = "aabcccccaaa"
print(s.compressString(S))
题目来源:
面试题 01.06. 字符串压缩
原文链接:https://blog.csdn.net/weixin_43283397/article/details/104893254
作者:编程gogogo
链接:https://www.pythonheidong.com/blog/article/262625/5488934c3a9e1d2f98f5/
来源:python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 python黑洞网 All Rights Reserved 版权所有,并保留所有权利。 京ICP备18063182号-1
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!