Python程序：找出需要从两端删除的最小数量，以使列表平衡

假设我们有一个包含0和1的列表，我们必须从列表的前端或后端删除值。最后，我们必须找到所需的最小删除次数，以便剩余列表中0和1的数量相等。

因此，如果输入类似于nums = [1, 1, 1, 0, 0, 1]，则输出将为2，因为我们可以删除第一个1和最后一个1，这样就有两个1和两个0。

为了解决这个问题，我们将遵循以下步骤：

• longest := 0
• d := 一个映射，其中键0的值为-1
• currSum := 0
• 对于范围从0到nums大小的i，执行：
  • 如果nums[i]等于0，则
    • currSum := currSum - 1
  • 否则，
    • currSum := currSum + 1
  • 如果d中包含currSum，则
    • longest := longest和i - d[currSum]中的最大值
  • 否则，
    • d[currSum] := i
• 返回nums的大小 - longest

让我们看看下面的实现，以便更好地理解：

示例

 在线演示

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

Arnab Chakraborty

更新于：2020年10月19日

175次浏览

开启你的职业生涯

完成课程获得认证

开始学习