将所有球移动到每个盒子的最少操作次数

在这个问题中，我们需要计算将所有球从多个盒子中移动到每个盒子所需的最小操作次数。目标是为每个盒子计算移动球到该盒子的总操作次数。

问题描述

• 输入: 一个字符串 boxes，其中每个字符是 '0' 或 '1'：
  • '1' 表示该位置有一个球。
  • '0' 表示该位置没有球。
• 输出: 一个数组，其中第 i 个元素表示将所有球移动到第 i 个盒子所需的操作次数。

操作次数定义

如果某个球在位置 j，要移动到位置 i，需要的操作次数是 |i - j|。
因此，对所有位置 j 有球的位置，我们需要将 |i - j| 累加。

示例

示例 1:

输入:
boxes = "110"
输出:
[1, 1, 3]

解释:

• 移动到第 0 个盒子：1 次操作
  （从位置 1 移动到位置 0，+1）
• 移动到第 1 个盒子：1 次操作
  （从位置 0 移动到位置 1，+1）
• 移动到第 2 个盒子：3 次操作
  （从位置 0 到 2，+2，从位置 1 到 2，+1，合计 3）

示例 2:

输入:
boxes = "001011"
输出:
[11, 8, 5, 4, 3, 4]

算法实现

为了解决问题，可以采用两种主要方法：暴力法和优化方法。

方法 1: 暴力法

对每个位置 i，计算到所有球的距离总和。

• 时间复杂度：O(n²)
• 实现如下：

def minOperations(boxes: str) -> list[int]:
    n = len(boxes)
    result = []
    for i in range(n):
        total_moves = 0
        for j in range(n):
            if boxes[j] == '1':
                total_moves += abs(i - j)
        result.append(total_moves)
    return result

方法 2: 优化方法

通过一次从左到右和一次从右到左的扫描，减少重复计算。

1. 从左到右计算累积操作次数：
   • 记录左边球的数量和操作次数。
2. 从右到左计算累积操作次数：
   • 记录右边球的数量和操作次数。

• 时间复杂度：O(n)
• 实现如下：

def minOperations(boxes: str) -> list[int]:
    n = len(boxes)
    result = [0] * n
    count = 0
    ops = 0

    # 从左到右计算
    for i in range(n):
        result[i] += ops
        count += int(boxes[i])
        ops += count

    count = 0
    ops = 0

    # 从右到左计算
    for i in range(n - 1, -1, -1):
        result[i] += ops
        count += int(boxes[i])
        ops += count

    return result

优化方法示例分析

输入: boxes = "110"

1. 从左到右:

   • 初始 result = [0, 0, 0]
   • 遍历第 0 个盒子，count=1, ops=1, 更新 result=[0, 1, 0]
   • 遍历第 1 个盒子，count=2, ops=3, 更新 result=[0, 1, 3]

2. 从右到左:

   • 初始 result = [0, 1, 3]
   • 遍历第 2 个盒子，count=0, ops=0, 更新 result=[0, 1, 3]
   • 遍历第 1 个盒子，count=1, ops=1, 更新 result=[0, 1, 1]
   • 遍历第 0 个盒子，count=2, ops=3, 更新 result=[1, 1, 3]

输出: [1, 1, 3]

总结

1. 暴力法适合理解问题的核心，适用于小规模数据。
2. 优化方法在处理大规模数据时高效，可通过线性时间解决问题。