โปรแกรมนับจำนวนการสลับเพื่อรวม 1 ให้อยู่ติดกันในสตริงไบนารีใน Python

สมมติว่าเรามีสตริงไบนารี และสามารถสลับบิตใดๆ ก็ได้สองตำแหน่ง ต้องการหาจำนวนการสลับขั้นต่ำเพื่อให้ 1 ทั้งหมดอยู่ติดกัน

เช่น s = "0111001" ผลลัพธ์ = 1 สลับได้ 0111001 → 1111000

ขั้นตอนการแก้ปัญหา (Sliding Window + Prefix Sum)

• data := list ของ 0 และ 1 จากสตริง
• one := จำนวน 1 ทั้งหมด, n := len(data)
• สร้าง summ = prefix sum array
• ans := one, left := 0, right := one - 1
• while right < n:
  • temp := summ[right] - (summ[left-1] if left > 0 else 0) (จำนวน 1 ในหน้าต่าง)
  • ans = min(ans, one - temp) (จำนวน 0 ในหน้าต่าง = จำนวนสลับที่ต้องทำ)
  • left++, right++
• คืน ans

ตัวอย่างโค้ด

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