Chương trình tìm các bước di chuyển tối thiểu để làm cho mảng bổ sung trong Python

Giả sử chúng ta có một số mảng có độ dài chẵn khác giới hạn giá trị. Trong một lần di chuyển, chúng ta có thể thay thế bất kỳ giá trị nào từ num bằng một giá trị khác từ 1 đến giới hạn, bao gồm cả. Mảng được cho là bổ sung nếu đối với tất cả các chỉ số i, nums [i] + nums [n-1-i] bằng cùng một số. Vì vậy, chúng ta phải tìm ra số lần di chuyển tối thiểu cần thiết để tạo ra các số bổ sung.

Vì vậy, nếu đầu vào giống như nums =[1,4,2,3] limit =4, thì đầu ra sẽ là 1 vì trong một lần di chuyển chúng ta có thể tạo phần tử ở chỉ số 1 đến 2, vì vậy mảng sẽ là [1,2 , 2,3], rồi đến nums [0] + nums [3] =4, nums [1] + nums [2] =4, nums [2] + nums [1] =4, nums [3] + nums [ 0] =4

Để 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
• mid:=thương số của n / 2
• zero_moves:=một bản đồ trống có giá trị kiểu số nguyên
• start:=một mảng có kích thước (2 * giới hạn + 1) và điền bằng 0
• end:=một mảng có kích thước (2 * giới hạn + 1) và điền bằng 0
• res:=infinity
• đối với tôi trong phạm vi từ 0 đến giữa - 1, hãy thực hiện
  • x:=nums [i]
  • y:=nums [n - 1 - i]
  • zero_moves [x + y]:=zero_moves [x + y] + 1
  • tăng bắt đầu [1 + tối thiểu của x, y] lên 1
  • tăng cuối [giới hạn + tối đa của x, y] lên 1
• khoảng thời gian:=0
• đối với mục tiêu trong phạm vi 2 đến giới hạn * 2, hãy thực hiện
  • khoảng thời gian:=khoảng thời gian + bắt đầu [mục tiêu]
  • chi phí:=2 * (giữa - khoảng) + khoảng - zero_moves [target]
  • res:=tối thiểu của res và chi phí
  • khoảng thời gian:=khoảng thời gian - kết thúc [mục tiêu]
• trả lại res

Ví dụ

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

from collections import defaultdict
def solve(nums, limit):
   n = len(nums)
   mid = n // 2

   zero_moves = defaultdict(int)

   start = [0] * (2 * limit + 1)
   end = [0] * (2 * limit + 1)
   res = float('inf')
   for i in range(mid):
      x = nums[i]
      y = nums[n - 1 - i]
      zero_moves[x + y] += 1
      start[min(x, y) + 1] += 1
      end[max(x, y) + limit] += 1

   intervals = 0
   for target in range(2, limit * 2 + 1):
      intervals += start[target]
      cost = 2 * (mid - intervals) + intervals - zero_moves[target]
      res = min(res, cost)
      intervals -= end[target]
   return res

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

Đầu vào

[1,4,2,3], 4

Đầu ra

1