r*******k
发帖数: 1423 | 1 https://oj.leetcode.com/problems/surrounded-regions/
按说很简单啊
就是从四个边，找，碰到O就去扩散，标记为某个D
然后四边都搜完之后，把所有的残存的O变为X；
再把D变回成O，就完成了。
O向外扩展时，可以用递归实现DFS，也可以实现BFS
先写了一个DFS，直接stackOverFlow了
改成BFS，怎么改都Time Limit Exceed
搞不懂怎么做才最快，我ft死了
看了看discussion，有个unionSet的方案
看了看，贴上去，通过了
没搞懂为啥这个unionSet比我那个优，
怎么想都是一样的复杂度啊 | p********g
发帖数: 61 | | R*****i
发帖数: 2126 | 3 有时候数太大超出range也是报“time limit exceeded”，把代码贴出来大家一起分析
一下吧。 | e*****i
发帖数: 182 | 4 java vs cpp?
【在 p********g 的大作中提到】
: 我也是用那算法写的，没问题啊
| p********g
发帖数: 61 | 5 java
【在 e*****i 的大作中提到】
: java vs cpp?
| r*******k
发帖数: 1423 | 6 我也是java啊
本机上拿TLE的例子测试过，没问题的。
void mark(char[][] board, int x, int y){
if(x<0 || y<0 || x>=board.length || y>=board[0].length){
return;
}
if(board[x][y]=='O'){
Queue X = new LinkedList();
Queue Y = new LinkedList();
X.offer(x);Y.offer(y);
int count = X.size();
while(count>0){
while(count>0){
int xx = X.poll();
int yy = Y.poll();
board[xx][yy]='D';
if(xx>0 && board[xx-1][yy]=='O'){
X.offer(xx-1);Y.offer(yy);
}
if(xx
X.offer(xx+1);Y.offer(yy);
}
if(yy>0 && board[xx][yy-1]=='O'){
X.offer(xx);Y.offer(yy-1);
}
if(yy
X.offer(xx);Y.offer(yy+1);
}
count--;
}
count = X.size();
}
}
return;
}
public void solve(char[][] board) {
if(board==null || board.length<3 || board[0].length<3){
return;
}
for (int i=0;i
mark(board, i, 0);
mark(board, i, board[0].length-1);
}
for (int i=0;i
mark(board, 0, i);
mark(board, board.length-1, i);
}
for(int i = 0;i
System.out.println(board[i]);
}
for (int i=0;i
for (int j=0;j
if(board[i][j]=='O'){
board[i][j]='X';
} else if(board[i][j]=='D'){
board[i][j]='O';
}
}
}
for(int i = 0;i
System.out.println(board[i]);
}
return;
}
【在 p********g 的大作中提到】
: java
| p********g
发帖数: 61 | 7 在最开始那两个for loop里面call了很多次mark().其实可以就在主函数里面申明一个
queue，把四边的position加进去，然后再去一次性mark掉
【在 r*******k 的大作中提到】
: 我也是java啊
: 本机上拿TLE的例子测试过，没问题的。
: void mark(char[][] board, int x, int y){
: if(x<0 || y<0 || x>=board.length || y>=board[0].length){
: return;
: }
: if(board[x][y]=='O'){
: Queue X = new LinkedList();
: Queue Y = new LinkedList();
: X.offer(x);Y.offer(y);
| y*******8
发帖数: 112 | | P*******L
发帖数: 2637 | 9 我的解，用了 BFS。还有很多优化的余地，但是已经 0.5s 过了。
public class Solution {
public void solve(char[][] board) {
int n = board.length;
if(n <= 2) return;
int m = board[0].length;
if(m <= 2) return;
Queue qi = new LinkedList();
Queue qj = new LinkedList();
for(int i = 0; i < n; i++) {
if(board[i][0] == 'O') {
qi.add(i); qj.add(0);
}
if(board[i][m-1] == 'O') {
qi.add(i); qj.add(m-1);
}
}
for(int j = 1; j < m - 1; j++) {
if(board[0][j] == 'O') {
qi.add(0); qj.add(j);
}
if(board[n-1][j] == 'O') {
qi.add(n-1); qj.add(j);
}
}
while(!(qi.isEmpty() || qj.isEmpty())) {
int i = qi.remove();
int j = qj.remove();
board[i][j] = '0';
if(i > 0 && board[i-1][j] == 'O') {
qi.add(i-1); qj.add(j);
}
if(i < n-1 && board[i+1][j] == 'O') {
qi.add(i+1); qj.add(j);
}
if(j > 0 && board[i][j-1] == 'O') {
qi.add(i); qj.add(j-1);
}
if(j < m-1 && board[i][j+1] == 'O') {
qi.add(i); qj.add(j+1);
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(board[i][j] == '0')
board[i][j] = 'O';
else
board[i][j] = 'X';
}
}
}
}
【在 r*******k 的大作中提到】
: https://oj.leetcode.com/problems/surrounded-regions/
: 按说很简单啊
: 就是从四个边，找，碰到O就去扩散，标记为某个D
: 然后四边都搜完之后，把所有的残存的O变为X；
: 再把D变回成O，就完成了。
: O向外扩展时，可以用递归实现DFS，也可以实现BFS
: 先写了一个DFS，直接stackOverFlow了
: 改成BFS，怎么改都Time Limit Exceed
: 搞不懂怎么做才最快，我ft死了
: 看了看discussion，有个unionSet的方案
| r*******k
发帖数: 1423 | 10 这个没啥区别吧
很影响性能？
【在 p********g 的大作中提到】
: 在最开始那两个for loop里面call了很多次mark().其实可以就在主函数里面申明一个
: queue，把四边的position加进去，然后再去一次性mark掉
| | | p********g
发帖数: 61 | 11 我的做法和9楼非常像。我想是这个原因吧。如果board非常大的话，就要call很多次
mark，然后每个mark里面都要创建两次新的queue。这些都可以优化掉
【在 r*******k 的大作中提到】
: 这个没啥区别吧
: 很影响性能？
| p********r
发帖数: 66 | 12 1. 从四个边是O的位置开始，广度优先搜索相邻的位置是O的，并且标记为R. 这一步用
时O(n^2)
2. 把所有是R的位置标记为O，所有是O的位置标记为X，用时O(n^2)
因为输入是二位矩阵所有，O(n^2)时间复杂度是最好的了。 Java 代码 572ms跑完所有
test case
具体代码如下：
public void solve(char[][] board) {
if(board.length < 3) return;
Stack stack = new Stack();
for(int i = 0; i < board.length; i++){
if(board[i][0] == 'O'){
insert(stack, i, 0);
}
if(board[i].length > 1 && board[i][board[i].length - 1] == 'O'){
insert(stack, i, board[i].length - 1);
}
if(i == 0 || i == (board.length - 1)){
for(int j = 1; j < board[i].length - 1; j++)
if(board[i][j] == 'O'){
insert(stack, i, j);
}
}
}
int[] pair;
while(!stack.empty()){
pair = stack.pop();
epidemicMark(board, pair[0], pair[1], stack);
}
changeChar(board);
}
private void insert(Stack stack, int x, int y){
int[] ins = {x, y};
stack.push(ins);
}
private void epidemicMark(char[][] board, int i, int j, Stack
stack){
if(board[i][j] != 'O') return;
board[i][j] = 'Y';
int ni, nj;
ni = i; nj = j - 1;
if( !(ni < 0 || ni >= board.length || nj < 0 || nj >= board[0].
length)
&& board[ni][nj] == 'O'){
insert(stack, ni, nj);
}
ni = i; nj = j + 1;
if( !(ni < 0 || ni >= board.length || nj < 0 || nj >= board[0].
length)
&& board[ni][nj] == 'O'){
insert(stack, ni, nj);
}
ni = i - 1; nj = j;
if( !(ni < 0 || ni >= board.length || nj < 0 || nj >= board[0].
length)
&& board[ni][nj] == 'O'){
insert(stack, ni, nj);
}
ni = i + 1; nj = j;
if( !(ni < 0 || ni >= board.length || nj < 0 || nj >= board[0].
length)
&& board[ni][nj] == 'O'){
insert(stack, ni, nj);
}
}
private void changeChar(char[][] board){
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[i].length; j++){
switch(board[i][j]){
case 'O':
board[i][j] = 'X';
break;
case 'Y':
board[i][j] = 'O';
break;
default:
break;
}
}
}
} | g*****g
发帖数: 212 | 13 内推君贴一个pass过的code：
class Solution {
public:
void setm1(vector> &board, int x, int y, int m, int n)
{
if (x <0 || x >= m || y < 0 || y >= n)
return;
if (board[x][y] != 'O')
return;
board[x][y] = 'Y';
setm1(board, x-1, y, m, n);
setm1(board, x+1, y, m, n);
setm1(board, x, y-1, m, n);
setm1(board, x, y+1, m, n);
}
void solve(vector> &board) {
int m = board.size();
if (m == 0)
return;
int n = board[0].size();
if (n == 0)
return;
for(int i=0; i
{
setm1(board, i, 0, m, n);
setm1(board, i, n-1, m, n);
}
for(int i=0; i
{
setm1(board, 0, i, m, n);
setm1(board, m-1, i, m, n);
}
for(int i=0; i
{
for(int j=0; j
{
if (board[i][j] == 'Y')
{
board[i][j] = 'O';
}
else
{
board[i][j] = 'X';
}
}
}
}
}; | j*****0
发帖数: 160 | 14 根据我的经验有时候leetcode上，偶尔有几次同样的代码有时候会TLE有时候不会 | k******n
发帖数: 451 | 15 mark
★ 发自iPhone App: ChineseWeb 7.8
【在 j*****0 的大作中提到】
: 根据我的经验有时候leetcode上，偶尔有几次同样的代码有时候会TLE有时候不会
| Z**********4
发帖数: 528 | 16 会不会你因为你用的linkedlist去实现queue？
用arraylist试试？
【在 r*******k 的大作中提到】
: https://oj.leetcode.com/problems/surrounded-regions/
: 按说很简单啊
: 就是从四个边，找，碰到O就去扩散，标记为某个D
: 然后四边都搜完之后，把所有的残存的O变为X；
: 再把D变回成O，就完成了。
: O向外扩展时，可以用递归实现DFS，也可以实现BFS
: 先写了一个DFS，直接stackOverFlow了
: 改成BFS，怎么改都Time Limit Exceed
: 搞不懂怎么做才最快，我ft死了
: 看了看discussion，有个unionSet的方案
| T*****u
发帖数: 7103 | 17 你先别做leetcode，自己写个简单的candycrash，就明白了。
【在 r*******k 的大作中提到】
: https://oj.leetcode.com/problems/surrounded-regions/
: 按说很简单啊
: 就是从四个边，找，碰到O就去扩散，标记为某个D
: 然后四边都搜完之后，把所有的残存的O变为X；
: 再把D变回成O，就完成了。
: O向外扩展时，可以用递归实现DFS，也可以实现BFS
: 先写了一个DFS，直接stackOverFlow了
: 改成BFS，怎么改都Time Limit Exceed
: 搞不懂怎么做才最快，我ft死了
: 看了看discussion，有个unionSet的方案
| m*******g
发帖数: 410 | |
|
