用 Python 编写程序，查找将所有 1 组合在一起所需的最少交换次数

pythonserver side programmingprogramming更新于 2026/1/15 1:48:17

假设我们有一个二进制字符串，我们必须找到在字符串的任意位置将所有 1 组合在一起所需的最少交换次数。因此，如果输入为"10101001101"，则输出将为 3，因为可能的解决方案是"00000111111"。

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

data := 给定字符串中的位列表
设置 one := 0，n:= 数据数组的长度
创建一个大小为 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
while right < n
- 如果 left 为 0，则 temp := summ[right]，否则 temp := summ[right] –
- summ[left - 1]
- ans := 最小 ans，one – temp
- left right 各增加 1
返回 ans

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

示例

class Solution(object):
   def solve(self, data):
      data = list(map(int, list(data)))
      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()
print(ob.solve("10101001101"))