Giả sử chúng ta có một chuỗi nhị phân được gọi là các hộp, trong đó các hộp [i] là '0' cho biết hộp thứ i trống và '1' cho biết nó chứa một quả bóng. Bây giờ, trong một thao tác, chúng ta có thể di chuyển một quả bóng từ một hộp sang hộp liền kề. Sau khi làm như vậy, có thể có nhiều hơn một quả bóng trong một số hộp. Chúng ta phải tìm một câu trả lời mảng có kích thước n, trong đó câu trả lời [i] là số phép toán tối thiểu cần thiết để di chuyển tất cả các quả bóng đến hộp thứ i.
Vì vậy, nếu đầu vào giống như box ="1101", thì đầu ra sẽ là [4, 3, 4, 5]
-
Để đặt tất cả các quả bóng vào hộp đầu tiên, chúng ta phải lấy từ hộp 2 bằng một phép toán và từ quả bóng cuối cùng bằng ba phép toán, như vậy có tổng cộng 4 phép toán.
-
Để đặt tất cả các quả bóng vào hộp thứ hai, chúng ta phải lấy từ hộp 1 bằng một phép toán và từ quả bóng cuối cùng bằng hai phép toán, như vậy có tổng cộng 3 phép toán.
-
Để đặt tất cả các quả bóng vào hộp thứ ba, chúng ta phải lấy từ hộp 2 và cuối cùng với một phép toán mỗi lần và từ hộp1 bằng hai phép toán, như vậy có tổng cộng 4 phép toán.
-
Để đặt tất cả các quả bóng vào hộp cuối cùng, chúng ta phải lấy từ hộp1 với ba phép toán và từ hộp2 với hai phép toán, vậy có tổng cộng 5 phép toán.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
left:=0, right:=0, dist:=0
-
đối với tôi trong phạm vi từ 0 đến kích thước của hộp - 1, thực hiện
-
nếu các hộp [i] giống với "1" thì
-
dist:=dist + i
-
nếu tôi giống 0, thì
-
left:=left + 1
-
-
nếu không,
-
right:=right + 1
-
-
-
-
arr:=một danh sách và ban đầu đặt dist vào đó
-
đối với tôi trong phạm vi từ 1 đến kích thước hộp - 1, làm
-
chèn arr [i-1] + left - right vào cuối arr
-
nếu các hộp [i] giống với "1" thì
-
left:=left + 1
-
right:=right - 1
-
-
-
return arr
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(boxes):
left = 0
right = 0
dist = 0
for i in range(len(boxes)):
if boxes[i] == "1":
dist += i
if i == 0:
left += 1
else:
right += 1
arr = [dist]
for i in range(1, len(boxes)):
arr.append(arr[i-1] + left - right)
if boxes[i] == "1":
left += 1
right -= 1
return arr
boxes = "1101"
print(solve(boxes)) Đầu vào
"1101"
Đầu ra
[4, 3, 4, 5]