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

มีอาร์เรย์ไบนารี nums และค่า k แต่ละครั้งสลับตำแหน่งติดกันได้ หาจำนวนการสลับน้อยที่สุดให้มี 1 ติดกัน k ตัว

ตัวอย่าง: nums=[1,0,0,1,0,1,0,1], k=3 ผลลัพธ์ 2

วิธีแก้ปัญหา (Sliding Window บนตำแหน่งของ 1)

1. เก็บตำแหน่งของ 1 ใน loc
2. ใช้ sliding window ขนาด k บน loc
3. คำนวณการสลับขั้นต่ำด้วย median trick: val += loc[-1] - loc[m] - (len(loc)-j)//2

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

def solve(nums, k):
    j = val = 0
    ans = 999999
    loc = []
    for i, x in enumerate(nums):
        if x:
            loc.append(i)
            m = (j + len(loc) - 1)//2
            val += loc[-1] - loc[m] - (len(loc)-j)//2
            if len(loc) - j > k:
                m = (j + len(loc))//2
                val -= loc[m] - loc[j] - (len(loc)-j)//2
                j += 1
            if len(loc)-j == k:
                ans = min(ans, val)
    return ans

nums = [1,0,0,1,0,1,0,1]
k = 3
print(solve(nums, k))

อินพุต

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

เอาต์พุต

2