。ほとんどの石が同じ行または列で除去される

947。ほとんどの石が同じ行または列で削除されました

難易度: 中

トピック: ハッシュ テーブル、深さ優先検索、ユニオン検索、グラフ

2D 平面上で、いくつかの整数座標点に n 個の石を配置します。各座標点には最大 1 つの石を含めることができます。

石は、削除されていない別の石と同じ行または同じ列を共有している場合、削除できます。

長さ n の石の配列が与えられ、stones[i] = [xi, yi] が i ^番目 の石の位置を表す場合、 削除できる石の最大数を返します。 .

例 1:

• 入力: 石 = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
• 出力: 5
• 説明: 5 つの石を削除する 1 つの方法は次のとおりです。
  1. 石 [2,2] は [2,1] と同じ行を共有しているため、削除します。
  2. 石 [2,1] は [0,1] と同じ列を共有しているため、削除します。
  3. 石 [1,2] は [1,0] と同じ行を共有しているため、削除します。
  4. 石 [1,0] は [0,0] と同じ列を共有しているため、削除します。
  5. 石 [0,1] は [0,0] と同じ行を共有しているため、削除します。
  6. 石 [0,0] は、まだ平面上にある別の石と行/列を共有していないため、削除できません。

例 2:

• 入力: 石 = [[0,0],[0,2],[1,1],[2,0],[2,2]]
• 出力: 3
• 説明: 3 つの移動を行う 1 つの方法は次のとおりです。
  1. 石 [2,2] は [2,0] と同じ行を共有しているため、削除します。
  2. 石 [2,0] は [0,0] と同じ列を共有しているため、削除します。
  3. 石 [0,2] は [0,0] と同じ行を共有しているため、削除します。
  4. 石 [0,0] と [1,1] は、まだ平面上にある別の石と行/列を共有していないため、削除できません。

例 3:

• 入力: 石 = [[0,0]]
• 出力: 0
• 説明: [0,0] は平面上の唯一の石なので、削除できません。

制約:

• 1
• 0 i、y_i 4
• 同じ座標点に 2 つの石はありません。

解決策:

深さ優先検索 (DFS) アプローチを使用してソリューションを実装できます。このアイデアは、行または列によって接続されている石を、同じ接続されたコンポーネントの一部として考えることです。すべての接続コンポーネントを見つけたら、削除できる石の最大数は、石の合計数から接続コンポーネントの数を引いたものになります。

このソリューションを PHP で実装してみましょう: 947。同じ行または列で削除されたほとんどの石

<?php function removeStones($stones) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

function dfs($stoneIndex, &$stones, &$visited) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$stones1 = array(
    array(0, 0),
    array(0, 1),
    array(1, 0),
    array(1, 2),
    array(2, 1),
    array(2, 2)
);
echo removeStones($stones1); // Output: 5

$stones2 = array(
    array(0, 0),
    array(0, 2),
    array(1, 1),
    array(2, 0),
    array(2, 2)
);
echo removeStones($stones2); // Output: 3

$stones3 = array(
    array(0, 0)
);
echo removeStones($stones3); // Output: 0
?>

説明：

1. DFS 関数:

   • dfs 関数は、同じ接続コンポーネント内にあるすべての石を探索するために使用されます。ストーンが現在のストーンに (同じ行または列内で) 接続されている場合、そのストーンに対して DFS を再帰的に実行します。

2. メイン関数:

   • すべての石を反復処理し、まだ訪問されていない石ごとに DFS を実行して、同じ接続コンポーネント内のすべての石をマークします。
   • 接続されたコンポーネントの数を数えます。その結果は、石の合計数から接続されたコンポーネントの数を引いたものになります ($n - $numComponents)。

3. 実行例:

   • 最初の例では、5 つの石を削除できることが正しく検出され、1 つの石は削除できないことがわかります。

複雑：

• 時間計算量: ネストされたループと DFS トラバーサルによる O(n^2)。
• 空間の複雑さ: 訪問した石を保存するための O(n)。

このソリューションは、指定された制約内で効率的に機能するはずです。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が。ほとんどの石が同じ行または列で除去されるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。