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

更新於：2020年10月19日

175次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告