@Author：Runsen
@Date：2020/9/6

大四刷題拼offer系列，不拼不行啊。自己知道自己的數(shù)據(jù)結(jié)構(gòu)算法很菜。而且2020/9/6今晚還有騰訊的筆試，祝我好運(yùn)吧。自己知道成功的可能性很低，但還是刷下騰訊的算法題。

文章目錄

• 題目
• 第一種思路
• 第二種思路
• 第三種思路

題目

題目：小Q想要給他的朋友發(fā)送一個(gè)神秘字符串，但是他發(fā)現(xiàn)字符串的過(guò)于長(zhǎng)了，于是小Q發(fā)明了一種壓縮算法對(duì)字符串中重復(fù)的部分進(jìn)行了壓縮，對(duì)于字符串中連續(xù)的m個(gè)相同字符串S將會(huì)壓縮為[m|S](m為一個(gè)整數(shù)且1<=m<=100)，例如字符串ABCABCABC將會(huì)被壓縮為[3|ABC]，現(xiàn)在小Q的同學(xué)收到了小Q發(fā)送過(guò)來(lái)的字符串，你能幫助他進(jìn)行解壓縮么？

''' @Author： Runsen @WeChat：RunsenLiu @微信公眾號(hào)： Python之王 @CSDN： https://blog.csdn.net/weixin_44510615 @Github： https://github.com/MaoliRUNsen @Date： 2020/9/6輸出一個(gè)字符串，代表解壓后的字符串。輸入例子1: HG[3|B[2|CA]]F輸出例子1: HGBCACABCACABCACAF例子說(shuō)明1: HG[3|B[2|CA]]F?>HG[3|BCACA]F?>HGBCACABCACABCACAF '''

這道題看似很簡(jiǎn)單，自己看著明白，腦子想明白了，但是就是敲不出，每次運(yùn)行就是還有一個(gè)數(shù)據(jù)不合適，可能是內(nèi)存的原因。其實(shí)關(guān)鍵就是如何找到[,|,]的index。

第一種思路

我相信很多人都是和我一樣，直接找到直接遍歷，如果遇到了第一個(gè)]，就往會(huì)回遍歷尋找[,|。這里遍歷如果寫for循環(huán)就覺(jué)得很難讀懂，下面的代碼j就是[的index，k就是|的index，i就是]的index。然后就是用replace，記作字符串是不可變類型，只能用replace，還有一種方法就是新建一個(gè)字符串，但是空間內(nèi)存變大了。

if __name__=='__main__':s=input()i=0while(i<len(s)):if(s[i]==']'):j=ik=0while(s[j]!='['):if(s[j]=='|'):k=jj=j-1s1=s[j:i+1]num=int(s[j+1:k])sz=s[k+1:i]sz=sz*nums=s.replace(s1,sz,1)i=ji = i + 1print(s)

第二種思路

第二種思路還是遍歷，但是想法和上面的不相同，就是找到]的index，就是break，同時(shí)儲(chǔ)存前面的[的index，和|的index，這樣就不斷地進(jìn)行遞歸解碼，直到一個(gè)中括號(hào)都沒(méi)有。

def decode(s):i = 0x, y, z = -1, -1, -1while i < len(s):if s[i] == '[':x = ielif s[i] == '|':y = ielif s[i] == ']':z = ibreaki += 1if x != -1 and y != -1 and z != -1:times = int(s[x + 1:y]) # 次數(shù)sub = s[y + 1:z] # 子串decode_str = s[:x] + times * sub + s[z + 1:] # 解碼return decode(decode_str) # 遞歸解碼return s # 如果一個(gè)中括號(hào)都沒(méi)有，說(shuō)明沒(méi)有需要解碼的部分if __name__ == '__main__':s = input()print(decode(s))

第三種思路

第三種思路就是使用正則，我是看別人都代碼才知道的思路，通配符寫成r"\[(\d+)\|(\w+)\]"這里的\表示轉(zhuǎn)義的意思。search返回的結(jié)果是竟然可以通過(guò)span取值，這個(gè)是我學(xué)正則不知道的！！！！！！

import reline = input() pattern = r"\[(\d+)\|(\w+)\]" tmp = re.search(pattern, line) print(tmp) while tmp:l, r = tmp.span()[0], tmp.span()[1]cur = line[l:r]mid = cur.find("|")num = int(cur[1:mid])chs = cur[mid + 1:-1] * numline = line[:l] + chs + line[r:]tmp = re.search(pattern, line)print(tmp) print(line)HG[3|B[2|CA]]F <re.Match object; span=(6, 12), match='[2|CA]'> <re.Match object; span=(2, 11), match='[3|BCACA]'> None HGBCACABCACABCACAF

看了騰訊第一道的解壓字符串，就知道自己有多垃圾了。正因?yàn)樽约豪?#xff0c;才需要不斷地提高字自己的水平。

如果你想跟博主建立親密關(guān)系，可以關(guān)注博主，或者關(guān)注博主公眾號(hào)“Python之王”，了解一個(gè)非本科程序員是如何成長(zhǎng)的。
博主ID：潤(rùn)森（weixin_44510615），希望大家點(diǎn)贊、評(píng)論、收藏

總結(jié)

以上是生活随笔為你收集整理的为了OFFER | 腾讯2020校招后端《解压字符串》的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。