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

Giả sử chúng ta có một danh sách chứa các số 0 và 1, chúng ta phải xóa các giá trị ở phía trước hoặc phía sau của danh sách. Cuối cùng, chúng ta phải tìm số lần xóa tối thiểu cần thiết để danh sách còn lại có số lượng 0 và 1 bằng nhau.

Vì vậy, nếu đầu vào giống như nums =[1, 1, 1, 0, 0, 1], thì đầu ra sẽ là 2, vì chúng ta có thể xóa đầu vào 1 và cuối cùng là 1 để có hai số 1 và hai số 0 .

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• dài nhất:=0
• d:=một bản đồ trong đó đặt giá trị -1 cho khóa 0
• currSum:=0
• đối với tôi trong phạm vi từ 0 đến kích thước là num, hãy thực hiện
  • nếu nums [i] giống 0, thì
    • currSum:=currSum - 1
  • nếu không,
    • currSum:=currSum + 1
  • nếu currSum bằng d, thì
    • dài nhất:=tối đa là dài nhất và i - d [currSum]
  • nếu không,
    • d [currSum]:=i
• trả về kích thước nums - dài nhất

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

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

Đầu ra

2