資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：查詢最長的“很棒”子字串
假設我們有一個數字字串s。眾所周知，“很棒”的子字串是s的一個非空子字串，我們可以對其進行任意次交換以使其成為迴文。我們必須找到s的最長“很棒”子字串的長度。
因此，如果輸入類似於s = "4353526"，則輸出將為5，因為"35352"是最長的“很棒”子字串。我們可以將“35253”變成迴文。
為了解決這個問題，我們將遵循以下步驟：
n := 0
pos_map := 一個對映，其中包含鍵0以及對應的值s的大小
max_len := 1
對於範圍從s的大小-1到0，遞減1的i，執行以下操作：
n := n XOR (2^s[i])
如果n存在於pos_map中，則：
max_len := max_len和pos_map[n]-i中的最大值
對於範圍從0到9的j，執行以下操作：
m := n XOR 2^j
如果m存在於pos_map中，則：
max_len := max_len和pos_map[m]-i中的最大值
如果n不在pos_map中，則：
pos_map[n] := i
返回max_len
示例
讓我們看看下面的實現以更好地理解
def solve(s):
n = 0
pos_map = {0:len(s)}
max_len = 1
for i in range(len(s)-1, -1, -1):
n = n ^ (1 << int(s[i]))
if n in pos_map:
max_len = max(max_len, pos_map[n]-i)
for j in range(10):
m = n ^ (1 << j)
if m in pos_map:
max_len = max(max_len, pos_map[m]-i)
if n not in pos_map:
pos_map[n] = i
return max_len
s = "4353526"
print(solve(s))輸入
"4353526"
輸出
5
更新於: 2021年10月6日
439 次檢視
廣告