Giả sử chúng ta có một chuỗi nhị phân và chúng ta có thể hoán đổi hai bit bất kỳ. Chúng tôi phải tìm số lượng hoán đổi tối thiểu cần thiết để nhóm tất cả các số 1 lại với nhau.
Vì vậy, nếu đầu vào là s ="0111001", thì đầu ra sẽ là 1, vì Chúng ta có thể thực hiện các hoán đổi sau:0111001 -> 1111000.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- data:=danh sách các số 0 và 1 từ chuỗi nhị phân đã cho
- đặt một:=0, n:=độ dài của mảng dữ liệu
- tạo một tổng mảng có kích thước n và điền vào giá trị này bằng 0, đặt tổng [0]:=data [0]
- một:=một + dữ liệu [0]
- cho tôi trong phạm vi từ 1 đến n - 1
- summ [i]:=summ [i - 1] + data [i]
- một:=một + dữ liệu [i]
- ans:=một
- left:=0, right:=one - 1
- trong khi đúng
- nếu bên trái là 0 thì temp:=summ [right], ngược lại temp:=summ [right] - summ [left - 1]
- ans:=tối thiểu ans, một - tạm độ
- tăng bên phải và bên trái 1
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class Solution(object): def solve(self, s): data = list(map(int, list(s))) one = 0 n = len(data) summ=[0 for i in range(n)] summ[0] = data[0] one += data[0] for i in range(1,n): summ[i] += summ[i-1]+data[i] one += data[i] ans = one left = 0 right = one-1 while right <n: if left == 0: temp = summ[right] else: temp = summ[right] - summ[left-1] ans = min(ans,one-temp) right+=1 left+=1 return ans ob = Solution() s = "0111001" print(ob.solve(s))
Đầu vào
"0111001"
Đầu ra
1