पायथन में सूची को संतुलित करने के लिए दो छोरों से आवश्यक न्यूनतम संख्या में विलोपन खोजने का कार्यक्रम

मान लीजिए कि हमारे पास 0s और 1s वाली एक सूची है, हमें सूची के आगे या पीछे से मानों को हटाना होगा। अंत में, हमें आवश्यक न्यूनतम संख्या में विलोपन की आवश्यकता है ताकि शेष सूची में 0 और 1 की समान संख्या हो।

इसलिए, यदि इनपुट nums =[1, 1, 1, 0, 0, 1] जैसा है, तो आउटपुट 2 होगा, क्योंकि हम पहले वाले 1 और अंतिम 1 को हटा सकते हैं ताकि दो 1s और दो 0s हों ।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• सबसे लंबा :=0
• d :=एक नक्शा जहां कुंजी 0 के लिए मान -1 रखा जाता है
• currSum:=0
• मैं के लिए 0 से लेकर अंकों के आकार तक, करें
  • यदि अंक [i] 0 के समान है, तो
    • currSum :=currSum - 1
  • अन्यथा,
    • currSum :=currSum + 1
  • यदि currSum d में है, तो
    • सबसे लंबा :=अधिकतम सबसे लंबा और i - d[currSum]
  • अन्यथा,
    • d[currSum] :=i
• अंकों का वापसी आकार - सबसे लंबा

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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