测试之家

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

肖军 · 2021年07月13日 · 最后由 MarvinWu 回复于 2021年07月20日 · 6254 次阅读

压缩的字母规则是，连续相同的字母串压缩成：连续的个数 +[字母串]。如 aaa,压缩成:3[a]；amamam 压缩成 3[am]。
请实现解压缩字符串功能。实现程序语言不限制。完成时间两个小时，过程不能看手机，不能切屏。
自测样例，输入：3[k] 2[am] 预期输出：kkkamam
输入：2[k3[am]] 预期输出：kamamamkamamam

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

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))
3 个赞
共收到 26 条回复 时间 点赞
尼古拉斯赵四 #1 · 2021年07月13日

挺有意思的题目，根据自己的思路也写了下，就是不知道执行怎么样

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))
肖军 #2 · 2021年07月13日 Author
对 尼古拉斯赵四 回复

比我的强

肖军 #3 · 2021年07月13日 Author
对 尼古拉斯赵四 回复

你的思路还是不错的，但是字母压缩还有一种情况：m3[k] 2[am] 。这种情况还需要优化考虑一下

海棠不是朵朵 #4 · 2021年07月13日 
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

还不快一键三连？🤗

肖军 #5 · 2021年07月13日 Author
对 海棠不是朵朵 回复

很厉害呀！可是 30[k] 呢 ，测试不通过。还得优化一下

海棠不是朵朵 #6 · 2021年07月13日
对 肖军 回复

可以改，但没必要

MarvinWu #8 · 2021年07月14日

看代码风格 4 楼就赢了😂

Ouroboros #9 · 2021年07月14日

综合楼上的一些思路，做了个 java 版。

public static String myUnzip(String testString){
        StringBuilder strb = new StringBuilder();
        int multi = 0;
        //倍数栈，记录每个子串的倍数
        Deque<Integer> stack_multi= new LinkedList<>();
        //子串栈，记录子串
        Deque<String> stack_strb= new LinkedList<>();
        char[] c=testString.toCharArray();
        for (int i = 0; i < c.length; i++) {
            if(c[i] >= '0' && c[i] <= '9'){//如果遇到数字，就记录到倍数multi，如果遇到连续的数字，就进位组合成更高位数的数字
                multi = multi * 10 + Integer.parseInt(c[i] + "");
            }else if(c[i]=='['){//如果遇到左中括号，倍数进倍数栈，同时把multi置为0，用来记录下一个子串的倍数,当前子串清空
                stack_multi.push(multi);
                stack_strb.push(strb.toString());//记录[]内与倍数倍子串同级的串，例如acd3[b]中的acd
                multi = 0;
                strb = new StringBuilder();
            }else if(c[i]==']'){//如果遇到右中括号，根据当前倍数拼接当前子串和同级的串，生成更外层[]中的子串
                StringBuilder tmp = new StringBuilder();
                int cur_multi = stack_multi.pop();//当前倍数
                for(int j = 0; j < cur_multi; j++){
                    tmp.append(strb);
                }
                strb = new StringBuilder(stack_strb.pop() + tmp);
            }else{//非数字和[]的情况，拼接
                strb.append(c[i]);
            }
        }
        return strb.toString();
    }
matt gong #18 · 2021年07月14日 1 个赞

这个可以转换成算术：
3[a] -> aaa 理解成 3*'a'
3[k] 2[am] -> kkkamam 理解成 3*'k' + 2*'am'
2[k3[am]] -> kamamamkamamam 理解成 2*('k'+3*'am')

解算术， 一般就是匹配， 入栈出栈。

如果把这个题目反过来， 看着难度会大增。

Ouroboros #11 · 2021年07月14日

递归应该也能做

落羽之梦 #12 · 2021年07月14日

我想知道反过来怎么解

cloudwind #13 · 2021年07月14日

是时候刷下 LeetCode 了

