摘要:原題鏈接邊緣搜索替換法復雜度時間空間思路從矩陣的四條邊上的點作為起點,搜索連續的一塊區域上值為的點并賦為一個臨時變量。對四條邊上所有點都進行過這個步驟后,矩陣內剩余的就是被包圍的。
Surrounded Regions
Given a 2D board containing "X" and "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 XAfter running your function, the board should be:
X X X X X X X X X X X X X O X X
原題鏈接
邊緣搜索替換法 復雜度時間 O(MN) 空間 O(MN)
思路從矩陣的四條邊上的點作為起點,搜索連續的一塊區域上值為O的點并賦為一個臨時變量。這里我們用BFS或DFS進行搜索。對四條邊上所有點都進行過這個步驟后,矩陣內剩余的O就是被包圍的O。此時再對所有點遍歷一遍,將臨時變量賦回O,而剩余的O則賦為X。
注意用隊列實現BFS時,賦臨時變量B時要在將周邊點加入隊列時就賦值,減少while循環的次數,否則Leetcode會超時
代碼廣度優先 BFS
public class Solution { public void solve(char[][] board) { for(int i = 0; i < board.length; i++){ for(int j = 0; j < board[0].length; j++){ if((i == 0 || j == 0 || i == board.length - 1 || j == board[0].length - 1) && (board[i][j]=="O")){ Queueq = new LinkedList (); q.offer(i * board[0].length + j); board[i][j] = "B"; while(!q.isEmpty()){ Integer key = q.poll(); int x = key / board[0].length; int y = key % board[0].length; if(x > 0 && board[x-1][y]=="O"){ q.offer((x-1) * board[0].length + y); board[x-1][y] = "B"; } if(x < board.length - 1 && board[x+1][y]=="O"){ q.offer((x+1) * board[0].length + y); board[x+1][y] = "B"; } if(y > 0 && board[x][y-1]=="O"){ q.offer(x * board[0].length + y - 1); board[x][y-1] = "B"; } if(y < board[0].length - 1 && board[x][y+1]=="O"){ q.offer(x * board[0].length + y + 1); board[x][y+1] = "B"; } } } } } for(int i = 0; i < board.length; i++){ for(int j = 0; j < board[0].length; j++){ if(board[i][j]=="O") board[i][j]="X"; if(board[i][j]=="B") board[i][j]="O"; } } } }
深度優先 DFS
public class Solution { static class Pair { public int first; public int second; public Pair(int f, int s) { first = f; second = s; } } public void solve(char[][] board) { if(board == null || board.length == 0) { return ; } for(int i = 0; i < board[0].length; ++i) { if(board[0][i] == "O") { markUnflippable(board,0,i); } } for(int i = 0; i < board[board.length-1].length; ++i) { if(board[board.length-1][i] == "O") { markUnflippable(board,board.length-1,i); } } for(int i = 0 ; i < board.length; ++i) { if(board[i][0] == "O") { markUnflippable(board,i,0); } } for(int i =0; i < board.length; ++i) { if(board[i][board[i].length-1] == "O") { markUnflippable(board,i,board[i].length-1); } } // modify the board for(int i = 0; i < board.length; ++i) { for(int j = 0; j < board[i].length; ++j) { if(board[i][j] == "O") { board[i][j] = "X"; } else if(board[i][j] == "U") { board[i][j] = "O"; } } } } public void markUnflippable(char[][] board, int r, int c) { int[] dirX = {-1,0,1,0}; int[] dirY = {0,1,0,-1}; ArrayDequestack = new ArrayDeque<>(); stack.push(new Pair(r,c)); while(!stack.isEmpty()) { Pair p = stack.pop(); board[p.first][p.second] = "U"; for(int i = 0; i < dirX.length; ++i) { if(p.first + dirX[i] >= 0 && p.first + dirX[i] < board.length && p.second + dirY[i] >= 0 && p.second +dirY[i] < board[p.first + dirX[i]].length && board[p.first+dirX[i]][p.second+dirY[i]] == "O") { stack.push(new Pair(p.first+dirX[i],p.second+dirY[i])); } } } } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66156.html
摘要:先用處理左右邊界上的換成再用處理上下邊界除去四角的換成把剩下的沒有被處理過,也就是被包圍的置為把所有暫時置為的不被包圍的換回如當前字符的坐標越界不是,返回是的都置為,然后迭代其上下左右各點 Problem Given a 2D board containing X and O, capture all regions surrounded by X.A region is captur...
摘要:將所有和邊界相連的都標記出來。那么當我重新遍歷數組的時候,剩下的則是被完全包圍的。 題目要求 Given a 2D board containing X and O (the letter O), capture all regions surrounded by X. A region is captured by flipping all Os into Xs in that s...
摘要:題目地址題目描述給定一個二維的矩陣,包含和字母。找到所有被圍繞的區域,并將這些區域里所有的用填充。示例運行你的函數后,矩陣變為解答就是找所有被圍繞的區域,然后填充是輕而易舉的事情。利用進行連通性構建做一個位置映射 題目地址:https://leetcode-cn.com/probl...題目描述:給定一個二維的矩陣,包含 X 和 O(字母 O)。 找到所有被 X 圍繞的區域,并將這些區...
摘要:并查集包括查詢和聯合,主要使用不相交集合查詢主要是用來決定不同的成員是否在一個子集合之內聯合主要是用來把多個子集合成一個集合的實際運用計算機網絡檢查集群是否聯通電路板檢查不同的電路元件是否聯通初始化聯通與檢測與是否聯通返回聯通的數 并查集(Union-Find)包括查詢(Find)和聯合(Union),主要使用不相交集合(Disjoint-Sets)查詢(Find)主要是用來決定不同的...
摘要:不得不說,對于這道題而言,是一種很木訥的模板。主函數按矩陣大小建立一個類進行后續操作一個結點用來連接邊角不可能被圍繞的一個函數對矩陣元素進行結點線性化。同理,,,在主函數中初始化后調用。 Surrounded Regions Problem Given a 2D board containing X and O (the letter O), capture all regions s...
閱讀 363·2024-11-06 13:38
閱讀 738·2024-09-10 13:19
閱讀 866·2024-08-22 19:45
閱讀 1363·2021-11-19 09:40
閱讀 2598·2021-11-18 13:14
閱讀 4266·2021-10-09 10:02
閱讀 2285·2021-08-21 14:12
閱讀 1268·2019-08-30 15:54