制作二进制字符串回文所需的最小交换次数

Question

给出一个仅由 0 和 1 组成的二进制字符串。例如，0100101。我们可以选择
任意两个索引并交换它们。我们必须 return 进行
所需的最小交换次数它是回文，如果不能则为 -1。字符串 0100101 可以通过交换
变成回文 (3,4)-> 0101001 和交换 (0,1) -> 1001001 这是回文。在这种情况下，
正确答案是 2.

我的想法：
我仔细考虑并试图找出一些属性。但是，就像我们需要交换 1,0 或 0,1 一样，交换具有相同值的索引没有意义。
如果字符串是偶数长度，那么0和1的个数一定是相等的，如果
是奇数长度，那么1和o的数一个是奇数，一个是偶数。
如果不满足这个条件，那么就不可能让字符串成为回文
但是这是否是一个充分条件，我不确定。

Answer 1

您可以比较最外面的两个数字：如果它们相同，则不需要发生任何事情，也不应该将这些数字参与交换。

如果它们不同，请注意，不要交换任何东西。

继续计算两端的第二个数字。比较一下。如果它们不同，并且这是我们第二次出现差异，请注意我们如何通过一次交换解决这两个差异。一个例子：

 10.......10

交换一次可以变成：

 10.......01

所以我们可以一次解决两个分歧。这意味着如果我们找到 even 数量的差异——当我们沿着二进制字符串从两端向内走时——就有一个解决方案，它需要一半的交换次数.

如果差的个数是奇数，如果输入字符串的大小是奇数，还是有解法的，因为中间那个数字可以和最后一个差的数字交换，所以得到一个回文。

然而 no 当差异数（在此算法中）为奇数时 and 输入中的位数是偶数。

现在，您实际上不必执行交换，因为挑战只要求次交换。

这导致以下代码：

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

你的想法

If the string is of even length, then the number of 0's and 1's must be equal,

不是，如果字符串是偶数长度，那么0的个数必须是偶数（这意味着1的个数是偶数）。

and if it is of odd length, then one of the numbers of 1's and o's is odd, and the other is even.

这是同义反复：它总是正确的。不可能有一个奇数长度的字符串，其中 1 和 0 的数量与您所说的不同。对于奇数长度的字符串总是有解决方案的。

Answer 2

你已经得到了交换计数中最切题的答案。那解决了你已经提到的问题。如果您也有兴趣使用该方法构建 palindromized 字符串，则需要添加一些额外的步骤。您不仅需要计算交换次数，还需要记住它们需要发生的位置以及完成它们的最佳方法。在这里您可以找到 Java 中解决方案的扩展。第一种方法只计算（基本上是上述算法的 Java 实现），第二种方法也执行交换。在对随机生成的 1 到 10000 个字符长的字符串进行平均计数时，我注意到由于交换开销，执行时间缩短了 50%。我相信它可以进一步改进。

private static int countOnly(String input)
{
    int n = input.length();
    int count = 0;
    char[] inputAsCharArray = input.toCharArray();
    for (int i = 0; i < n / 2; i++)
    {
        if (inputAsCharArray[i] != inputAsCharArray[n - i - 1])
        {
            count++;
        }
    }
    if (count % 2 == 1 && n % 2 == 0)
        return -1;      
    return (count + 1) / 2;
}
private static int countAndPalindromize(String input)
{
    int n = input.length();
    int swapsCount = 0;
    int swaps[] = new int[n/2];
    for(int i = 0; i < swaps.length; i++)
    {
        swaps[i] = -1;
    }
    char[] inputAsCharArray = input.toCharArray();
    int count = 0;
    for (int i = 0; i < n / 2; i++)
    {
        if (inputAsCharArray[i] != inputAsCharArray[n - i - 1])
        {
            count++;
            if (swaps[0] != -1)
            {
                if (inputAsCharArray[i] != inputAsCharArray[swaps[0]])
                {
                    char c = inputAsCharArray[i];
                    inputAsCharArray[i] = inputAsCharArray[swaps[0]];
                    inputAsCharArray[swaps[0]] = c;
                    for (int y = 1; y <= swapsCount; y++)
                    {
                        swaps[y - 1] = swaps[y];
                    }
                    swapsCount--;
                }
                else if (inputAsCharArray[n - i - 1] != inputAsCharArray[swaps[0]])
                {
                    char c = inputAsCharArray[n - i - 1];
                    inputAsCharArray[n - i - 1] = inputAsCharArray[swaps[0]];
                    inputAsCharArray[swaps[0]] = c;
                    for (int y = 1; y <= swapsCount; y++)
                    {
                        swaps[y - 1] = swaps[y];
                    }
                    swapsCount--;
                }
                else
                {
                    swaps[swapsCount++] = n - i - 1;
                }
            }
            else
            {
                swaps[swapsCount++] = n - i - 1;
            }
        }
    }
    
    if (count % 2 == 1 && n % 2 == 0)
        return -1;
    return (count + 1) / 2;
}

制作二进制字符串回文所需的最小交换次数

Minimum number of swaps required to make a binary string palindrome

python

algorithm

你的想法