给定一个全 0 的二进制字符串，将它隐藏在目标字符串中

Question

给定一个表示目标状态的二进制字符串。将相同大小的二进制字符串（全部为 0）转换为目标状态所需的最小翻转次数。翻转还会导致所有正确的位被翻转。

例如

输入：（00101代表目标）

输出 ： 3

解释 ：

00000 -> 00111 -> 00100 -> 00101

Answer 1

两个观察：

1. 翻转是可交换的。无论您按什么顺序执行，您都会得到相同的结果。

2. 在某些时候，您必须翻转不匹配的最重要的位

这给了我们一个方便的贪婪论证。我们将始终通过翻转需要翻转的最左边的位来获得最佳解决方案。在某些时候，我们必须翻转那个位，顺序无关紧要，所以我们不妨先做一下。

实现这一点O(N)可能很棘手 - 如果我们天真地翻转所有东西，我们最终O(N)会得到一个提供O(N^2)解决方案的翻转。我们可以注意到，在确定当前位的真值时，我们只关心已经发生的翻转次数。如果此数字为奇数，则翻转该位的值。否则不变。

然后我们可以进行最后的观察，让生活变得更轻松：

3. 翻转相互抵消。与其问从 0 到目标需要多少次翻转，不如问从目标到 0 需要多少次翻转。每当一位的真值不等于零时，我们只需添加一个翻转。

伪代码：

result = 0
// most to least significant
for bit in bits:
    if result%2 == 0:
        if bit != 0: result += 1
    else:
        if not bit != 0: result += 1
print(result)

更简洁地说：

result = 0
// most to least significant
for bit in bits:
    if result%2 == 0:
        if bit != 0: result += 1
    else:
        if not bit != 0: result += 1
print(result)

输出：

3