java - 给定一个全 0 的二进制字符串，将其隐藏到目标字符串中

Question

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

例如

输入:00101(代表目标)

输出:3

解释:

00000 -> 00111 -> 00100 -> 00101

Answer 1

两个观察:

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

2. 在某些时候，您必须翻转不匹配的最高有效位

这给了我们一个方便的贪心论证。我们总是会通过翻转最左边需要翻转的位来得到最优解。在某些时候我们必须翻转那个位，顺序并不重要所以我们不妨先做。

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

然后我们可以做最后的观察，让生活变得更轻松:

1. 翻转相互抵消。与其问从 0 到目标需要多少次翻转，不如问从目标到 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)

更简洁:

bits = [0, 0, 1, 0, 1]
result = 0
for bit in bits: result += (result%2)^bit
print(result)

输出:

3