一道算法題：求出異或和為零的最長連續(xù)子串

劉玉平發(fā)布于2019-07-30 18:00 / 2726人閱讀

摘要：最近看見一道算法題，本著見題解題的學(xué)習(xí)心態(tài)解決了它，由于目前正在研究正則表達式，所以就從正則的方向入手了題目如下輸入個整數(shù)，中間用空格隔開，求出異或和為的最長連續(xù)子串。要求輸出子串的長度子串在輸入的數(shù)組中的起始位置和結(jié)束位置。

最近看見一道算法題，本著見題解題的學(xué)習(xí)心態(tài)解決了它，由于目前正在研究正則表達式，所以就從正則的方向入手了：
題目如下：

輸入N個整數(shù)，中間用空格隔開，求出異或和為0的最長連續(xù)子串。要求輸出子串的長度、子串在輸入的數(shù)組中的起始位置和結(jié)束位置。如果不存在這樣的子串則輸出-1.

代碼如下：

import re
x = input("請輸入")
#將輸入的整數(shù)去掉空格并分別存入列表備用，用來最后比對子串的位置。
z = re.split(r"s+",x)
#定義空列表用來存放所有符合異或和為0的連續(xù)子串
lis = []
while 1:
#首先查找是否存在符合條件的子串
    res1 = re.search(r"((d+)s+2s*)+",x)
    if not res1:break
#如果存在的話就把它保存到列表中
    lis.append(res1.group().strip())
#并且刪除該子串，以便進行后續(xù)查找。
    x = re.sub(r"((d+)s+2s*)+","",x,1)
if lis: 
#對查找結(jié)果進行篩選，把列表中每個子串轉(zhuǎn)再換成列表   
    for i in range(len(lis)):
        lis[i] = re.split(r"s+",lis[i])
#創(chuàng)建字典，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")

我自己測試一千多條數(shù)據(jù)是OK的，歡迎各位學(xué)長指教。

云服務(wù)器 GPU云服務(wù)器最大連續(xù)子串算法異或和最長公共子串 java最長相同子串

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/42557.html

相關(guān)文章

網(wǎng)易2018校招前端筆試題解析

摘要：現(xiàn)在有一個給定的字符串中每個字符代表小易的某個磚塊的顏色。例如那么小易有六種排列的結(jié)果其中只有和滿足最多只有一對不同顏色的相鄰磚塊。輸入描述輸入包括一行四個整數(shù)以空格分割輸出描述輸出一個整數(shù)表示小易最多能獨立生活多少天。前言：注意，網(wǎng)易校招筆試在?？途W(wǎng)進行，在這里使用js完成算法題時，不要寫一個function() {}就認為完成了題目，那樣通過率是0%(題主就是這樣，估計筆試掛了。...

Baoyuan 2019-08-21 11:56 評論0 收藏0
JS算法題之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一個字符，判斷正負符號，若是英文直接返回，若數(shù)字則不取。回文數(shù)題目描述判斷一個整數(shù)是否是回文數(shù)。回文數(shù)是指正序從左向右和倒序從右向左讀都是一樣的整數(shù)。 JS算法題之leetcode(1~10) 前言一直以來，前端開發(fā)的知識儲備在數(shù)據(jù)結(jié)構(gòu)以及算法層面是有所暫缺的，可能歸根于我們的前端開發(fā)的業(yè)務(wù)性質(zhì)，但是我認為任何的編程崗位都離不開數(shù)據(jù)結(jié)構(gòu)以及算法。因此，我作為...

SoapEye 2019-08-26 10:44 評論0 收藏0
【C語言操作符多圖詳解】——“講述你所未知的操作符細節(jié)”

摘要：今天小玄為大家?guī)碚Z言的操作符相關(guān)的講解，希望大家能通過這篇文章對相關(guān)操作符有更加深入的理解。操作符的兩個操作數(shù)必須為整數(shù)。操作符的優(yōu)先級操作符的結(jié)合性是否控制求值順序。兩個相鄰的操作符先執(zhí)行哪個取決于他們的優(yōu)先級。 ????????今天小玄為大家?guī)鞢語言的操作符相關(guān)的講解，希望大家能通過...

iliyaku 2021-09-27 13:36 評論0 收藏0
由三道 LeetCode 題目簡單了解一下位運算

摘要：使用位運算數(shù)組只出現(xiàn)一次數(shù)字的數(shù)組得到最低的有效位，即兩個數(shù)不同的那一位看完上面的解法，我腦海中只有問號的存在，啥意思啊下面就讓我們簡單了解一下位運算并解析一下這三道題目。另，負數(shù)按補碼形式參加按位與運算。你可做過這幾道題？在面試的準備過程中，刷算法題算是必修課，當(dāng)然我也不例外。某天，我刷到了一道神奇的題目： # 136. 只出現(xiàn)一次的數(shù)字給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外...

daydream 2019-05-21 11:41 評論0 收藏0
由三道 LeetCode 題目簡單了解一下位運算

摘要：簡單介紹一下位運算異或運算異或邏輯的關(guān)系是當(dāng)不同時，輸出當(dāng)相同時，輸出。另，負數(shù)按補碼形式參加按位與運算。使一個數(shù)的最低位為零，可以表示為。，截止到這兒，三道題目中使用的位運算介紹完畢，那么這里我們插入一下的詳細題解。你可做過這幾道題？在面試的準備過程中，刷算法題算是必修課，當(dāng)然我也不例外。某天，我刷到了一道神奇的題目： # 136. 只出現(xiàn)一次的數(shù)字給定一個非空整數(shù)數(shù)組，除了某個元素只...

劉明 2019-05-22 14:21 評論0 收藏0