。同一行或同一列移除的大部分石頭

947。同一行或同一列移除的大部分石頭

難度：中

主題：雜湊表、深度優先搜尋、並集查找、圖

在 2D 平面上，我們將 n 個石頭放置在一些整數座標點。每個座標點最多可以有一顆石頭。

如果一塊石頭與另一塊尚未移除的石頭同一行或同一列，則可以將其移除。

給定一個長度為n 的石頭數組，其中stones[i] = [xi, yi] 表示第i^第 個石頭的位置，返回可以移除的最大可能數量的石頭.

範例1：

• 輸入： 石頭 = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
• 輸出： 5
• 說明：移除 5 顆石頭的一種方法如下：
  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. 移除石頭 [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
• 沒有兩塊石頭位於同一座標點。

解：

我們可以使用深度優先搜尋（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 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。同一行或同一列移除的大部分石頭的詳細內容。更多資訊請關注PHP中文網其他相關文章！