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

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

ตัวอย่าง: nums = [1, 1, 1, 0, 0, 1] ผลลัพธ์ 2 (ลบ 1 ตัวหน้า และ 1 ตัวท้าย เหลือ 1,1,0,0)

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

1. longest = 0
2. d = {0: -1} (map prefix sum -> index แรก)
3. currSum = 0
4. วนลูป i จาก 0 ถึง len(nums)-1:
   • ถ้า nums[i] == 0: currSum -= 1
   • อื่นๆ: currSum += 1
   • ถ้า currSum in d: longest = max(longest, i - d[currSum])
   • อื่นๆ: d[currSum] = i
5. คืนค่า len(nums) - longest

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

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

อินพุต / เอาต์พุต

Input: [1, 1, 1, 0, 0, 1]

Output: 2