某大厂的机试题，解压压缩的字母串。

波哥的IT人生 2021-10-20

333

压缩的字母规则是，连续相同的字母串压缩成：连续的个数 +[字母串]。如 aaa,压缩成:3[a]；amamam 压缩成 3[am]。

请实现解压缩字符串功能。实现程序语言不限制。完成时间两个小时，过程不能看手机，不能切屏。
自测样例，输入：3[k] 2[am] 预期输出：kkkamam
输入：2[k3[am]] 预期输出：kamamamkamamam

虽然我做了一下，结果调试没有问题，但是和最终结果还是有出入。大家可以自己做做。看是不是只有我觉得这个题目难，还是我太 low 了。
以下是我的实现，基于 python3.6：

思路1:

import re
from string import digits

def untar_word(word,num):
    '''
    解压字符
    :param word:
    :param num:
    :return:
    '''
    re_word = ''
    for i in range(0,num):
        re_word = re_word + word
    return re_word

def get_number(word):
    '''
    提取数值list
    :param word:
    :return:
    '''
    return re.findall(r'\d+',word)

def del_digit(word):
    '''
    去除字符串中的数值
    :param word:
    :return:
    '''
    return word.translate(str.maketrans('', '', digits))

def deal_word(word):
    '''
    处理word
    :param word:
    :return:
    '''
    list_number = get_number(word)
    new_words = del_digit(word)
    deal_times = 0
    a = -1 #记录处理的第几个压缩字符串
    leve = 0
    while True:
        if deal_times == len(list_number):
            break
        else:
            for i in range(0,len(new_words)):
                if new_words[i] ==  '[':
                    a = a + 1
                    leve = leve + 1
                    mark = i
                if new_words[i] == ']':
                    num = int(list_number[a])
                    word = new_words[(mark + 1):i]
                    new_words = new_words[0:mark] + untar_word(word,num) + new_words[i+1:]
                    deal_times = deal_times + 1
                    if leve > 1:
                        a = -1
                    break
    return new_words

if __name__ == "__main__":
    tar_word1 = '3[k]2[am]'
    tar_word2 = '2[k3[am]]'
    print(deal_word(tar_word1))
    print(deal_word(tar_word2))

思路2:

def deal_word(words):
    word_list = re.findall(r'[a-z|A-Z]+', words)
    for i in word_list:
         words = words.replace(i, "'{}'".format(i))
    special_word = re.findall(r"('\w+')\d+", words)  # 处理字母后跟数字的情况
    if special_word:
        words = words.replace(special_word[0], '['+special_word[0]+']+')
    words = words.replace('[', '*[').replace(']', ']+').strip('*').strip('+')
    while ']+]' in words:
        words = words.replace(']+]', ']]')
    words = eval(words)
    words = [''.join(w) for w in words]
    return ''.join(words)


if __name__ == "__main__":
    tar_word1 = '3[k]2[am]'
    tar_word2 = '2[k3[am]]'
    tar_word3 = '2[2[k3[am]]]'
    print(deal_word(tar_word1))
    print(deal_word(tar_word2))
    print(deal_word(tar_word3))

思路3:

def unzip(zip_data):
    stack = []
    for z in zip_data:
        if z == "]":  # 开始弹出
            tmp_result = ""
            while stack:
                item = stack.pop()

                if item == "[":
                    continue

                if item.isdigit():
                    tmp_result = int(item) * tmp_result[::-1]
                    break
                else:
                    tmp_result += item
            stack.append(tmp_result)
        else:
            stack.append(z)
    return "".join(stack)

测试样例

print(unzip("3[k]"))
print(unzip("3[k]4[x]"))
print(unzip("2[am]"))
print(unzip("2[k3[am]]"))
print(unzip("x5[a4[c]5[d]m]"))

kkk
kkkxxxx
amam
kmamamakmamama
xaccccdddddmaccccdddddmaccccdddddmaccccdddddmaccccdddddm

关注

绝对干货的公众号

某大厂的机试题，解压压缩的字母串。

评论