三刷 06/2022
Version #4 BFS from surround regions
这个写法坑比较多，但是硬写出来了，不推荐
还是推荐之前比较巧妙的写法
不过这个写法自己硬写出来了还是证明现在implement的能力提高了
看了之前的写法可以通过从border向里面traverse的方法，就很简单
我自己的写法是先bfs一遍如果bfs的过程中遇到了出界就返回false，如果没有遇到出界就返回true然后再bfs一遍进行flip
这里一个bug就是不能一遇到出界就立刻返回，这样会造成一部分点visited而一部分点没有visited，那些没有visited的点就会被后续的bfs traverse到从而被误判成可以flip的点
关键是遇到出界还要继续直到bfs走完再返回false
Time O(MN)
Space O(MN)
Runtime: 4 ms, faster than 34.91% of Java online submissions for Surrounded Regions.
Memory Usage: 44.7 MB, less than 85.16% of Java online submissions for Surrounded Regions.
class Solution {
private static int[] dx = new int[]{1, 0, -1, 0};
private static int[] dy = new int[]{0, -1, 0, 1};
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
return;
}
int rows = board.length;
int cols = board[0].length;
boolean[][] visited = new boolean[rows][cols];
for (int y = 1; y < rows - 1; y++) {
for (int x = 1; x < cols - 1; x++) {
if (board[y][x] == 'X' || visited[y][x]) {
continue;
}
if (bfs(board, visited, y, x, false)) {
bfs(board, null, y, x, true);
}
}
}
}
private boolean bfs(char[][] board, boolean[][] visited, int y, int x, boolean flip) {
boolean result = true;
Queue<int[]> que = new ArrayDeque<>();
que.offer(new int[]{y, x});
if (flip) {
board[y][x] = 'X';
} else {
visited[y][x] = true;
}
while (!que.isEmpty()) {
int[] curr = que.poll();
for (int i = 0; i < 4; i++) {
int ny = curr[0] + dy[i];
int nx = curr[1] + dx[i];
// If the neighbor is out of the boundary, means current position is at the boundary
if (ny < 0 || nx < 0 || ny >= board.length || nx >= board[0].length) {
result = false;
continue;
}
if (board[ny][nx] != 'O' || (!flip && visited[ny][nx])) {
continue;
}
if (flip) {
board[ny][nx] = 'X';
} else {
visited[ny][nx] = true;
}
que.offer(new int[]{ny, nx});
}
}
return result;
}
}
Version #2 Union Find
This is much slower than the DFS version, but it is a very good practice of union find
Connect all 'O' on 4 edges (x == 0 || x == cols - 1 || y == 0 || y == row - 1) to a dummy node
Connect all 'O' to its neighbor 'O's
In the end, mark all node connected to dummy node as 'O', otherwise 'X'
Time O(mn)
Space O(mn)
6.93 %
class Solution {
class UF {
private int[] id;
private int[] size;
public UF(int N) {
id = new int[N];
size = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
size[i] = 1;
}
}
private int root(int i) {
while (id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}
private boolean connected(int p, int q) {
return root(p) == root(q);
}
private void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) {
return;
}
if (size[rootP] < size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
}
}
private int rows;
private int cols;
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
return;
}
this.rows = board.length;
this.cols = board[0].length;
UF uf = new UF(rows * cols + 1);
int dummyId = rows * cols;
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
if (board[y][x] == 'O') {
int currLabel = getLabel(y, x);
if (x == 0 || x == cols - 1 || y == 0 || y == rows - 1) {
uf.union(currLabel, dummyId);
} else {
if (board[y - 1][x] == 'O') {
uf.union(currLabel, getLabel(y - 1, x));
}
if (board[y + 1][x] == 'O') {
uf.union(currLabel, getLabel(y + 1, x));
}
if (board[y][x - 1] == 'O') {
uf.union(currLabel, getLabel(y, x - 1));
}
if (board[y][x + 1] == 'O') {
uf.union(currLabel, getLabel(y, x + 1));
}
}
}
}
}
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
if (uf.connected(getLabel(y, x), dummyId)) {
board[y][x] = 'O';
} else {
board[y][x] = 'X';
}
}
}
}
private int getLabel(int y, int x) {
return y * cols + x;
}
}
Version #3 DFS
100.00 %
Similar to BFS version, mark un-surrounded area as '#' and flip back in the end
time O(mn) Space O(1)
class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
return;
}
int rows = board.length;
int cols = board[0].length;
for (int y = 0; y < rows; y++) {
dfs(y, 0, board);
dfs(y, cols - 1, board);
}
for (int x = 0; x < cols; x++) {
dfs(0, x, board);
dfs(rows - 1, x, board);
}
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
if (board[y][x] == '#') {
board[y][x] = 'O';
} else {
board[y][x] = 'X';
}
}
}
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
private void dfs(int y, int x, char[][] board) {
if (board[y][x] == 'O') {
board[y][x] = '#';
} else {
return;
}
for (int i = 0; i < 4; i++) {
int nextY = y + dy[i];
int nextX = x + dx[i];
if (nextY > 0 && nextY < board.length && nextX > 0 && nextX < board[0].length && board[nextY][nextX] == 'O') {
dfs(nextY, nextX, board);
}
}
}
}
[1 ST TRY]
Version #1 BFS
这道题想法比较巧妙一开始没想出来
求Surrounded Regions比较难，但是从四条边界出发求UnSurrounded Regions就比较容易了
先把UnSurrounded Regions标记为‘U’
最后对全部matrix traverse一遍，依然标记为‘O’的证明是Surrounded Regions
public class Solution {
private int[] dx = {1, 0, -1, 0};
private int[] dy = {0, 1, 0, -1};
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) return;
//for j = 0 and j = board[0].length - 1
//for every i
for (int i = 0; i < board.length; i++) {
if (board[i][0] == 'O') {
solve(board, new int[]{i, 0});
}
if (board[i][board[0].length - 1] == 'O') {
solve(board, new int[]{i, board[0].length - 1});
}
}
//for i = 0 and i = board.length - 1
//for every j
for (int j = 0; j < board[0].length; j++) {
if (board[0][j] == 'O') {
solve(board, new int[]{0, j});
}
if (board[board.length - 1][j] == 'O') {
solve(board, new int[]{board.length - 1, j});
}
}
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] == 'U') board[i][j] = 'O';
}
}
}
//Set unbounded positions to 'U'
private void solve(char[][] board, int[] startPoint) {
Queue<int[]> que = new LinkedList<>();
que.add(startPoint);
board[startPoint[0]][startPoint[1]] = 'U';
int[] curr;
int nx, ny;
while (!que.isEmpty()) {
curr = que.poll();
//neighbors
for (int i = 0; i < 4; i++) {
nx = curr[0] + dx[i];
ny = curr[1] + dy[i];
if (nx >= 0 && nx < board.length && ny >= 0 && ny < board[0].length) {
if (board[nx][ny] == 'O') {
board[nx][ny] = 'U';
que.offer(new int[]{nx, ny});
}
}
}
}
}
}
二刷 BFS
感觉没有一刷写的好
跟一刷的区别是这里提前把所有boarder的0都加到queue里面了， 看了一刷的答案感觉是unnecessary的
Runtime: 2 ms, faster than 58.83% of Java online submissions for Surrounded Regions.
Memory Usage: 40.8 MB, less than 91.47% of Java online submissions for Surrounded Regions.
class Solution {
private int[] dx = {1, 0, -1, 0};
private int[] dy = {0, 1, 0, -1};
public void solve(char[][] board) {
int m = board.length;
int n = board[0].length;
Queue<int[]> que = new LinkedList<>();
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') {
board[i][0] = '#';
que.offer(new int[]{i, 0});
}
if (board[i][n - 1] == 'O') {
board[i][n - 1] = '#';
que.offer(new int[]{i, n - 1});
};
}
for (int j = 1; j < n - 1; j++) {
if (board[0][j] == 'O') {
board[0][j] = '#';
que.offer(new int[]{0, j});
}
if (board[m - 1][j] == 'O') {
board[m - 1][j] = '#';
que.offer(new int[]{m - 1, j});
}
}
while (!que.isEmpty()) {
int[] curr = que.poll();
int x = curr[0], y = curr[1];
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] == 'O') {
board[nx][ny] = '#';
que.offer(new int[]{nx, ny});
}
}
}
for (int x = 0; x < m; x++) {
for (int y = 0; y < n; y++) {
if (board[x][y] == '#') {
board[x][y] = 'O';
} else {
board[x][y] = 'X';
}
}
}
}
}
No comments:
Post a Comment