首页 > 试题广场 >

压缩算法

[编程题]压缩算法

热度指数：10816 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小Q想要给他的朋友发送一个神秘字符串，但是他发现字符串的过于长了，于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩，对于字符串中连续的m个相同字符串S将会压缩为[m|S](m为一个整数且1<=m<=100)，例如字符串ABCABCABC将会被压缩为[3|ABC]，现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？

输入描述:

输入第一行包含一个字符串s，代表压缩后的字符串。
S的长度<=1000;
S仅包含大写字母、[、]、|;
解压后的字符串长度不超过100000;
压缩递归层数不超过10层;

输出描述:

输出一个字符串，代表解压后的字符串。

示例1

输入

HG[3|B[2|CA]]F

输出

HGBCACABCACABCACAF

说明

HG[3|B[2|CA]]F−>HG[3|BCACA]F−>HGBCACABCACABCACAF

算法知识视频讲解

Python

myyhdmz

Python版本的双栈法：

s = input()
numStk, strStk = [], []
ans = ""
cnt = 0
for i in range(len(s)):
    if s[i].isdigit():
        cnt = cnt * 10 + int(s[i])
    elif s[i] == '[':
        strStk.append(ans)
        ans = ""
    elif s[i] == '|':
        numStk.append(cnt)
        cnt = 0
    elif s[i] == ']':
        k = numStk.pop()
        tmp = strStk.pop()
        for _ in range(k):
            tmp += ans
        ans = tmp
    else:
        ans += s[i]
print(ans)

编辑于 2020-11-26 19:23:44 回复(0)

Python

牛客155955564号

def solution(s):  while s.__contains__(']'):  r = s.index(']')
        t = s[:r+1][::-1]
        l = r - t.index('[')
        repeatS = s[l+1:r]
        rsp = repeatS.split('|')
        s = s.replace("["+repeatS+"]", rsp[1]*int(rsp[0])) return s  if __name__ == '__main__':  s = input() print(solution(s)) # HG[3|B[2|CA]]F # HG[3|BCACA]F

发表于 2020-09-04 11:22:05 回复(0)

Python

3s_wyf2020

#倒着找呗！

cod=input()
i=0
while i<len(cod):
    a=cod.find(']')
    if a != -1:
        for j in range(a,-1,-1):
            if cod[j]=='[':
                b=j
                break
        c1=cod[b+1:a].split('|')
        c2=int(c1[0])*c1[1]
        cod=cod.replace(cod[b:a+1],c2)
        i+=1
    else:
        break
print (cod)

发表于 2020-08-12 01:48:59 回复(0)