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:
這次作業(yè)寫了太久太久，久的我?guī)状味枷敕艞壛恕Ｋ悸芬沧兞撕枚啻巍?br>
讓我先休息下。然后好好總結下。
剛和女朋友打了個電話，小吵了一架，然后又互相理解。我把我對她的不爽和她說了。我覺得戀愛就得這樣，不要憋著，有什么對對方不舒服的地方一定要說出來。
好吧，咱們繼續(xù)。
這道題目昨天就開始做了。但是沒能做出來。又不想看答案，今天就接著做了。
其實昨天就已經(jīng)找到那個思路了，或者說，很接近的思路了。
我發(fā)現(xiàn)，解決一道題目的思路有很多，但簡潔解決的方法往往只有一個。
而找到這個正確思路之前，需要思考許多其他方法，然后最后的最后，簡化成了這個方法。
或者說，是模型。
這道題目就是找出被包圍的部分。
怎么找呢？我剛開始很快就找到了思路。能和外面的O連在一塊的里面的O，就一定是未被包圍的，其他的都是被包圍的，可以被變成X。
那么，最重要的問題是，以何種形式來找出這些和外部連著的O呢？
這里我就是思維被局限了。或者說，我之前對BFS的認識還不夠深。
我傻逼的按了下 提示?？吹秸f用 BFS。
BFS在我腦子里是什么樣的東西呢？一個隊列。然后從最左上角開始，遍歷。然后設置一個標志位數(shù)組來標志每個節(jié)點是否已經(jīng)被訪問過。
然后我就在 是否被訪問 這個問題上 陷進去了。絕對不可能是簡單的，訪問過了一次，就算已經(jīng)被訪問了。 比如， 之前的元素是 X， 訪問的元素是O。 那么，這個O 就算未被訪問過。
總之，里面的情況會比較復雜。
為什么這么復雜，就是因為我站的角度不對。正確的角度應該是，
訪問那些在外圍的， O 點。對每個點進行 BFS。而不是直接從左上角那個點開始進行BFS。
而且，這里還有一個要注意的地方。如果設置一個統(tǒng)一的隊列來存放這些點，那么就會造成 stackoverflow。 所以，必須在方法里新建隊列。并且對每一個點，設置自己的隊列。
而且，只有O點可以被放進隊列。這是一個我之前想法沒能想到的地方。
具體地說，當你碰到X的時候，就可以停止了。即使與X相鄰的有O，那又如何呢？你們中間隔著X，說明你們沒有連接在一塊。如果你們事實上是連接在一塊的，那一定也是通過其他的渠道，連接在一塊的，一定不是通過這個X鏈接在一塊的。
所以，一旦碰到X，就停止，不用塞入隊列。
還有個小技巧。將與邊緣O連在一塊的O全部改成R，然后搜索過程中如果碰到R，那就說明已經(jīng)訪問過了，該O已經(jīng)在隊列或者已經(jīng)處理過了，就不需要再被考慮了，直接退出。
所以，之前看的BFS總結現(xiàn)在想來很有意義。
什么樣的結點，滿足什么樣的狀態(tài)，才可以進入隊列。
這是BFS需要考慮的。
而DFS需要考慮的是，
DFS是建立在遞歸之上的，那么，什么時候，滿足什么條件時，該結束DFS，結束遞歸。
LJ 第20題。
今天重做，我寫出了DFS的方法。
其中會有個測試過不了，爆棧。
ooooooooo
xxxxxxxxo
ooooooooo
oxxxxxxxx
ooooooooo
xxxxxxxxo
ooooooooo
....
當碰到這么一種形式的時候，如果DFS寫的太隨意太莽撞，就會很容易一次遞歸把所有這些O全部走下來，導致stack裝不下這么多東西。然后直接爆棧。
所以要多用幾次DFS，分攤壓力。
那么就是我?guī)讉€月前說的，DFS該考慮，滿足什么條件是，就結束遞歸。
為了分攤壓力，當滿足，掃描的當前點，如果已經(jīng)在邊緣上了，那么就不掃描了。因為無論他是O/X，我都沒辦法改變啊。這樣就過了測試。
另外，對bfs，現(xiàn)在的理解還是很錯誤。得多訓練。
代碼如下：
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);
}
**
總結：什么樣的結點，滿足什么樣的狀態(tài)，才可以進入隊列。
這是BFS需要考慮的。
而DFS需要考慮的是，
DFS是建立在遞歸之上的，那么，什么時候，滿足什么條件時，該結束DFS，結束遞歸。
另外， Java中 queue是一個接口，interface，不能直接用。
需要選擇一個數(shù)據(jù)結構。比如
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
然后我再做一樣的事。
最后，我遍歷內層的數(shù)據(jù)，如果是 O并且祖先是-1,那么一定和外面相連的。就flip
差不多就這樣了。
今天收到了兩封拒信，心情不好很好。
而且都是真人給我發(fā)拒信，而不是系統(tǒng)據(jù)。
看了背景還不是很強。
1010data覺得自己答得很好，沒想到還是拒了。
今年真的不知道能走多遠，能否進個大公司。
真的不知道。
繼續(xù)刷題，繼續(xù)投。
不拋棄，不放棄。
然后等待機會，抓住他。
是這樣嗎？
是的。
現(xiàn)在才知道，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
