โปรแกรมค้นหาการดำเนินการขั้นต่ำเพื่อลด X เป็นศูนย์ใน Python

สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums และอีกค่าหนึ่งคือ x ในการดำเนินการเดียว เราสามารถลบองค์ประกอบซ้ายสุดหรือขวาสุดออกจากอาร์เรย์แล้วลบค่าออกจาก x เราต้องหาจำนวนขั้นต่ำของการดำเนินการที่จำเป็นในการลด x ให้เป็น 0 หากไม่สามารถทำได้ ให้คืนค่า -1

ดังนั้นหากอินพุตเป็น nums =[4,2,9,1,4,2,3] x =9 ผลลัพธ์จะเป็น 3 เพราะในตอนแรกเราต้องลบองค์ประกอบที่เหลือส่วนใหญ่ 4 ดังนั้นอาร์เรย์จะเป็น [2,9,1,4,2,3] และ x จะเป็น 5 จากนั้นลบองค์ประกอบ 3 ส่วนใหญ่ออก ดังนั้นอาร์เรย์จะเป็น [2,9,1,4,2] และ x =2 จากนั้นอีกครั้งเช่นกัน ซ้ายจากซ้ายหรือขวาเพื่อสร้าง x =0 และอาร์เรย์จะเป็น [2,9,1,4] หรือ [9,1,4,2]

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

• n :=ขนาดของ nums
• leftMap :=แผนที่ใหม่
• leftMap[0] :=-1
• ซ้าย :=0
• สำหรับฉันในช่วง 0 ถึง n - 1 ทำ
  • ซ้าย :=ซ้าย + nums[i]
  • ถ้า left ไม่อยู่ใน leftMap แล้ว
    • leftMap[left] :=i
• ขวา :=0
• ตอบ :=n + 1
• สำหรับฉันในช่วง n ถึง 0, ลดลง 1 ทำ
  • ถ้าฉัน
  • ขวา :=ขวา + nums[i]
• ซ้าย :=x - ขวา
• ถ้า left มีอยู่ใน leftMap แล้ว
  • ans :=ขั้นต่ำของ ans และ leftMap[left] + 1 + n-i

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(nums, x):
   n = len(nums)

   leftMap = dict()
   leftMap[0] = -1
   left = 0
   for i in range(n):
      left += nums[i]
      if left not in leftMap:
         leftMap[left] = i

   right = 0
   ans = n + 1
   for i in range(n, -1, -1):
      if i < n:
         right += nums[i]
      left = x - right
      if left in leftMap:
         ans = min(ans, leftMap[left] + 1 + n - i)
   if ans == n + 1:
      return -1
   return ans

nums = [4,2,9,1,4,2,3]
x = 9
print(solve(nums, x))

อินพุต

[4,2,9,1,4,2,3], 9

ผลลัพธ์

3