給出一個僅由 0 和 1 組成的二進制字串。例如，0100101。我們可以選擇
任意兩個索引并交換它們。我們必須回傳使其
成為回文所需的最小交換次數，如果不能，則回傳 -1。字串 0100101 可以通過交換
(3,4)-> 0101001 和交換 (0,1) -> 1001001 這是一個回文來制作回文。在這種情況下，
正確答案是 2。
我的想法：
我想了想，并試圖找出一些屬性。但是，就像我們需要交換 1,0 或 0,1 一樣，用相同的值交換索引是沒有意義的。
如果字串是偶數長度，那么 0 和 1 的個數必須相等，如果它
是奇數長度，那么 1 和 o 的一個是奇數，另一個是偶數。
如果不滿足這個條件，那么就不可能使字串成為回文
但是這是否是充分條件，我不確定。
uj5u.com熱心網友回復：
您可以比較最外面的兩個數字：如果它們相同，則不需要發生任何事情，這些數字也不應該參與交換。
如果它們不同，請注意這一點，并且不要交換任何東西。
繼續每一端的第二個數字。比較它們。如果它們不同，這是我們第二次出現差異，請注意我們如何通過一次交換來解決這兩個差異。一個例子：
10.......10
通過一次交換，這可以變成：
10.......01
因此，我們可以通過一次交換解決兩個差異。這意味著如果我們找到偶數個差異——當我們沿著二進制字串從兩端向內走時——就有一個解決方案，它需要一半的交換次數。
如果差異的數量是奇數，那么如果輸入字串是奇數，仍然有一個解決方案，因為這樣中間的數字可以與最后一個差異的數字交換，從而得到回文。
但是，當差異的數量（在此演算法中）為奇數且輸入中的位數為偶數時，沒有解決方案。
現在，您實際上不必執行交換，因為挑戰只要求交換次數。
這導致以下代碼：
def numswaps(binary):
n = len(binary)
count = 0
for i in range(n // 2):
if binary[i] != binary[n - i - 1]:
count = 1
if count % 2 == 1 and n % 2 == 0:
return -1
return (count 1) // 2
你的意見
如果字串的長度是偶數，那么 0 和 1 的數量必須相等，
不，如果字串的長度是偶數，那么 0 的數量必須是偶數（這意味著 1 的數量是偶數）。
如果它的長度是奇數，那么 1 和 o 的一個數是奇數，另一個是偶數。
這是一個重言式：它總是正確的。不可能有一個奇數長度的字串，其中 1 和 0 的數量與您所說的不同。奇數長度的字串總是有解決方案。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/466754.html
下一篇：在遞回中只應用一次條件