Python程序：在给定字符串中用最少交换次数将1分组

假设我们给定一个包含0和1的二进制字符串input_str。我们的任务是通过交换给定字符串中的1来分组0和1。我们必须执行最少的交换操作，并返回该值。需要注意的是，我们只能交换相邻的值。

因此，如果输入类似于input_str = 10110101，则输出将为4

交换将如下所示：

10110101->01110101->01111001->01111010->01111100

交换总数：4。

为了解决这个问题，我们将遵循以下步骤：

  • one := 一个新列表，包含input_str中1的位置
  • mid := one大小的向下取整值
  • res := 0
  • 对于范围0到one大小的i，执行：
    • res := res + |one[mid] - one[i]| - |mid - i|
  • 如果 res < 0，则
    • 返回 0
  • 否则，
    • 返回 res

示例

让我们看下面的实现来更好地理解：

def solve(input_string):
   one = [i for i in range(len(input_string)) if input_string[i] == "1"]
   mid = len(one) // 2
   res = 0
   for i in range(len(one)):
      res += abs(one[mid] - one[i]) - abs(mid - i)
   return 0 if res < 0 else res

print(solve('10110101'))

输入

'10110101'

输出

4

更新于：2021年10月16日

260 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告