Chương trình tìm các giao dịch hoán đổi liền kề tối thiểu cho K hoán đổi liên tiếp trong Python

Giả sử chúng ta có một số mảng nhị phân và một giá trị k. Trong một lần di chuyển, chúng ta có thể chọn hai chỉ số liền kề và hoán đổi giá trị của chúng. Chúng ta phải tìm số lần di chuyển tối thiểu cần thiết để số có k số 1 liên tiếp.

Vì vậy, nếu đầu vào giống như nums =[1,0,0,1,0,1,0,1], k =3, thì đầu ra sẽ là 2 vì trong một lần hoán đổi, chúng ta có thể tạo mảng từ [1,0 , 0,1,0,1,0,1] đến [1,0,0,0,1,1,0,1], sau đó [1,0,0,0,1,1,1,0] .

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

• j:=0

• val:=0

• ans:=999999

• loc:=a new list

• đối với mỗi chỉ số i và giá trị x tính bằng số, thực hiện

  • nếu x khác 0 thì

    • chèn tôi vào cuối loc

    • m:=thương số của (j + kích thước của loc - 1) / 2

    • val:=val + loc [-1] - loc [m] - thương số của (kích thước của loc -j) / 2

    • nếu độ dài của loc - j> k, thì

      • m:=thương số của (j + kích thước của loc) / 2

      • val:=val - loc [m] - loc [j] - thương số của (kích thước của loc -j) / 2

      • j:=j + 1

    • nếu kích thước của loc -j bằng k thì

      • ans:=tối thiểu ans và val

• trả lại ans

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, k):
   j = val = 0
   ans = 999999
   loc = []
   for i, x in enumerate(nums):
      if x:
         loc.append(i)
         m = (j + len(loc) - 1)//2
         val += loc[-1] - loc[m] - (len(loc)-j)//2
         if len(loc) - j > k:
            m = (j + len(loc))//2
            val -= loc[m] - loc[j] - (len(loc)-j)//2
            j += 1
         if len(loc)-j == k:
            ans = min(ans, val)
   return ans

nums = [1,0,0,1,0,1,0,1]
k = 3
print(solve(nums, k))

Đầu vào

[1,0,0,1,0,1,0,1], 3

Đầu ra

2