在Python中寻找移动所有球到每个盒子所需最少操作次数的程序
假设我们有一个名为boxes的二进制字符串,其中boxes[i]为’0’表示第i个盒子为空,而’1’表示它包含一个球。现在,我们可以在一个操作中将一个球从一个盒子移动到相邻的盒子。这样做后,有些盒子中可能有多个球。我们必须找到大小为n的数组答案,其中答案[i]是将所有球移动到第i个盒子所需的最小操作次数。
因此,如果输入是boxes = “1101”,则输出将为[4,3,4,5]
- 要将所有球放在第一个盒子中,我们必须在第一个操作中从第二个盒子取一个球,第三个操作中从最后一个盒子取一个球,因此总共需要4个操作。
-
要将所有球放在第二个盒子中,我们必须在第一个操作中从第一个盒子取一个球,在第二个操作中从最后一个盒子取一个球,因此总共需要3个操作。
-
要将所有球放在第三个盒子中,我们必须在第一个操作中从第二个盒子取一个球并从最后一个盒子取一个球,在第二个操作中从第一个盒子取两个球,因此总共需要4个操作。
-
要将所有球放在最后一个盒子中,我们必须在第一个操作中从第一个盒子取三个球,在第二个操作中从第二个盒子取两个球,因此总共需要5个操作。
要解决这个问题,我们将遵循以下步骤-
- left := 0,right := 0,dist := 0
-
for i in range 0 to size of boxes – 1, do
- 如果boxes[i]和“1”相同,则
- dist := dist + i
-
如果i等于0,则
-
left := left + 1
-
否则,
-
right := right + 1
- 如果boxes[i]和“1”相同,则
-
arr :=列表,最初将dist放入其中
-
for i in range 1 to size of boxes – 1, do
- 将arr[i-1] + left – right插入到arr的末尾
-
如果boxes[i]和“1”相同,则
- left := left + 1
-
right := right – 1
-
返回arr
示例
让我们看下面的实现以更好地理解-
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))
输入
"1101"
输出
[4, 3, 4, 5]