移动所有球到每个盒子所需的最小操作数

标签: 数组 字符串

难度: Medium

有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ，其中 boxes[i] 的值为 '0' 表示第 i 个盒子是 空 的，而 boxes[i] 的值为 '1' 表示盒子里有 一个 小球。

在一步操作中，你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == 1 。注意，操作执行后，某些盒子中可能会存在不止一个小球。

返回一个长度为 n 的数组 answer ，其中 answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数。

每个 answer[i] 都需要根据盒子的 初始状态 进行计算。

 

示例 1：

输入：boxes = "110"
输出：[1,1,3]
解释：每个盒子对应的最小操作数如下：
1) 第 1 个盒子：将一个小球从第 2 个盒子移动到第 1 个盒子，需要 1 步操作。
2) 第 2 个盒子：将一个小球从第 1 个盒子移动到第 2 个盒子，需要 1 步操作。
3) 第 3 个盒子：将一个小球从第 1 个盒子移动到第 3 个盒子，需要 2 步操作。将一个小球从第 2 个盒子移动到第 3 个盒子，需要 1 步操作。共计 3 步操作。

示例 2：

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

 

提示：

  • n == boxes.length
  • 1 <= n <= 2000
  • boxes[i] 为 '0' 或 '1'

Submission

运行时间: 93 ms

内存: 0.0 MB

class Solution:
    def minOperations(self, boxes: str) -> List[int]:

        left, right = 0, 0
        l = [[0] * 2 for i in range(len(boxes))]

        for i in range(len(boxes)):
            if boxes[i] == "1": left += 1
            if boxes[-i-1] == "1": right += 1
            l[i][0] = left
            l[-i-1][1] = right

        output = [0 for i in range(len(boxes))]

        first = 0
        for i in range(len(l)-1, -1, -1):
            left, right = l[i]
            first += int(boxes[i]) * i
        
        output[0] = first

        for i in range(1, len(l)):
            left, right = l[i]
            if boxes[i] == "1":
                output[i] = output[i-1] - right + left - 1
            else:
                output[i] = output[i-1] - right + left
        
        return output

Explain

该题解使用了动态规划和前缀和的概念。首先，通过两次遍历，计算每个位置左侧和右侧的球数，这些值存储在二维数组l中。接着，利用这些预计算的球数，计算移动所有球到每个盒子的最小操作数。具体来说，第一次遍历计算了到最左边盒子的操作数，之后的每个盒子操作数通过上一个盒子的操作数来计算，更新时考虑从左侧和右侧移动球的操作数差异。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minOperations(self, boxes: str) -> List[int]:

        # 初始化左右球的计数
        left, right = 0, 0
        l = [[0] * 2 for i in range(len(boxes))]

        # 预计算每个位置的左侧和右侧球数
        for i in range(len(boxes)):
            if boxes[i] == '1': left += 1
            if boxes[-i-1] == '1': right += 1
            l[i][0] = left
            l[-i-1][1] = right

        output = [0 for i in range(len(boxes))]

        # 计算移动到最左边盒子的最小操作数
        first = 0
        for i in range(len(l)-1, -1, -1):
            left, right = l[i]
            first += int(boxes[i]) * i
        
        output[0] = first

        # 从左到右计算每个盒子的最小操作数
        for i in range(1, len(l)):
            left, right = l[i]
            if boxes[i] == '1':
                output[i] = output[i-1] - right + left - 1
            else:
                output[i] = output[i-1] - right + left
        
        return output

Explore

题解中通过从左到右和从右到左两次遍历字符串来确定每个盒子的左侧和右侧球数。在每次遍历中，如果盒子中有球（即字符为'1'），则相应的左侧或右侧球数计数器会递增。这种方法确保了无论球在字符串中的位置如何，都能正确计算每个盒子左右的球数。两次遍历确保了对所有位置的全面覆盖，包括在字符串两端的边界情况。

前缀和通常用于快速计算数组中一段元素的和。在这个题解中，通过计算到每个盒子为止的从左侧和右侧的球的总数（即前缀和），可以快速得出将所有球移动到任一盒子所需的总步数。具体到每个盒子，利用之前计算的左侧和右侧球数的前缀和，可以轻松计算出将所有左侧球移至该盒子和所有右侧球移至该盒子的操作次数。这种方法大大减少了重复计算，提高了效率。

从最左边盒子开始初始化操作数是因为这样可以逐渐累加向右的移动成本，这种方法可以有效利用动态规划思想，避免重复计算每个盒子的操作数。从最左边开始然后向右逐盒累计调整，可以保证每次更新只需要考虑当前盒子与前一个盒子的关系，从而降低总体计算复杂度。这种方法在处理此类累积和问题时通常是最优的，因为它能够以线性的时间复杂度处理问题。

这个公式是基于动态规划的思想来更新每个盒子的操作数。当当前盒子i中有球（即`boxes[i] == '1'`），则需要调整前一个盒子的操作数来计算当前盒子的操作数。具体来说，`output[i-1] - right`部分表示从前一个盒子到当前盒子，所有右侧的球都少移动了一步，而`+ left`部分表示所有左侧的球都多移动了一步。由于当前盒子i有球，它自身的位置也要计入操作数，因此公式中有`-1`来减去这一球原本位置的计数，因为它现在无需移动。