すべてのボールを各ボックスに移動するための最小操作数

1769年。すべてのボールを各ボックスに移動するための最小操作数

難易度: 中

トピック: 配列、文字列、プレフィックス合計

n 個のボックスがあります。長さ n のバイナリ文字列ボックスが与えられます。ここで、ボックス[i]は、i^番目ボックスが空の場合は「0」、ボックスにが含まれている場合は「1」になります。 ボール 1 つ。

1 回の操作で、1 個 個のボールをボックスから隣接するボックスに移動できます。 abs(i - j) == 1 の場合、ボックス i はボックス j に隣接します。そうした後、一部のボックスに複数のボールが存在する可能性があることに注意してください。

サイズ n の配列回答 を返します。ここで、answer[i] は、すべてのボールを i 番目 ボックスに移動するのに必要な ^最小 操作数です.

各答え[i]は、ボックスの初期状態を考慮して計算されます。

例 1:

• 入力: ボックス = "110"
• 出力: [1,1,3]
• 説明: 各ボックスの答えは次のとおりです。
  1. 最初のボックス: 1 回の操作で 2 番目のボックスから 1 個のボールを最初のボックスに移動する必要があります。
  2. 2 番目のボックス: 1 回の操作で 1 つのボールを最初のボックスから 2 番目のボックスに移動する必要があります。
  3. 3 番目のボックス: 1 つのボールを 2 回の操作で最初のボックスから 3 番目のボックスに移動し、1 つのボールを 2 番目のボックスから 3 番目のボックスに 1 回の操作で移動する必要があります。

例 2:

• 入力: ボックス = "001011"
• 出力: [11,8,5,4,3,4]

制約:

• n == box.length
• 1
• box[i] は '0' または '1' です。

ヒント:

1. ボールをボックス i からボックス j に移動したい場合は、abs(i-j) の移動が必要です。
2. すべてのボールをボックスに移動するには、ボールを 1 つずつ移動します。
3. 各ボックス i について、ボックス j 内の各ボールを反復処理し、abs(i-j) をanswer[i]に追加します。

解決策:

接頭辞合計 アプローチを使用すると、各操作を明示的にシミュレートせずに、すべてのボールを各ボックスに移動するのに必要な最小操作数を計算できます。

主な所見:

1. ボールをボックス i からボックス j に移動するのに必要な手数は、単純に abs(i - j) です。
2. ボールの位置と操作の累計を利用して、すべてのボールを特定のボックスに移動するための総移動数を計算できます。
3. 左から右へ、および右から左への動きを計算することで、2 回のパスで結果を決定できます。

アプローチ：

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
)

時間計算量:

• ボックス文字列を 2 回 (左から右へのパスで 1 回、右から左へのパスで 1 回) 反復処理するため、ソリューションは O(n) 時間で実行されます。
• 結果を保持するために回答配列を保存するため、空間計算量は O(n) です。

このソリューションは、プレフィックス合計手法を使用して各ボックスの最小演算数を効率的に計算します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がすべてのボールを各ボックスに移動するための最小操作数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。