algorithm - “换电”算法

Question

首先，我不确定如何命名这个问题。如果有人有更好的想法，请随时更改或告诉我这样做。

假设我有两个字符串 s1，s2 包含“+”和“-”，表示正电荷和负电荷。

s1 是我们的开始输入，s2 是我们想从 s1 获得的模式。我们唯一的操作是我们可以将电荷变为相反。但是当我们这样做时，不仅选择的电荷被改变，而且我们选择的电荷旁边的电荷（左和右，除了第一个和最后一个字符，因为其中一个没有左和另一个右）。

1. 当无法从 s1 到 s2 时。
2. 如何找到从 s1 到 s2 的最小电荷变化量。

我相信唯一的一个是当我们的字符串长度为 2 并且总量“+”（或“-”）是奇数时。例如

在：“+-”

模式：“++”

否则这是可能的，但我们将不胜感激。至于第2点，我不知道，欢迎任何提示。

Answer 1

您对问题何时可以解决的直觉并不完全正确。任何时候都有一半的实例无法解决n = 2 (mod 3)。看到这一点的一种方法是通过几个步骤来减少适当的方程组（mod 2）。另一种查看冗余的方法是查看翻转第一个、第四个、第七个、... (n-1)st 与翻转第二个、第五个、八个、... nth 影响完全相同的字符集。

至于解决这些问题的算法：第一次翻转有两种可能的选择。一旦您决定是否翻转第一个字符，第一个字符的值会告诉您是否需要翻转第二个字符。然后第二个字符的值告诉你是否翻转第三个字符。等等。因此，只需尝试两种可能性。如果两者都不起作用，则问题无法解决；如果有，请报告；如果两者都有效，请报告需要较少翻转的那个。