数据结构
网络
关系数据库管理系统
操作系统
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 次查看
