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

劉玉平發布于2019-07-30 18:00 / 2718人閱讀

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

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

輸入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最長相同子串

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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