java - 给定一个全为 0 的二进制字符串,将其隐藏在目标字符串中
问题描述
给定一个表示目标状态的二进制字符串。将相同大小的二进制字符串(全为 0)转换为目标状态所需的最少翻转次数。翻转也会导致所有正确的位被翻转。
例如
输入:(00101
代表目标)
输出 :3
解释 :
00000 -> 00111 -> 00100 -> 00101
解决方案
两个观察:
翻转是可交换的。无论您按什么顺序进行操作,您都会得到相同的结果。
在某些时候,您必须翻转不匹配的最重要位
这给了我们一个方便的贪心论点。我们总是通过翻转需要翻转的最左边的位来获得最佳解决方案。在某些时候,我们必须翻转那个位,顺序无关紧要,所以我们不妨先做。
实现这一点可能O(N)
会很棘手 - 如果我们天真地翻转所有东西,我们最终O(N)
会得到一个提供解决方案的翻转O(N^2)
。我们可以注意到,在确定当前位的真值时,我们只关心已经发生的翻转次数。如果这个数字是奇数,则该位的值被翻转。否则不变。
然后我们可以进行最后的观察,让生活变得更轻松:
- 翻转相互抵消。与其问从 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
推荐阅读
- python - 如何从自定义 AI 平台模型登录
- excel - 仅刷新excel电源查询/数据模型中的内部连接
- function - 使用 defalias 或新函数创建 Lisp 别名?
- flutter - Flutter - 在充满其他小部件的屏幕上检测点击
- c++ - 球体/平面碰撞检测
- ios - 使用推送弹出导航在多个视图控制器之间传递数据时出现问题
- oracle - 从 oracle 和 postgres 的字符串列表中过滤无效 ID
- ajax - laravel刀片模板中的Ajax更新字段数据库字段
- javascript - 从 JSON 数组中确定最高值
- python - 读取带有限制和偏移量的 CSV 文件