通信するサーバーの数を数える

1267年。通信するサーバーを数える

難易度: 中

トピック: 配列、深さ優先検索、幅優先検索、和集合検索、行列、カウント

m * n 整数行列グリッドとして表されるサーバー センターのマップが与えられます。1 はそのセル上にサーバーがあることを意味し、0 はサーバーがないことを意味します。 2 つのサーバーは、同じ行または同じ列にある場合に通信するといわれています。

他のサーバーと通信するサーバーの数を返します。

例 1:

• 入力: グリッド = [[1,0],[0,1]]
• 出力: 0
• 説明: どのサーバーも他のサーバーと通信できません。

例 2:

• 入力: グリッド = [[1,0],[1,1]]
• 出力: 3
• 説明: 3 つのサーバーはすべて、少なくとも 1 つの他のサーバーと通信できます。

例 3:

• 入力: グリッド = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1] ]
• 出力: 4
• 説明: 最初の行の 2 つのサーバーは相互に通信できます。 3 列目の 2 つのサーバーは相互に通信できます。右下隅のサーバーは他のサーバーと通信できません。

制約:

• m == グリッドの長さ
• n == グリッド[i].length
• 1
• 1
• グリッド[i][j] == 0 または 1

ヒント:

1. 各行と列にコンピュータの番号を格納します。
2. 分離されていないすべてのサーバーをカウントします。

解決策:

次の手順に従います:

アプローチ：

1. 各行と列のサーバー数を数える:

   • グリッドを走査し、各行と各列に存在するサーバーの数を計算します。これは、2 つの配列 rowCount とcolCount を使用して実行できます。
     • rowCount[i] には、行 i のサーバーの数が格納されます。
     • ColCount[j] は列 j にサーバーの数を格納します。

2. 通信をチェック:

   • グリッド内の各サーバーについて、rowCount とcolCount を確認して、他のサーバーと通信できるかどうかを確認します。どちらかが 1 より大きい場合、サーバーは他のサーバーと通信できます。

3. 通信するサーバーを数える:

   • グリッドを再度横断し、各サーバー (値 1 のセル) について、複数のサーバーが存在する行または列に属しているかどうかを確認します。

このソリューションを PHP で実装してみましょう: 1267。通信するサーバーを数える

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

// Test the function with the provided examples
$grid1 = [[1, 0], [0, 1]];
$grid2 = [[1, 0], [1, 1]];
$grid3 = [[1, 1, 0, 0], [0, 0, 1, 0], [0, 0, 1, 0], [0, 0, 0, 1]];

echo countServers($grid1) . "\n"; // Output: 0
echo countServers($grid2) . "\n"; // Output: 3
echo countServers($grid3) . "\n"; // Output: 4
?>

説明：

1. 行と列でサーバーを数える:

   • グリッドを反復処理し、各行と各列にサーバー (つまり 1) の数を数えます。これらのカウントを rowCount 配列とcolCount 配列に保存します。

2. 通信サーバーの識別:

   • カウント後、各サーバー (値 1 のセル) を反復処理します。サーバーは、その行のサーバー数 (rowCount[i] > 1) またはその列のサーバー数 (colCount[j] > 1) が 1 より大きい場合、他のサーバーと通信できます。その後、結果をインクリメントします。通信する各サーバーのカウンター。

3. 出力:

   • この関数は、他のサーバーと通信できるサーバーの総数を返します。

時間計算量:

• O(m * n)、ここで、m は行数、n は列数です。これは、グリッドを 2 回反復処理するためです。1 回目は行と列でサーバーをカウントし、もう 1 回目は通信をチェックします。

このソリューションは、指定された制約内で問題を効率的に処理します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が通信するサーバーの数を数えるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。