Chương trình tìm số hoán vị liền kề tối thiểu cho K số 1 liên tiếp trong Python

Mô tả bài toán

Cho mảng nhị phân nums và giá trị k. Một phép: hoán vị hai phần tử liền kề. Tìm số phép tối thiểu để có k số 1 liên tiếp.

Ví dụ

nums = [1,0,0,1,0,1,0,1], k = 3 -> 2 (hoán vị tạo ra [1,0,0,0,1,1,0,1] rồi [1,0,0,0,1,1,1,0]).

Giải thuật (Sliding Window + Median)

1. Lưu vị trí các số 1 vào mảng loc.
2. Duy trì cửa sổ trượt kích thước k trên loc.
3. Tối ưu hóa vị trí trung vị: di chuyển các số 1 về vị trí trung vị để giảm tổng khoảng cách.
4. Cập nhật chi phí tăng dần khi mở rộng/thu hẹp cửa sổ.

Triển khai Python

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))

Đầu vào

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

Đầu ra

2