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

Arnab Chakraborty

更新於：2020年12月12日

116 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習