博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
一道算法题:求出异或和为零的最长连续子串
阅读量:5946 次
发布时间:2019-06-19

本文共 875 字,大约阅读时间需要 2 分钟。

最近看见一道算法题,本着见题解题的学习心态解决了它,由于目前正在研究正则表达式,所以就从正则的方向入手了:

题目如下:

输入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的,欢迎各位学长指教。

转载地址:http://rqbxx.baihongyu.com/

你可能感兴趣的文章
poj 1742 roads
查看>>
笔记:学习JavaWeb开发第二课
查看>>
Go实现FastCgi Proxy Client 系列(一)
查看>>
不能用array === null 来判断数组为空!!!
查看>>
关于对象的存在和销毁
查看>>
如何移动CleanMyMac激活码到另一台Mac上
查看>>
Parallels Desktop12推出 新增Parallels Toolbox
查看>>
正则表达式验证身份证格式是否正确
查看>>
Firebird(全功能的,免维护的数据库,能够管理多个独立的数据库) V2.1.3 英文特别版...
查看>>
Spring框架简介
查看>>
xml格式文件解析
查看>>
ios百度地图-路径规划
查看>>
Python高效编程技巧
查看>>
配置Eclipse使用maven构建项目默认JDK为1.8
查看>>
博客分享:程序员提升自我必备
查看>>
【细品架构10/100】架构由术至道的转变(1)
查看>>
网页显示405 Method not allowed问题
查看>>
jsp内置对象以及jsp动作
查看>>
Struts上路_09-数据类型转换
查看>>
定制CentOS
查看>>