Pythonでリストのバランスをとるために両端から必要な削除の最小数を見つけるプログラム

0と1を含むリストがあるとすると、リストの前または後ろから値を削除する必要があります。最後に、残りのリストの0と1の数が等しくなるように、必要な削除の最小数を見つける必要があります。

したがって、入力がnums =[1、1、1、0、0、1]の場合、出力は2になります。これは、最初の1と最後の1を削除して、2つの1と2つの0を作成できるためです。 。

これを解決するには、次の手順に従います-

• 最長：=0
• d：=キー0に値-1を入力したマップ
• currSum：=0
• 0からnumsのサイズの範囲のiの場合は、
  • nums [i]が0と同じ場合、
    • currSum：=currSum-1
  • それ以外の場合、
    • currSum：=currSum + 1
  • currSumがdにある場合、
    • longest：=最長の最大値とi --d [currSum]
  • それ以外の場合、
    • d [currSum]：=i
• numsのサイズを返す-最長

理解を深めるために、次の実装を見てみましょう-

例

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]

出力

2