![. Most Stones Removed with Same Row or Column](https://img.php.cn/upload/article/000/000/000/172497106529050.jpg)
947。同一行或同一列移除的大部分石頭
難度:中
主題:雜湊表、深度優先搜尋、並集查找、圖
在 2D 平面上,我們將 n 個石頭放置在一些整數座標點。每個座標點最多可以有一顆石頭。
如果一塊石頭與另一塊尚未移除的石頭同一行或同一列,則可以將其移除。
給定一個長度為n 的石頭數組,其中stones[i] = [xi, yi] 表示第i第個石頭的位置,返回可以移除的最大可能數量的石頭.
範例1:
- 輸入:石頭 = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
- 輸出:5
- 說明:移除 5 顆石頭的一種方法如下:
- 移除石頭 [2,2],因為它與 [2,1] 共用同一行。
- 移除石頭 [2,1],因為它與 [0,1] 共用同一列。
- 移除石頭 [1,2],因為它與 [1,0] 共用同一行。
- 移除石頭 [1,0],因為它與 [0,0] 共用同一列。
- 移除石頭 [0,1],因為它與 [0,0] 共用同一行。
- 石頭 [0,0] 無法移除,因為它不與平面上的另一塊石頭共用行/列。
範例2:
- 輸入:石頭 = [[0,0],[0,2],[1,1],[2,0],[2,2]]
- 輸出:3
- 說明:進行 3 步驟的一種方法如下:
- 移除石頭 [2,2],因為它與 [2,0] 共用同一行。
- 移除石頭 [2,0],因為它與 [0,0] 共用同一列。
- 移除石頭 [0,2],因為它與 [0,0] 共用同一行。
- 棋子 [0,0] 和 [1,1] 無法移除,因為它們不會與平面上的另一個棋子共用行/列。
範例 3:
- 輸入:石頭 = [[0,0]]
- 輸出:0
- 解釋:[0,0] 是平面上唯一的石頭,所以你無法移除它。
約束:
- 1
- 0 i, yi4
- 沒有兩塊石頭位於同一座標點。
解:
我們可以使用深度優先搜尋(DFS)方法來實現該解決方案。這個想法是將透過行或列連接的石頭視為同一連接組件的一部分。一旦找到所有連通分量,可以移除的最大石子數量就是石子總數減去連通分量的數量。
讓我們用 PHP 實作這個解決方案:947。同一行或同一列移除的大部分石頭
雷雷
解釋:
DFS 函數:
- dfs 函數用於探索同一連通分量中的所有石子。如果一塊石頭與目前石頭相連(在同一行或同一列),我們會遞歸地對該石頭執行 DFS。
主要功能:
- 我們迭代所有的石頭,對於每一個沒有被訪問過的石頭,我們執行 DFS 來標記同一個連接組件中的所有石頭。
- 我們計算連通分量的數量,結果是石子總數減去連通分量的數量($n - $numComponents)。
執行範例:
- 對於第一個範例,它正確地發現 5 個石頭可以被移除,剩下 1 個石頭無法移除。
複雜:
- 時間複雜度:由於巢狀迴圈和 DFS 遍歷,O(n^2)。
- 空間複雜度:儲存造訪過的石頭的時間複雜度為 O(n)。
該解決方案應該在給定的限制內有效地工作。
聯絡連結
如果您發現本系列有幫助,請考慮在 GitHub 上給存儲庫一個星號或在您最喜歡的社交網絡上分享該帖子? 。您的支持對我來說意義重大!
如果您想要更多類似的有用內容,請隨時關注我:
以上是。同一行或同一列移除的大部分石頭的詳細內容。更多資訊請關注PHP中文網其他相關文章!