haoheiyo #14 · 2021年07月14日 
# 按照自己想法写的，比较low，轻喷
def unzip(zip_data):
    y_index=zip_data.find(']') 
    if y_index==-1: #如果没有]跳出
        return zip_data
    else:
        tmp_data=zip_data[:y_index]
        z_index=len(tmp_data)-tmp_data[::-1].find('[')-1
        num=""
        for i in tmp_data[z_index-1::-1]:
            if i.isdigit():
                num=i+num
            else:
                break
        z_data=tmp_data[:z_index-len(num)]
        do_data=int(num)*tmp_data[z_index+1:y_index]
        y_data=zip_data[y_index+1:]
        ret_data=z_data+do_data+y_data
        return unzip(ret_data)
天邪泪 #15 · 2021年07月14日

测试这么卷的吗

落羽之梦 #11 · 2021年07月14日

@matt gong 按你的想法写，感觉写的好渣

def unzip(zip_data):
    word = ''
    for i,j in enumerate(zip_data):
        if j == "[":
            word = word + "*("
        elif j == "]":
            word = word + ")"
        elif j.isalpha():
            if not (zip_data[i-1].isalpha() or zip_data[i+1].isalpha()):
                if zip_data[i+1].isdigit():
                    word = word + '"' + j + '"+'
                else:
                    word = word + '"' + j + '"'
            elif not zip_data[i-1].isalpha():
                word = word + '"' + j
            elif not zip_data[i+1].isalpha():
                if zip_data[i+1].isdigit():
                    word = word + j + '"+'
                else:
                    word = word + j + '"'
            else:
                word = word + j
        else:
            word = word + j
    return eval(word)
云中一只猫 #17 · 2021年07月14日

目测用 “栈” 来搞是可以的;

c = []
e = ''
for i in list('3[am]2[bn]'):
    if i == ']':
        d = ''
        for value in reversed(c):
            if value == '[':
                c.pop()
                beishu = c.pop()
                e = e + int(beishu) * d if d != '' else e+int(beishu) * e
                break
            else:
                d = c.pop() + d
    else:
        c.append(i)
骷髅弓箭手 #18 · 2021年07月14日 
class Solution(object):
    def __init__(self, this_str: str):
        self.this_str = this_str

    def unzip(self):
        return_str = ''
        cal_str = ''
        while len(self.this_str) > 0:
            cur_word = self.this_str[0]
            self.this_str = self.this_str[1:]
            # 如果是字母
            if 90 >= ord(cur_word) >= 65 or 122 >= ord(cur_word) >= 97:
                return_str += cur_word
            # 如果是[则进入递归，返回后防止同层级有多个压缩，需要重置倍率值
            elif ord(cur_word) == 91:
                z = self.unzip()
                return_str += int(cal_str)*z
                cal_str = ''
            # 如果是]则返回中括号内的内容
            elif ord(cur_word) == 93:
                return return_str
            # 如果是数字，则存入计算字符串中
            elif 57 >= ord(cur_word) >= 48:
                cal_str += cur_word

        return return_str
matt gong #19 · 2021年07月15日

尝试写一下， 思路：编历字符串， 把其中数字、字母往栈里面丢， 不用管'['。 匹配到']', 取出栈中字符直到遇到数字，扩展后 (即数字 * 字母) 再放回栈。这样遍历完成后， 栈中放的就是所有扩展后的字母串， 取出来拼接好。

public class UnzipWords {

    public static String unZipWords(String words){

        /**
         * 思路：编历字符串， 把其中数字、字母往栈里面丢， 不用管'['。 匹配到']', 取出栈中字符直到遇到数字，扩展后(即数字 * 字母)再放回栈。
         * 这样遍历完成后， 栈中放的就是所有扩展后的字母串， 取出来拼接好。
         *
         */
        Deque<String> deque = new LinkedList<>();
        for(char w : words.toCharArray()){
            if(w==']'){

                StringBuilder de_word = new StringBuilder();
                while(!deque.isEmpty()){
                    String word = deque.pop();
                    if(word.length()==1 && Character.isDigit(word.charAt(0))){
                        int f = Integer.valueOf(word);
                        StringBuilder temp = new StringBuilder();
                        for(int i=1;i<=f;i++){
                            temp.append(de_word);
                        }

                        deque.push(temp.toString());
                        break;

                    }else{
                        de_word.insert(0,word);
                    }
                }

            }else if(w!='['){
                deque.push(w+"");
            }

        }

        StringBuilder sb = new StringBuilder();
        while(!deque.isEmpty()){
            sb.insert(0,deque.pop());
        }
        System.out.println(words + " -> " +sb.toString());
        return sb.toString();

    }


