โปรแกรมค้นหาจำนวนการลบขั้นต่ำที่ต้องการจากปลายทั้งสองเพื่อให้รายการสมดุลในPython

สมมติว่าเรามีรายการที่มี 0 และ 1 เราต้องลบค่าออกจากด้านหน้าหรือด้านหลังรายการ สุดท้าย เราต้องหาจำนวนการลบขั้นต่ำที่จำเป็น เพื่อให้รายการที่เหลือมีจำนวนเท่ากับ 0 และ 1 วินาที

ดังนั้น หากอินพุตเป็น nums =[1, 1, 1, 0, 0, 1] ผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถลบอันแรก 1 และอันสุดท้าย 1 เพื่อให้มี 1 และ 0 สองตัว .

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ยาวที่สุด :=0
• d :=แผนที่โดยใส่ค่า -1 สำหรับคีย์ 0
• currSum :=0
• สำหรับ i ในช่วง 0 ถึงขนาดของ nums ให้ทำ
  • ถ้า nums[i] เท่ากับ 0 แล้ว
    • currSum :=currSum - 1
  • มิฉะนั้น
    • currSum :=currSum + 1
  • ถ้า currSum อยู่ใน d แล้ว
    • ยาวที่สุด :=สูงสุดของที่ยาวที่สุดและ i - d[currSum]
  • มิฉะนั้น
    • d[currSum] :=ฉัน
• ขนาดผลตอบแทนของ 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