Chương trình tìm các phép toán tối thiểu để giảm X về 0 trong Python

Giả sử chúng ta có một mảng được gọi là nums và một giá trị khác là x. Trong một thao tác, chúng ta có thể xóa phần tử ngoài cùng bên trái hoặc ngoài cùng bên phải khỏi mảng và trừ giá trị cho x. Chúng ta phải tìm số phép toán tối thiểu cần thiết để giảm x xuống chính xác bằng 0. Nếu không thể thì trả về -1.

Vì vậy, nếu đầu vào là nums =[4,2,9,1,4,2,3] x =9, thì đầu ra sẽ là 3 vì lúc đầu chúng ta phải xóa phần tử bên trái gần hết 4, vì vậy mảng sẽ là [2,9,1,4,2,3] và x sẽ là 5, sau đó loại bỏ bên phải hầu hết phần tử 3, vì vậy mảng sẽ là [2,9,1,4,2] và x =2, sau đó một lần nữa trái từ trái hoặc từ phải để tạo thành x =0 và mảng sẽ là [2,9,1,4] hoặc [9,1,4,2].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của nums
• leftMap:=một bản đồ mới
• leftMap [0]:=-1
• trái:=0
• đối với tôi trong phạm vi từ 0 đến n - 1, thực hiện
  • left:=left + nums [i]
  • nếu left không có trong leftMap, thì
    • leftMap [left]:=i
• đúng:=0
• ans:=n + 1
• đối với tôi trong phạm vi n đến 0, giảm đi 1, thực hiện
  • nếu tôi
  • right:=right + nums [i]
• left:=x - right
• nếu left có trong Bản đồ trái, thì
  • ans:=tối thiểu ans và leftMap [left] + 1 + n-i

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

3