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

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

难度：中等

主题：数组、字符串、前缀和

你有n个盒子。给定一个长度为 n 的二进制字符串 box，其中，如果第 i^th 框为 空，则 box[i] 为“0”，如果包含 ，则为“1”一个球。

在一次操作中，您可以将一个个球从一个盒子移动到相邻的盒子。如果abs(i - j) == 1，则盒子 i 与盒子 j 相邻。请注意，这样做后，某些盒子中可能会有多个球。

返回大小为n的数组答案，其中answer[i]是将所有球移动到第i第个盒子所需的^最小操作次数.

每个答案[i]都是根据盒子的初始状态计算的。

示例1：

• 输入：框=“110”
• 输出： [1,1,3]
• 说明：每个方框的答案如下：
  1. 第一个盒子：您必须在一次操作中将一个球从第二个盒子移动到第一个盒子。
  2. 第二个盒子：您必须在一次操作中将一个球从第一个盒子移动到第二个盒子。
  3. 第三个盒子：您需要通过两次操作将一个球从第一个盒子移动到第三个盒子，并通过一次操作将一个球从第二个盒子移动到第三个盒子。

示例2：

• 输入：框=“001011”
• 输出： [11,8,5,4,3,4]

约束：

• n == box.length
• 1
• box[i] 为“0”或“1”。

提示：

1. 如果你想将球从 i 框移动到 j 框，你需要进行 abs(i-j) 移动。
2. 要将所有球移动到某个盒子中，您可以将它们一个接一个地移动。
3. 对于每个框 i，迭代框 j 中的每个球，并将 abs(i-j) 添加到answers[i]。

解决方案：

我们可以使用前缀和方法来计算将所有球移动到每个盒子所需的最小操作数，而无需显式模拟每个操作。

主要观察结果：

1. 将球从 i 框移动到 j 框所需的移动次数就是abs(i - j)。
2. 我们可以利用球的位置和操作总数来计算将所有球移动到特定盒子的总移动次数。
3. 通过计算从左到右和从右到左的移动，我们可以在两遍中确定结果。

方法：

1. 从左到右传球：在此传球中，计算从左侧开始将所有球带到当前盒子的移动次数。
2. 从右到左传球：在此传球中，计算从右侧开始将所有球带到当前盒子的移动次数。
3. 合并两次传递的结果以获得每个框的最终结果。

解决步骤：

1. 首先迭代盒子字符串并计算每个盒子左侧和右侧有多少个球。
2. 在迭代过程中，使用左右信息计算将所有球带到当前盒子所需的移动次数。

让我们用 PHP 实现这个解决方案：1769。将所有球移动到每个盒子的最少操作次数

<?php
/**
 * @param String $boxes
 * @return Integer[]
 */
function minOperations($boxes) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$boxes = "110";
print_r(minOperations($boxes)); // Output: [1,1,3]

$boxes = "001011";
print_r(minOperations($boxes)); // Output: [11,8,5,4,3,4]
?>

解释：

1. 从左向右传球：我们计算将所有球从左侧带到当前盒子所需的操作总数。对于找到的每个球（“1”），我们更新移动总数。
2. 从右到左传球：与从左到右传球类似，但是我们计算将球从右侧移动到当前盒子的操作次数。
3. 每个方块的操作总数是左右遍的移动次数之和。

演练示例：

示例1：

$boxes = "110";
print_r(minOperations($boxes));

输出:

Array
(
    [0] => 1
    [1] => 1
    [2] => 3
)

示例2：

$boxes = "001011";
print_r(minOperations($boxes));

输出:

Array
(
    [0] => 11
    [1] => 8
    [2] => 5
    [3] => 4
    [4] => 3
    [5] => 4
)

时间复杂度：

• 该解决方案运行时间为 O(n)，因为我们对框字符串进行了两次迭代（一次用于从左到右的传递，一次用于从右到左的传递）。
• 空间复杂度为 O(n)，因为我们存储答案数组来保存结果。

该解决方案使用前缀和技术有效地计算每个框的最小操作数。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是将所有球移动到每个盒子的最少操作次数的详细内容。更多信息请关注PHP中文网其他相关文章！