Hoán đổi tối thiểu để nhóm tất cả 1 lại với nhau bằng Python

Giả sử chúng ta có dữ liệu mảng nhị phân, chúng ta phải tìm số lượng hoán đổi tối thiểu cần thiết để nhóm tất cả các 1 được lưu trữ trong mảng lại với nhau ở bất kỳ vị trí nào trong mảng. Vì vậy, nếu mảng giống như [1,0,1,0,1,0,0,1,1,0,1], thì kết quả đầu ra sẽ là 3, giải pháp có thể là [0,0,0,0, 0,1,1,1,1,1,1]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• đặt một:=0, n:=độ dài của mảng dữ liệu
• tạo một tổng mảng có kích thước n và điền vào giá trị này bằng 0, đặt tổng [0]:=data [0]
• một:=một + dữ liệu [0]
• cho tôi trong phạm vi từ 1 đến n - 1
  • summ [i]:=summ [i - 1] + data [i]
  • một:=một + dữ liệu [i]
• ans:=một
• left:=0, right:=one - 1
• trong khi đúng
• nếu bên trái là 0 thì temp:=summ [right], ngược lại temp:=summ [right] - summ [left - 1]
• ans:=tối thiểu ans, một - tạm thời
• tăng bên phải và bên trái 1

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

class Solution(object):
   def minSwaps(self, 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.minSwaps([1,0,1,0,1,0,0,1,1,0,1]))

Đầu vào

[1,0,1,0,1,0,0,1,1,0,1]

Đầu ra

3