leetcode130. Surrounded Regions

focusj 發布于2019-08-16 10:45 / 1754人閱讀

摘要：將所有和邊界相連的都標記出來。那么當我重新遍歷數組的時候，剩下的則是被完全包圍的。

題目要求

Given a 2D board containing "X" and "O" (the letter O), capture all regions surrounded by "X".

A region is captured by flipping all "O"s into "X"s in that surrounded region.

For example,
X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

將所有被X環繞的O區域獲取出來并轉化為X

思路與代碼

這篇題目與leetcode200. Number of Islands思路非常相近，建議毫無思路的同學先參考一下這篇博客。其實這種將區域相連的題目往往都可以使用深度優先遍歷或者是Union-Find方法來實現。在這里我就給出深度優先遍歷的實現方法，有興趣的同學可以參考上文的博客來自己實現Union-Find方法。

和leetcode200題不同，在本題中，只有被完全包圍的圖形才可以被選中與轉化，也就是，任何一個和數組邊界上的O相連的都不可能是完全包圍。所以在這題里我們采用逆向思維。將所有和邊界O相連的O都標記出來。那么當我重新遍歷數組的時候，剩下的O則是被完全包圍的。

代碼如下：

    public void solve(char[][] board) {
        if(board.length<=2 || board[0].length<=2 ) return;
        int row = board.length;
        int column = board[0].length;
        for(int i = 0 ; i=board.length || j>=board[0].length) return;
        if(board[i][j] == "X" || board[i][j]=="*") return;
        board[i][j] = "*";
        if(i>1 && board[i-1][j]=="O") boundarySearch(board, i-1, j);
        if(j>1 && board[i][j-1]=="O") boundarySearch(board, i, j-1);
        if(i

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 Regions Surrounded 130美元 cdn130

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/70403.html

[Leetcode] Surrounded Regions 找出被包圍的區域

摘要：原題鏈接邊緣搜索替換法復雜度時間空間思路從矩陣的四條邊上的點作為起點，搜索連續的一塊區域上值為的點并賦為一個臨時變量。對四條邊上所有點都進行過這個步驟后，矩陣內剩余的就是被包圍的。 Surrounded Regions Given a 2D board containing X and O, capture all regionssurrounded by X. A region i...

miguel.jiang 2019-08-14 16:10 評論0 收藏0
[LintCode] Surrounded Regions

摘要：先用處理左右邊界上的換成再用處理上下邊界除去四角的換成把剩下的沒有被處理過，也就是被包圍的置為把所有暫時置為的不被包圍的換回如當前字符的坐標越界不是，返回是的都置為，然后迭代其上下左右各點 Problem Given a 2D board containing X and O, capture all regions surrounded by X.A region is captur...

Labradors 2019-08-14 15:11 評論0 收藏0
Leetcode之Union-Find(并查集)

摘要：并查集包括查詢和聯合，主要使用不相交集合查詢主要是用來決定不同的成員是否在一個子集合之內聯合主要是用來把多個子集合成一個集合的實際運用計算機網絡檢查集群是否聯通電路板檢查不同的電路元件是否聯通初始化聯通與檢測與是否聯通返回聯通的數并查集(Union-Find)包括查詢(Find)和聯合(Union)，主要使用不相交集合(Disjoint-Sets)查詢(Find)主要是用來決定不同的...

roland_reed 2019-08-15 13:44 評論0 收藏0
【LC總結】Union Find系列(Num of Islands I&II/Graph V

摘要：不得不說，對于這道題而言，是一種很木訥的模板。主函數按矩陣大小建立一個類進行后續操作一個結點用來連接邊角不可能被圍繞的一個函數對矩陣元素進行結點線性化。同理，，，在主函數中初始化后調用。 Surrounded Regions Problem Given a 2D board containing X and O (the letter O), capture all regions s...

bergwhite 2019-08-14 15:51 評論0 收藏0
leetcode200. Number of Islands

摘要：題目要求提供一個二維數組表示一張地圖，其中代表陸地，代表海洋。這里使用一個新的二維數組來表示對應地圖上的元素屬于哪個并查集。在合并的時候先進行判斷，如果二者為已經相連的陸地，則無需合并，否則將新的二維數組上的元素指向所在的并查集。題目要求 Given a 2d grid map of 1s (land) and 0s (water), count the number of isla...

Zoom 2019-08-16 10:45 評論0 收藏0