在Python中编写计算所需交换所有1以进行分组的程序

在Python中编写计算所需交换所有1以进行分组的程序

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

那么,如果输入为s =“0111001”,则输出将为1,因为我们可以执行这些交换:0111001-> 1111000。

要解决这个问题,我们将遵循以下步骤:

  • data:获取给定二进制字符串中0和1的列表
  • set one := 0,n:数据数组的长度
  • 制作大小为n的summ数组,并用0填充它,将summ [0]设置为data [0]
  • one := one + data [0]
  • for i in range 1 to n-1
    • summ[i] := summ[i-1] + data[i]
    • one := one + data[i]
  • ans := one
  • left := 0,right := one-1
  • while right
  • 如果left为0,则temp:= summ [right],否则temp:= summ [right] – summ [left-1]
  • ans := ans,one-temp的最小值
  • increase right and left by 1
    • return 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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程