首页 > 试题广场 >

压缩算法

[编程题]压缩算法

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

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

示例1

输入

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

输出

"HGBCACABCACABCACAF"

说明

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

备注:

S的长度<=1000;
S仅包含大写字母、[、]、|;
解压后的字符串长度不超过100000;
压缩递归层数不超过10层;

算法知识视频讲解

Python

xiemaoxian

python + 正则

import re
class Solution:
    def compress(self , s ):
        # write code here
        while re.findall(r'\[(\d+)\|([a-zA-Z]+)\]',s):
            s = re.sub(r'\[(\d+)\|([a-zA-Z]+)\]',lambda match:match.group(2)*int(match.group(1)),s)
        return s

发表于 2021-07-15 20:29:13 回复(1)

Python

勤奋的鳄鱼在对齐目标

# 构造一个链表就好做了，用的是python，希望能帮助需要的同学

class Solution:

class StackNode:
def __init__(self, number=0, stack=None, last_node=None):
self.number = number
self.stack = stack
self.last_node = last_node

def compress(self, string):
c, ans, number = '', '', 0
current_node = self.StackNode(stack=[])
for c in string:
if c == '[':
new_node = self.StackNode(stack=[], last_node=current_node)
current_node = new_node
elif '0' <= c <= '9':
current_node.number = current_node.number * 10 + int(c)
elif c == ']':
current_node.last_node.stack += (current_node.number * current_node.stack)
current_node = current_node.last_node
elif 'A' <= c <= 'Z':
current_node.stack.append(c)
ans = ''
for e in current_node.stack:
ans += e
return ans

发表于 2021-03-30 10:45:13 回复(2)