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

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

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

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

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

代碼如下：

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

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

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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/42557.html

相關(guān)文章

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

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

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

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

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

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

iliyaku 2021-09-27 13:36 評(píng)論0 收藏0
由三道 LeetCode 題目簡(jiǎn)單了解一下位運(yùn)算

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

daydream 2019-05-21 11:41 評(píng)論0 收藏0
由三道 LeetCode 題目簡(jiǎn)單了解一下位運(yùn)算

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

劉明 2019-05-22 14:21 評(píng)論0 收藏0