一道算法题：求出异或和为零的最长连续子串

刘玉平发布于2019-07-30 18:00 / 2554人阅读

摘要：最近看见一道算法题，本着见题解题的学习心态解决了它，由于目前正在研究正则表达式，所以就从正则的方向入手了题目如下输入个整数，中间用空格隔开，求出异或和为的最长连续子串。要求输出子串的长度子串在输入的数组中的起始位置和结束位置。

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

输入N个整数，中间用空格隔开，求出异或和为0的最长连续子串。要求输出子串的长度、子串在输入的数组中的起始位置和结束位置。如果不存在这样的子串则输出-1.

代码如下：

import re
x = input("请输入")
#将输入的整数去掉空格并分别存入列表备用，用来最后比对子串的位置。
z = re.split(r"s+",x)
#定义空列表用来存放所有符合异或和为0的连续子串
lis = []
while 1:
#首先查找是否存在符合条件的子串
    res1 = re.search(r"((d+)s+2s*)+",x)
    if not res1:break
#如果存在的话就把它保存到列表中
    lis.append(res1.group().strip())
#并且删除该子串，以便进行后续查找。
    x = re.sub(r"((d+)s+2s*)+","",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的，欢迎各位学长指教。

云服务器 GPU服务器最大连续子串算法异或和最长公共子串 java最长相同子串

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/42557.html

网易2018校招前端笔试题解析

摘要：现在有一个给定的字符串中每个字符代表小易的某个砖块的颜色。例如那么小易有六种排列的结果其中只有和满足最多只有一对不同颜色的相邻砖块。输入描述输入包括一行四个整数以空格分割输出描述输出一个整数表示小易最多能独立生活多少天。前言：注意，网易校招笔试在牛客网进行，在这里使用js完成算法题时，不要写一个function() {}就认为完成了题目，那样通过率是0%(题主就是这样，估计笔试挂了。...

Baoyuan 2019-08-21 11:56 评论0 收藏0
JS算法题之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一个字符，判断正负符号，若是英文直接返回，若数字则不取。回文数题目描述判断一个整数是否是回文数。回文数是指正序从左向右和倒序从右向左读都是一样的整数。 JS算法题之leetcode(1~10) 前言一直以来，前端开发的知识储备在数据结构以及算法层面是有所暂缺的，可能归根于我们的前端开发的业务性质，但是我认为任何的编程岗位都离不开数据结构以及算法。因此，我作为...

SoapEye 2019-08-26 10:44 评论0 收藏0
【C语言操作符多图详解】——“讲述你所未知的操作符细节”

摘要：今天小玄为大家带来语言的操作符相关的讲解，希望大家能通过这篇文章对相关操作符有更加深入的理解。操作符的两个操作数必须为整数。操作符的优先级操作符的结合性是否控制求值顺序。两个相邻的操作符先执行哪个取决于他们的优先级。今天小玄为大家带来C语言的操作符相关的讲解，希望大家能通过...

iliyaku 2021-09-27 13:36 评论0 收藏0
由三道 LeetCode 题目简单了解一下位运算

摘要：使用位运算数组只出现一次数字的数组得到最低的有效位，即两个数不同的那一位看完上面的解法，我脑海中只有问号的存在，啥意思啊下面就让我们简单了解一下位运算并解析一下这三道题目。另，负数按补码形式参加按位与运算。你可做过这几道题？在面试的准备过程中，刷算法题算是必修课，当然我也不例外。某天，我刷到了一道神奇的题目： # 136. 只出现一次的数字给定一个非空整数数组，除了某个元素只出现一次以外...

daydream 2019-05-21 11:41 评论0 收藏0
由三道 LeetCode 题目简单了解一下位运算

摘要：简单介绍一下位运算异或运算异或逻辑的关系是当不同时，输出当相同时，输出。另，负数按补码形式参加按位与运算。使一个数的最低位为零，可以表示为。，截止到这儿，三道题目中使用的位运算介绍完毕，那么这里我们插入一下的详细题解。你可做过这几道题？在面试的准备过程中，刷算法题算是必修课，当然我也不例外。某天，我刷到了一道神奇的题目： # 136. 只出现一次的数字给定一个非空整数数组，除了某个元素只...

刘明 2019-05-22 14:21 评论0 收藏0