Chương trình đếm số lần hoán vị để gom tất cả bit 1 lại với nhau trong Python

Cho chuỗi nhị phân, cho phép hoán vị bất kỳ hai bit nào. Tìm số hoán vị tối thiểu để gom tất cả các bit 1 thành một khối liên tiếp.

Ví dụ: s = "0111001" → hoán vị bit 1 ở cuối với bit 0 ở đầu → "1111000" → 1 lần hoán vị.

Giải thuật (Cửa sổ trượt trên mảng tiền tố)

• Chuyển chuỗi thành mảng data 0/1. Tổng số 1 là one.
• Tính mảng tiền tố summ.
• Cửa sổ độ dài one trượt qua mảng, đếm số 1 trong cửa sổ (temp). Số 0 trong cửa sổ = one - temp là số hoán vị cần cho cửa sổ đó.
• Lấy min của one - temp qua mọi cửa sổ.

Mã nguồn Python

class Solution:
    def solve(self, s):
        data = list(map(int, list(s)))
        one = sum(data)
        n = len(data)
        if one == 0:
            return 0
        summ = [0] * n
        summ[0] = data[0]
        for i in range(1, n):
            summ[i] = summ[i-1] + 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))  # Output: 1

Đầu vào

"0111001"

Đầu ra

1