这题leetcode设的memory好紧... 最后把recursion换成iterative做才过..
还有BFS忘了track visited loop 搞了很久
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| public class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) return;
for (int i = 0; i < board.length; i++){
if (board[i][0] == 'O') filpEdgeRegionToOne(board, i, 0);
if (board[i][board[0].length-1] == 'O') filpEdgeRegionToOne(board, i, board[0].length-1);
}
for (int i = 0; i < board[0].length; i++){
if (board[0][i] == 'O') filpEdgeRegionToOne(board, 0, i);
if (board[board.length-1][i] == 'O') filpEdgeRegionToOne(board, board.length-1, i);
}
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';
else if (board[i][j] == '1')
board[i][j] = 'O';
}
}
}
void filpEdgeRegionToOne(char[][]board, int i, int j){
int dirs[][] = {{1,0},{-1,0},{0,1},{0,-1}};
Queue<int[]> queue = new LinkedList<int[]>();
queue.add(new int[]{i,j});
while (!queue.isEmpty()){
int []location = queue.poll();
if (board[location[0]][location[1]] == 'O'){
board[location[0]][location[1]] = '1';
for (int k = 0; k < dirs.length; k++){
int x = location[0]+dirs[k][0];
int y = location[1]+dirs[k][1];
if (checkValid(board, x, y)) queue.add(new int[]{x,y});
}
}
}
}
boolean checkValid(char[][] board, int i, int j){
return !(i < 0 || i >= board.length ||
j < 0 || j >= board[i].length ||
board[i][j] == 'X' || board[i][j] == '1');
}
}
|
No comments:
Post a Comment