將所有球移動到每個盒子的最少操作次數

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中文網其他相關文章！