Python에서 목록 균형을 맞추기 위해 두 끝에서 필요한 최소 삭제 수를 찾는 프로그램

<시간/>

0과 1을 포함하는 목록이 있다고 가정하고 목록의 앞이나 뒤에서 값을 제거해야 합니다. 마지막으로, 나머지 목록이 0과 1의 동일한 수를 갖도록 필요한 최소 삭제 횟수를 찾아야 합니다.

따라서 입력이 nums =[1, 1, 1, 0, 0, 1]과 같으면 출력은 2가 됩니다. 첫 번째 것 1과 마지막 것 1을 삭제하여 두 개의 1과 두 개의 0이 있도록 할 수 있기 때문입니다. .

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

가장 긴 :=0
d :=키 0에 값 -1을 입력하는 맵
currSum :=0
0~숫자 크기 범위의 i에 대해
- nums[i]가 0과 같으면
  - currSum :=currSum - 1
- 그렇지 않으면
  - currSum :=currSum + 1
- currSum이 d에 있으면
  - longest :=가장 긴 것의 최대값 및 i - d[currSum]
- 그렇지 않으면
  - d[currSum] :=나
숫자의 반환 크기 - 가장 긴

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

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

입력

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