Question:
My code:
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
private int width = 0;
private int height = 0;
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0)
return;
width = board.length;
height = board[0].length;
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
if ((i == 0 || i == width - 1 || j == 0 || j == height - 1) && (board[i][j] == 'O')) {
board[i][j] = 'R';
bfs(i, j, board);
}
}
}
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
if (board[i][j] == 'R')
board[i][j] = 'O';
else if (board[i][j] == 'O')
board[i][j] = 'X';
}
}
}
private void bfs(int i, int j, char[][] board) {
if (i < 0 || i >= width || j < 0 || j >= height)
return;
Queue<Integer> q = new LinkedList<Integer>();
q.offer(i * height + j);
while (!q.isEmpty()) {
int id = q.poll();
int tempWidth = id / height;
int tempHeight = id % height;
if (tempHeight - 1 >= 0)
if (board[tempWidth][tempHeight - 1] == 'O') {
board[tempWidth][tempHeight - 1] = 'R';
q.offer(tempWidth * height + tempHeight - 1);
}
if (tempHeight + 1 < height)
if (board[tempWidth][tempHeight + 1] == 'O') {
board[tempWidth][tempHeight + 1] = 'R';
q.offer(tempWidth * height + tempHeight + 1);
}
if (tempWidth - 1 >= 0)
if (board[tempWidth - 1][tempHeight] == 'O') {
board[tempWidth - 1][tempHeight] = 'R';
q.offer((tempWidth - 1) * height + tempHeight);
}
if (tempWidth + 1 < width)
if (board[tempWidth + 1][tempHeight] == 'O') {
board[tempWidth + 1][tempHeight] = 'R';
q.offer((tempWidth + 1) * height + tempHeight);
}
}
}
}
My test result:
这次作业写了太久太久，久的我几次都想放弃了。思路也变了好多次。
让我先休息下。然后好好总结下。
刚和女朋友打了个电话，小吵了一架，然后又互相理解。我把我对她的不爽和她说了。我觉得恋爱就得这样，不要憋着，有什么对对方不舒服的地方一定要说出来。
好吧，咱们继续。
这道题目昨天就开始做了。但是没能做出来。又不想看答案，今天就接着做了。
其实昨天就已经找到那个思路了，或者说，很接近的思路了。
我发现，解决一道题目的思路有很多，但简洁解决的方法往往只有一个。
而找到这个正确思路之前，需要思考许多其他方法，然后最后的最后，简化成了这个方法。
或者说，是模型。
这道题目就是找出被包围的部分。
怎么找呢？我刚开始很快就找到了思路。能和外面的O连在一块的里面的O，就一定是未被包围的，其他的都是被包围的，可以被变成X。
那么，最重要的问题是，以何种形式来找出这些和外部连着的O呢？
这里我就是思维被局限了。或者说，我之前对BFS的认识还不够深。
我傻逼的按了下 提示。看到说用 BFS。
BFS在我脑子里是什么样的东西呢？一个队列。然后从最左上角开始，遍历。然后设置一个标志位数组来标志每个节点是否已经被访问过。
然后我就在 是否被访问 这个问题上 陷进去了。绝对不可能是简单的，访问过了一次，就算已经被访问了。 比如， 之前的元素是 X， 访问的元素是O。 那么，这个O 就算未被访问过。
总之，里面的情况会比较复杂。
为什么这么复杂，就是因为我站的角度不对。正确的角度应该是，
访问那些在外围的， O 点。对每个点进行 BFS。而不是直接从左上角那个点开始进行BFS。
而且，这里还有一个要注意的地方。如果设置一个统一的队列来存放这些点，那么就会造成 stackoverflow。 所以，必须在方法里新建队列。并且对每一个点，设置自己的队列。
而且，只有O点可以被放进队列。这是一个我之前想法没能想到的地方。
具体地说，当你碰到X的时候，就可以停止了。即使与X相邻的有O，那又如何呢？你们中间隔着X，说明你们没有连接在一块。如果你们事实上是连接在一块的，那一定也是通过其他的渠道，连接在一块的，一定不是通过这个X链接在一块的。
所以，一旦碰到X，就停止，不用塞入队列。
还有个小技巧。将与边缘O连在一块的O全部改成R，然后搜索过程中如果碰到R，那就说明已经访问过了，该O已经在队列或者已经处理过了，就不需要再被考虑了，直接退出。
所以，之前看的BFS总结现在想来很有意义。
什么样的结点，满足什么样的状态，才可以进入队列。
这是BFS需要考虑的。
而DFS需要考虑的是，
DFS是建立在递归之上的，那么，什么时候，满足什么条件时，该结束DFS，结束递归。
LJ 第20题。
今天重做，我写出了DFS的方法。
其中会有个测试过不了，爆栈。
ooooooooo
xxxxxxxxo
ooooooooo
oxxxxxxxx
ooooooooo
xxxxxxxxo
ooooooooo
....
当碰到这么一种形式的时候，如果DFS写的太随意太莽撞，就会很容易一次递归把所有这些O全部走下来，导致stack装不下这么多东西。然后直接爆栈。
所以要多用几次DFS，分摊压力。
那么就是我几个月前说的，DFS该考虑，满足什么条件是，就结束递归。
为了分摊压力，当满足，扫描的当前点，如果已经在边缘上了，那么就不扫描了。因为无论他是O/X，我都没办法改变啊。这样就过了测试。
另外，对bfs，现在的理解还是很错误。得多训练。
代码如下：
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0)
return;
boolean[][] isVisited = new boolean[board.length][board[0].length];
for (int i = 0; i < board[0].length; i++)
if (!isVisited[0][i] && board[0][i] == 'O')
transform(board, isVisited, 0, i);
for (int i = 0; i < board[0].length; i++)
if (!isVisited[board.length - 1][i] && board[board.length - 1][i] == 'O')
transform(board, isVisited, board.length - 1, i);
for (int i = 0; i < board.length; i++)
if (!isVisited[i][0] && board[i][0] == 'O')
transform(board, isVisited, i, 0);
for (int i = 0; i < board.length; i++)
if (!isVisited[i][board[0].length - 1] && board[i][board[0].length - 1] == 'O')
transform(board, isVisited, i, board[0].length - 1);
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == 'R')
board[i][j] = 'O';
else if (board[i][j] == 'O')
board[i][j] = 'X';
}
}
}
private void transform(char[][] board, boolean[][] isVisited, int i, int j) {
if (isVisited[i][j])
return;
isVisited[i][j] = true;
int row = board.length;
int col = board[0].length;
board[i][j] = 'R';
if (i - 1 >= 1 && !isVisited[i - 1][j] && board[i - 1][j] == 'O')
transform(board, isVisited, i - 1, j);
if (i + 1 < row - 1 && !isVisited[i + 1][j] && board[i + 1][j] == 'O')
transform(board, isVisited, i + 1, j);
if (j - 1 >= 1 && !isVisited[i][j - 1] && board[i][j - 1] == 'O')
transform(board, isVisited, i, j - 1);
if (j + 1 < col - 1 && !isVisited[i][j + 1] && board[i][j + 1] == 'O')
transform(board, isVisited, i, j + 1);
}
**
总结：什么样的结点，满足什么样的状态，才可以进入队列。
这是BFS需要考虑的。
而DFS需要考虑的是，
DFS是建立在递归之上的，那么，什么时候，满足什么条件时，该结束DFS，结束递归。
另外， Java中 queue是一个接口，interface，不能直接用。
需要选择一个数据结构。比如
Queue<Integer> q = new LinkedList<Integer>();
**
Anyway, Good luck, Richardo!
这道题目依然采用了三种方法来做。
DFS, BFS, Union-Find
DFS:
My code:
public class Solution {
private int row = 0;
private int col = 0;
private boolean[][] mark;
private int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private class Pair {
int x;
int y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
this.row = board.length;
this.col = board[0].length;
mark = new boolean[row][col];
for (int i = 0; i < row; i++) {
if (board[i][0] == 'O' && !mark[i][0]) {
visit(i, 0, board);
}
if (board[i][col - 1] == 'O' && !mark[i][col - 1]) {
visit(i, col - 1, board);
}
}
for (int i = 1; i < col - 1; i++) {
if (board[0][i] == 'O' && !mark[0][i]) {
visit(0, i, board);
}
if (board[row - 1][i] == 'O' && !mark[row - 1][i]) {
visit(row - 1, i, board);
}
}
for (int i = 1; i < row - 1; i++) {
for (int j = 1; j < col - 1; j++) {
if (board[i][j] == 'O' && !mark[i][j]) {
board[i][j] = 'X';
}
}
}
}
private void visit(int i, int j, char[][] board) {
mark[i][j] = true;
for (int k = 0; k < 4; k++) {
int x = i + dir[k][0];
int y = j + dir[k][1];
if (check(x, y) && board[x][y] == 'O' && !mark[x][y]) {
visit(x, y, board);
}
}
}
private boolean check(int i, int j) {
if (i <= 0 || i >= row - 1 || j <= 0 || j >= col - 1) {
return false;
}
return true;
}
}
和 number of islands 差不多的。
这里注意的是，一开始，最后一个例子一直 stackoverflow
可能就差一点。
然后做了改进，
check处， 如果 (i, j) 定义的点在边上，也不用再深入做dfs了。
万一他正好成一种 zigzag条状的形式 往下链接，那么栈就会爆。
还不如，就老老实实做好自己这个点上的事。其他的，由其他边上的点来做。
BFS:
My code:
public class Solution {
private int row = 0;
private int col = 0;
private boolean[][] mark;
private int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private class Pair {
int x;
int y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
this.row = board.length;
this.col = board[0].length;
mark = new boolean[row][col];
for (int i = 0; i < row; i++) {
if (board[i][0] == 'O' && !mark[i][0]) {
visit(i, 0, board);
}
if (board[i][col - 1] == 'O' && !mark[i][col - 1]) {
visit(i, col - 1, board);
}
}
for (int i = 1; i < col - 1; i++) {
if (board[0][i] == 'O' && !mark[0][i]) {
visit(0, i, board);
}
if (board[row - 1][i] == 'O' && !mark[row - 1][i]) {
visit(row - 1, i, board);
}
}
for (int i = 1; i < row - 1; i++) {
for (int j = 1; j < col - 1; j++) {
if (board[i][j] == 'O' && !mark[i][j]) {
board[i][j] = 'X';
}
}
}
}
private void visit(int i, int j, char[][] board) {
Queue<Pair> q = new LinkedList<Pair>();
q.offer(new Pair(i, j));
while (!q.isEmpty()) {
Pair curr = q.poll();
int curr_x = curr.x;
int curr_y = curr.y;
mark[curr_x][curr_y] = true;
for (int k = 0; k < 4; k++) {
int x = curr_x + dir[k][0];
int y = curr_y + dir[k][1];
if (check(x, y) && board[x][y] == 'O' && !mark[x][y]) {
q.offer(new Pair(x, y));
}
}
}
}
private boolean check(int i, int j) {
if (i < 0 || i >= row || j < 0 || j >= col) {
return false;
}
return true;
}
}
TLE, BFS 总是超时。
Union-Find
My code:
public class Solution {
private int[] id;
private int row = 0;
private int col = 0;
private int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
this.row = board.length;
this.col = board[0].length;
id = new int[row * col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == 'O' && (i == 0 || i == row - 1 || j == 0 || j == col - 1)) {
id[i * col + j] = -1;
}
else {
id[i * col + j] = i * col + j;
}
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == 'O') {
visit(i, j, board);
}
}
}
for (int i = 1; i < row - 1; i++) {
for (int j = 1; j < col - 1; j++) {
if (board[i][j] == 'O' && find(i * col + j) != -1) {
board[i][j] = 'X';
}
}
}
}
private void visit(int i, int j, char[][] board) {
for (int k = 0; k < 4; k++) {
int curr_x = i + dir[k][0];
int curr_y = j + dir[k][1];
if (check(curr_x, curr_y) && board[curr_x][curr_y] == 'O') {
union(i * col + j, curr_x * col + curr_y);
}
}
}
private void union(int x, int y) {
int left = find(x);
int right = find(y);
if (left == right) {
return;
}
else if (left == -1) {
id[right] = -1;
}
else if (right == -1) {
id[left] = -1;
}
else {
id[left] = right;
}
}
private int find(int x) {
if (id[x] == -1 || id[x] == x) {
return id[x];
}
else {
int ret = find(id[x]);
id[x] = ret;
return ret;
}
}
private boolean check(int i, int j) {
if (i <= 0 || i >= row - 1 || j <= 0 || j >= col - 1) {
return false;
}
return true;
}
}
和 number of islands 差不多。
那个题目是画块，这个也差不多的。
只不过边上的 O 都属于同一块。
所以我略微改写了下 union find 方法。
让这些边上的点都同时继承于一个 virtual head: -1
然后我再做一样的事。
最后，我遍历内层的数据，如果是 O并且祖先是-1,那么一定和外面相连的。就flip
差不多就这样了。
今天收到了两封拒信，心情不好很好。
而且都是真人给我发拒信，而不是系统据。
看了背景还不是很强。
1010data觉得自己答得很好，没想到还是拒了。
今年真的不知道能走多远，能否进个大公司。
真的不知道。
继续刷题，继续投。
不抛弃，不放弃。
然后等待机会，抓住他。
是这样吗？
是的。
现在才知道，BFS之所以那么那么容易TLE，因为是
Naive BFS
然后针对于这种类型的题目，还有种更高效的BFS，
Multi-End BFS
My code:
public class Solution {
private int row = 0;
private int col = 0;
private int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private class Pair {
int x;
int y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
this.row = board.length;
this.col = board[0].length;
Queue<Pair> q = new LinkedList<Pair>();
for (int i = 0; i < row; i++) {
if (board[i][0] == 'O') {
q.offer(new Pair(i, 0));
}
if (col > 1 && board[i][col - 1] == 'O') {
q.offer(new Pair(i, col - 1));
}
}
for (int j = 1; j < col - 1; j++) {
if (board[0][j] == 'O') {
q.offer(new Pair(0, j));
}
if (row > 1 && board[row - 1][j] == 'O') {
q.offer(new Pair(row - 1, j));
}
}
while (!q.isEmpty()) {
Pair curr = q.poll();
int curr_x = curr.x;
int curr_y = curr.y;
board[curr_x][curr_y] = 'R';
for (int k = 0; k < 4; k++) {
int x = curr_x + dir[k][0];
int y = curr_y + dir[k][1];
if (check(x, y) && board[x][y] == 'O') {
q.offer(new Pair(x, y));
}
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == 'R') {
board[i][j] = 'O';
}
else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
private boolean check(int i, int j) {
if (i <= 0 || i >= row - 1 || j <= 0 || j >= col - 1) {
return false;
}
return true;
}
}
Anyway, Good luck, Richardo! -- 09/09/2016