    public static void main(String args[]){
        unZipWords("3[k]4[x]");
        unZipWords("2[k3[am]]");
        unZipWords("x5[a4[c]5[d]m]");
        unZipWords("3[K]");

    }
}

示例：

3[k]4[x] -> kkkxxxx
2[k3[am]] -> kamamamkamamam
x5[a4[c]5[d]m] -> xaccccdddddmaccccdddddmaccccdddddmaccccdddddmaccccdddddm
3[K] -> KKK
dxx4396 #20 · 2021年07月15日 
def parse(data: str):
    data_list = []
    for i in data:
        if i != ']':
            data_list.append(i)
        else:
            word, num = '', ''
            while data_list[-1] != '[':
                if 'A' <= data_list[-1] <= 'z':
                    word = data_list[-1] + word
                    data_list.pop()
            else:
                data_list.pop()
                while data_list[-1] in '0123456789':
                    num = data_list[-1] + num
                    data_list.pop()
                    if not data_list:
                        break
            data_list.append(int(num) * word)
    return ''.join(i for i in data_list)
YueChen #21 · 2021年07月15日 2 个赞

大佬们都开始拼算法了，写个其他解法，转成计算题😂 

def unzip(data:str):
    import re
    pattern = r"(\D(?=[0-9]))|" \
              r"([0-9](?=\[))"

    def replace(matched):
        value = ''
        if matched.group(1):
            value += matched.group(1) + "+"
        if matched.group(2):
            value += matched.group(2) + "*"
        return value

    data = re.sub(pattern, replace, data)  # 转成数学计算
    data = re.sub("[a-zA-Z]+", lambda x: f"'{x.group(0)}'", data)  # 给字母加引号
    return eval(data.replace("[", "(").replace("]", ")"))  # 中括号替换


if __name__ == '__main__':

    str_list = ["5[a]", "k3[k]2[am]", "2[[k10[am]]]", "x8[a1[pp]5[d]]"]
    for s in str_list:
        print(unzip(s))
endno3 #22 · 2021年07月15日 1 个赞

改了下四楼大佬的算法，考虑了数字是多位的情况

def unzip(data):
    stack = []
    for e in data:
        # 开始弹出
        if e == ']':
            tmp_str = ''
            while stack:
                item = stack.pop()
                if item == '[':
                    continue
                elif item.isdigit():
                    n = int(item)
                    # 处理所有的数字
                    loop = 1
                    while stack and stack[-1].isdigit():
                        n = int(stack.pop())*10**loop + n
                        loop += 1
                    tmp_str = n * tmp_str
                    break
                # 如果是字母，则字符串相加
                else:
                    tmp_str = item + tmp_str
            stack.append(tmp_str)
        else:
            stack.append(e)
    return "".join(stack)

print(unzip('101[k]'))
print(unzip('2[k10[am]]'))
print(unzip('2[am]'))
print(unzip('2[k]2[am]'))

kkkkkkkkkkkkkkkkkkkk
kamamamamamamamamamamkamamamamamamamamamam
amam
kkamam

干饭狂人 #25 · 2021年07月20日 
def flat(s):
    def fla(mat):
        cnt, s = mat.groups()
        return int(cnt) * s
    s = re.sub("(?:(\d+)\[(\w*)\])", fla, s)
    if re.search("(?:(\d+)\[(\w*)\])", s):
        return flat(s)
    return s

备注：非算法，能简单解决问题的才是最有用的
群内大佬：atx uiautomator2 自动化群-->南京-DiN 解法

26楼 已删除
MarvinWu #27 · 2021年07月20日

这题最简单的解法不就是栈吗，正则才是炫技吧
就 25 楼的答案，不上机测试有多少人能看明白结果对还是不对😂

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册。