Python程序：计算将所有1分组所需的交换次数

假设我们有一个二进制字符串，我们可以交换任意两位。我们必须找到将所有1分组所需的最小交换次数。

因此，如果输入类似于s = "0111001"，则输出将为1，因为我们可以执行以下交换：0111001 -> 1111000。

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

  • data := 从给定二进制字符串中提取的0和1列表
  • one := 0, n:= data数组的长度
  • 创建一个大小为n的数组summ，并将其填充为0，设置summ[0] := data[0]
  • one := one + data[0]
  • 对于i从1到n – 1
    • summ[i] := summ[i - 1] + data[i]
    • one := one + data[i]
  • ans := one
  • left := 0, right := one – 1
  • 当right < n
    • 如果left为0，则temp := summ[right]，否则temp := summ[right] – summ[left - 1]
    • ans := ans和one – temp中的最小值
    • 将right和left分别加1
  • 返回ans

示例（Python）

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

 在线演示

class Solution(object):
   def solve(self, s):
      data = list(map(int, list(s)))
      one = 0
      n = len(data)
      summ=[0 for i in range(n)]
      summ[0] = data[0]
      one += data[0]
      for i in range(1,n):
         summ[i] += summ[i-1]+data[i]
         one += data[i]
      ans = one
      left = 0
      right = one-1
      while right <n:
         if left == 0:
            temp = summ[right]
         else:
            temp = summ[right] - summ[left-1]
         ans = min(ans,one-temp)
         right+=1
         left+=1
      return ans
ob = Solution()
s = "0111001"
print(ob.solve(s))

输入

"0111001"

输出

1

更新于：2020年12月12日

116 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告