資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：計算將字串轉換為迴文串所需的最小交換次數
假設我們有一個字串 s，我們需要找到將其轉換為迴文串所需的最小相鄰交換次數。如果無法解決，則返回 -1。
因此，如果輸入類似於 s = "xxyy"，則輸出將為 2，因為我們可以交換中間的 "x" 和 "y"，使字串變為 "xyxy"，然後交換前兩個 "x" 和 "y" 以獲得 "yxxy"，這是一個迴文串。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 util()。它將接收 s 作為輸入。
seen := 一個新的對映
對於 s 中的每個 i，執行以下操作：
seen[i] := 1 + (如果存在則為 seen[i]，否則為 0)
odd_count := 0
對於 seen 的每個鍵值對，執行以下操作：
如果值為奇數，則
odd_count := odd_count + 1
如果 odd_count 等於 2，則
返回 False
返回 True
在主方法中執行以下操作：
swaps := 0
如果 util(s) 為真，則
left := 0
right := s 的大小 - 1
s := 透過從 s 中獲取字元建立的新字元列表
當 left < right 時，執行以下操作：
如果 s[left] 不等於 s[right]，則
k := right
當 k > left 且 s[k] 不等於 s[left] 時，執行以下操作：
k := k - 1
如果 k 等於 left，則
swaps := swaps + 1
s[left], s[left + 1] := s[left + 1], s[left]
否則，
當 k < right 時，執行以下操作：
交換 s[k] 和 s[k + 1]
k := k + 1
swaps := swaps + 1
left := left + 1
right := right - 1
否則，
left := left + 1
right := right - 1
返回 swaps
返回 -1
示例（Python）
讓我們看看以下實現，以便更好地理解：
class Solution:
def solve(self, s):
def util(s):
seen = {}
for i in s:
seen[i] = seen.get(i, 0) + 1
odd_count = 0
for k, val in seen.items():
if val & 1 == 1:
odd_count += 1
if odd_count == 2:
return False
return True
swaps = 0
if util(s):
left = 0
right = len(s) - 1
s = list(s)
while left < right:
if s[left] != s[right]:
k = right
while k > left and s[k] != s[left]:
k -= 1
if k == left:
swaps += 1
s[left], s[left + 1] = s[left + 1], s[left]
else:
while k < right:
s[k], s[k + 1] = s[k + 1], s[k]
k += 1
swaps += 1
left += 1
right -= 1
else:
left += 1
right -= 1
return swaps
return -1
ob = Solution()
s = "xxyy"
print(ob.solve(s))輸入
"xxyy"
輸出
2
288 次檢視
