Giả sử chúng ta có một chuỗi nhị phân s. Hãy để chúng tôi xem xét một hoạt động mà chúng tôi có thể lật một chút. Chuỗi s được gọi là chuỗi xen kẽ nếu không có hai ký tự liền kề nào giống nhau. Chúng ta phải tìm số lượng thao tác tối thiểu cần thiết để thực hiện xen kẽ.
Vì vậy, nếu đầu vào là s ="11100011", thì đầu ra sẽ là 3 vì nếu chúng ta lật các bit ở vị trí 1, 4 và 7, thì nó sẽ là "10101010", khi đó tất cả đều xen kẽ.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
thay đổi:=0
-
Even_1:=0, Even_0:=0
-
lẻ_1:=0, lẻ_0:=0
-
đối với tôi trong phạm vi từ 0 đến kích thước của s-1, hãy thực hiện
-
nếu tôi là số chẵn thì
-
nếu s [i] giống với '1' thì
-
Even_1:=Even_1 + 1
-
-
nếu không,
-
Even_0:=Even_0 + 1
-
-
-
nếu không,
-
nếu s [i] giống với '1' thì
-
lẻ_1:=lẻ_1 + 1
-
-
nếu không,
-
lẻ_0:=lẻ_0 + 1
-
-
-
-
nếu (chẵn_1 + lẻ_0)> (chẵn_0 + lẻ_1) thì
-
thay đổi:=chẵn_0 + lẻ_1
-
-
nếu không,
-
thay đổi:=chẵn_1 + lẻ_0
-
-
trả lại tiền lẻ
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn &minnus;
def solve(s): change = 0 even_1 = 0 even_0 = 0 odd_1 = 0 odd_0 = 0 for i in range(len(s)): if(i%2 == 0): if(s[i]=='1'): even_1 +=1 else: even_0 +=1 else: if(s[i] == '1'): odd_1 +=1 else: odd_0 +=1 if((even_1+odd_0)>(even_0+odd_1)): change = even_0 + odd_1 else: change = even_1 + odd_0 return change s = "11100011" print(solve(s))
Đầu vào
"11100011"
Đầu ra
3