1078 字符串压缩与解压 (20 分)
1078 字符串压缩与解压 (20 分)
题意描述:
文本压缩有很多种方法,这里我们只考虑最简单的一种:把由相同字符组成的一个连续的片段用这个字符和片段中含有这个字符的个数来表示。例如 ccccc 就用 5c 来表示。如果字符没有重复,就原样输出。例如 aba 压缩后仍然是 aba。
解压方法就是反过来,把形如 5c 这样的表示恢复为 ccccc。
本题需要你根据压缩或解压的要求,对给定字符串进行处理。这里我们简单地假设原始字符串是完全由英文字母和空格组成的非空字符串。
输入格式:
输入第一行给出一个字符,如果是 C 就表示下面的字符串需要被压缩;如果是 D 就表示下面的字符串需要被解压。第二行给出需要被压缩或解压的不超过 1000 个字符的字符串,以回车结尾。题目保证字符重复个数在整型范围内,且输出文件不超过 1MB。
输出格式:
根据要求压缩或解压字符串,并在一行中输出结果。
输入样例 1:
C
TTTTThhiiiis isssss a tesssst CAaaa as
输出样例 1:
5T2h4is i5s a3 te4st CA3a as
输入样例 2:
D
5T2h4is i5s a3 te4st CA3a as10Z
输出样例 2:
TTTTThhiiiis isssss a tesssst CAaaa asZZZZZZZZZZ
解题思路:
Mara: 这不就是行程编码吗?
Jack:就是行程编码,没什么新鲜的。压缩的话,比较当前字符和前一个字符是否相等就好了,不相等就该压缩了,相等就把字符重复计数器 加一。对于最后一个字符没法比较的问题,我们可以在整个字符串后面加一字符让最后一个字符变成倒数第二个字符。把一个问题转换成我们已经解决过的问题就好了。
Mara: 你是不是做过这种题目,怎么想的这么细?
Jack: 可能做过,处理字符串的题目太多了。解压缩的话,应该很简单的,遇到连续的数字字符拼成一个整数,遇到下一个非数字字符就解压缩。
Mara: 没有别的做法了吗 ? 怎么感觉这种方法不够优雅 ?
Jack: (¦3」∠), 暂时还没想出来,可能正则匹配能做! 关键我不会呀,(¦3」∠)。
代码:
- Python Version:
def main():
mode = input()
string = input()
if mode == 'C':
print(encrypt(string))
elif mode == 'D':
print(decrypt(string))
def encrypt(string):
# 对一个字符串使用行程编码 加密
if len(string) <= 1:
return string
# 如果某字符串长度小于等于1,直接返回原字符串即可
else:
count = 1
answer = []
# count 记录当前的字符重复了多少次 ?
for index in range(1, len(string) + 1):
# 注意我们这里循环的次数,多加了一次,便于处理最后一个字符
pre = string[index - 1]
# 前面的字符
if index == len(string):
now = '#'
# 若pre 已经是最后一个字符,设置这个特殊的字符来处理最后一个字符
else:
now = string[index]
# 正常情况, string[index], string[index - 1]分别是now 和 pre
if now != pre:
# 旧的字符重复已经终止
if count > 1:
# 字符重复多于一次的
answer.extend(["{}{}".format(count, pre)])
else:
# 字符重复仅有一次的
answer.extend([pre])
count = 1
# 字符重复字数要重置
else:
count += 1
# 字符仍在重复
return ''.join(answer)
# 将所有字符的重复模式记录下来并拼接成一个字符串后返回
def decrypt(string):
# 解压缩某个被压缩的字符串
number = 0
answer = []
for index in range(len(string)):
if is_number(string[index]):
# 若是数字,就把数字拼接起来
number = number * 10 + int(string[index])
else:
# 遇到非数字,开始解压
if number == 0:
# 仅有一个字母的情况下
number = 1
answer.extend([number * string[index]])
number = 0
# 重置数字
return ''.join(answer)
# 返回结果
def is_number(x):
# 判断 x 是不是 数字字符
return x in '0123456789'
if __name__ == '__main__':
main()
易错点:
- 仅有一个字符的时候,不需写上数字。如
‘a’
不必写成‘1a’
。 - 压缩的时候如何处理最后一个字符要考虑清楚,如
‘Aaaaaaa’
以及‘a’
等。
总结:
and :
上一篇: 笔试题细节整理