[编程题]压缩算法

腾讯后端校招题目

链接：https://www.nowcoder.com/questionTerminal/c27561e5b7e0441493adb9a54071888d

来源：牛客网

热度指数：9198时间限制：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

First Try

2020-10-08

其实就是类似js里面的flattern array的操作，但是这是字符串，需要一个字符一个字符的扫描过去。遇到[号表示开始新的征程，遇到]表示可以退回上一层，然后使用相同的index进行追踪，直到完成整个字符串。一开始以为根本不需要|标记，但如果考虑到重复次数可能是100次这种三个数字的，不使用正则表达式的话还是需要通过|来进行标记了。

扫了一眼题解，有的人是先扫描完一遍字符找到所有标记之后再进行处理的，感觉还是现在这种一次扫描的更高端一些。

txt = input().strip()
 
def unpack(txt, lft):
    rv = ''
    while lft < len(txt):
        if txt[lft] == '[':
            t = lft
            while txt[lft] != "|":
                lft += 1
            times = int(txt[t + 1: lft])
            lft, content = unpack(txt, lft + 1)
            rv += times * content
        elif txt[lft] ==']':
            return lft + 1, rv
        else:
            rv += txt[lft]
            lft += 1
    return lft, rv
_, rv = unpack(txt, 0)
print(rv)

[编程题]压缩算法​

First Try​

[编程题]压缩算法

First Try