时间戳

首页 > 解决方案 > 给定一个全为 0 的二进制字符串，将其隐藏在目标字符串中

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

问题描述

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

例如

输入：（00101代表目标）

输出 ：3

解释 ：

00000 -> 00111 -> 00100 -> 00101

标签： javaalgorithmdata-structures

解决方案

两个观察：

  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

推荐阅读