Cho chuỗi nhị phân boxes, '0' = hộp trống, '1' = có 1 bóng. Một phép: di chuyển 1 bóng sang hộp kề. Tìm mảng answer[n], answer[i] = số phép tối thiểu đưa tất cả bóng vào hộp i.
Ví dụ: boxes = "1101", đầu ra = [4, 3, 4, 5].
- Hộp 0: từ hộp 1 (1 phép) + hộp 3 (3 phép) = 4
- Hộp 1: từ hộp 0 (1) + hộp 3 (2) = 3
- Hộp 2: từ hộp 1 (1) + hộp 3 (1) + hộp 0 (2) = 4
- Hộp 3: từ hộp 0 (3) + hộp 1 (2) = 5
Giải pháp
Tính trước tổng khoảng cách đến hộp 0, sau đó lan truyền:
- left := 0, right := 0, dist := 0
- Với i từ 0 đến n-1: nếu boxes[i]=='1': dist += i; nếu i==0: left++ else: right++
- arr := [dist]
- Với i từ 1 đến n-1:
- arr.append(arr[i-1] + left - right)
- Nếu boxes[i]=='1': left++; right--
- Trả về arr
Ví dụ minh họa
Xem 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]