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

大四刷题拼offer系列，不拼不行啊。自己知道自己的数据结构算法很菜。而且2020/9/6今晚还有腾讯的笔试，祝我好运吧。自己知道成功的可能性很低，但还是刷下腾讯的算法题。

题目

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

'''
@Author： Runsen
@WeChat：RunsenLiu 
@微信公众号： Python之王
@CSDN： https://blog.csdn.net/weixin_44510615
@Github： https://github.com/MaoliRUNsen
@Date： 2020/9/6

输出一个字符串，代表解压后的字符串。

输入例子1:
HG[3|B[2|CA]]F

输出例子1:
HGBCACABCACABCACAF

例子说明1:
HG[3|B[2|CA]]F−>HG[3|BCACA]F−>HGBCACABCACABCACAF
'''

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

这道题看似很简单，自己看着明白，脑子想明白了，但是就是敲不出，每次运行就是还有一个数据不合适，可能是内存的原因。其实关键就是如何找到[,|,]的index。

第一种思路

我相信很多人都是和我一样，直接找到直接遍历，如果遇到了第一个]，就往会回遍历寻找[,|。这里遍历如果写for循环就觉得很难读懂，下面的代码j就是[的index，k就是|的index，i就是]的index。然后就是用replace，记作字符串是不可变类型，只能用replace，还有一种方法就是新建一个字符串，但是空间内存变大了。

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

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

第二种思路

第二种思路还是遍历，但是想法和上面的不相同，就是找到]的index，就是break，同时储存前面的[的index，和|的index，这样就不断地进行递归解码，直到一个中括号都没有。

def decode(s): i = 0 x, y, z = -1, -1, -1 while i < len(s): if s[i] == '[': x = i elif s[i] == '|': y = i elif s[i] == ']': z = i break i += 1 if x != -1 and y != -1 and z != -1: times = int(s[x + 1:y])  # 次数 sub = s[y + 1:z]  # 子串 decode_str = s[:x] + times * sub + s[z + 1:]  # 解码 return decode(decode_str)  # 递归解码 return s  # 如果一个中括号都没有，说明没有需要解码的部分


if __name__ == '__main__': s = input() print(decode(s))

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
 

第三种思路

第三种思路就是使用正则，我是看别人都代码才知道的思路，通配符写成r"\[(\d+)\|(\w+)\]"这里的\表示转义的意思。search返回的结果是竟然可以通过span取值，这个是我学正则不知道的！！！！！！

import re

line = 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] * num line = 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

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
 

看了腾讯第一道的解压字符串，就知道自己有多垃圾了。正因为自己垃圾，才需要不断地提高字自己的水平。

如果你想跟博主建立亲密关系，可以关注博主，或者关注博主公众号“Python之王”，了解一个非本科程序员是如何成长的。
博主ID：润森（weixin_44510615），希望大家点赞、评论、收藏

文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。

原文链接：maoli.blog.csdn.net/article/details/108428416