Giả sử chúng ta có một chuỗi nhị phân, chúng ta 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 1 lại với nhau ở bất kỳ vị trí nào trong chuỗi. Vì vậy, nếu đầu vào là "10101001101", thì đầu ra sẽ là 3, giải pháp khả thi là "00000111111".
Để 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 bit từ chuỗi đã cho
-
đặt một:=0, n:=độ dài của mảng dữ liệu
-
tạo 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]
-
one:=one + data [i]
-
-
ans:=một
-
left:=0, right:=one - 1
-
trong khi bên phải
-
nếu bên trái là 0 thì temp:=summ [right], ngược lại temp:=summ [right] -
- tổng [trái - 1]
-
ans:=tối thiểu ans, một - tạm thời
-
tăng sang phải và trái 1
-
-
trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution(object):
def solve(self, data):
data = list(map(int, list(data)))
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()
print(ob.solve("10101001101")) Đầu vào
"10101001101"
Đầu ra
3