Chương trình tìm số lần lật tối thiểu được yêu cầu để có các giá trị xen kẽ trong Python

Giả sử chúng ta có một chuỗi nhị phân s. Bây giờ, giả sử chúng ta có thể lấy một số tiền tố của s và chuyển nó ra phía sau. sau đó, tìm số ký tự tối thiểu cần được lật sao cho không có ký tự liên tiếp nào có cùng giá trị.

Vì vậy, nếu đầu vào là s =​​"10010101111", thì đầu ra sẽ là 2, vì chúng ta có thể lấy tiền tố "10", sau đó di chuyển nó về phía sau để chuỗi là "01010111110" rồi lật bit thứ 3 và thứ 5 từ phải sang 0 ("01010101010").

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

• ans:=kích thước của S

• N:=kích thước của S

• s:=0

• đối với tôi trong phạm vi 0 đến 2 * N, thực hiện

  • s:=s + số nguyên của (S [i mod N] XOR (i AND 1))

  • nếu tôi> =N - 1, thì

    • ans:=tối thiểu ans, s và N - s

    • s:=s - số nguyên của (S [(i - (N - 1)) mod N]) XOR ((i - (N - 1)) AND 1)

• trả lại ans

Ví dụ

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

class Solution:
   def solve(self, S):
      ans = N = len(S)
      s = 0
      for i in range(2 * N):
         s += int(S[i % N]) ^ (i & 1)
         if i >= N - 1:
            ans = min(ans, s, N - s)
            s -= int(S[(i - (N - 1)) % N]) ^ ((i - (N - 1)) & 1)
      return ans
ob = Solution()
s = "10010101111"
print(ob.solve(s))

Đầu vào

"10010101111"

Đầu ra

2