Chương trình tìm số lần xóa tối thiểu từ hai đầu để danh sách cân bằng bằng Python

Cho danh sách chỉ chứa 0 và 1. Có thể xóa từ đầu hoặc cuối. Tìm số lần xóa tối thiểu sao cho danh sách còn lại có số lượng 0 và 1 bằng nhau.

Ví dụ: nums = [1, 1, 1, 0, 0, 1] → 2 (xóa 1 ở đầu và 1 ở cuối, còn 2 số 1 và 2 số 0).

Quy trình giải quyết (Prefix Sum + Hash Map)

1. Biến đổi: 0 → -1, 1 → +1. Tìm dãy con liên tiếp dài nhất có tổng = 0.
2. Duyệt mảng, tính currSum (tiền tố).
3. Dùng từ điển d lưu chỉ số đầu tiên xuất hiện của mỗi currSum (khởi tạo d[0] = -1).
4. Nếu currSum đã có trong d, cập nhật longest = max(longest, i - d[currSum]).
5. Kết quả = len(nums) - longest.

Ví dụ mã nguồn

class Solution:
    def solve(self, nums):
        longest = 0
        d = {0: -1}
        currSum = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                currSum -= 1
            else:
                currSum += 1
            if currSum in d:
                longest = max(longest, i - d[currSum])
            else:
                d[currSum] = i
        return len(nums) - longest

ob = Solution()
nums = [1, 1, 1, 0, 0, 1]
print(ob.solve(nums))  # Output: 2

Đầu vào

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

Đầu ra

2