最近看见一道算法题,本着见题解题的学习心态解决了它,由于目前正在研究正则表达式,所以就从正则的方向入手了:
题目如下:输入N个整数,中间用空格隔开,求出异或和为0的最长连续子串。要求输出子串的长度、子串在输入的数组中的起始位置和结束位置。如果不存在这样的子串则输出-1.
代码如下:
import rex = input('请输入')#将输入的整数去掉空格并分别存入列表备用,用来最后比对子串的位置。z = re.split(r'\s+',x)#定义空列表用来存放所有符合异或和为0的连续子串lis = []while 1:#首先查找是否存在符合条件的子串 res1 = re.search(r'((\d+)\s+\2\s*)+',x) if not res1:break#如果存在的话就把它保存到列表中 lis.append(res1.group().strip())#并且删除该子串,以便进行后续查找。 x = re.sub(r'((\d+)\s+\2\s*)+','',x,1)if lis: #对查找结果进行筛选,把列表中每个子串转再换成列表 for i in range(len(lis)): lis[i] = re.split(r'\s+',lis[i])#创建字典,key为每个子串长度,value为每个子串的列表形式 dic = {len(lis[i]):lis[i] for i in range(len(lis))}#求出最长的子串 max_str = dic[max(dic)] a = len(max_str) for i in range(len(z)-a+1): if z[i:i+a] == max_str: b = i+1 break c = b+a-1 print(a,b,c)else: print('-1')
我自己测试一千多条数据是OK的,欢迎各位学长指教。