B*****7
发帖数: 137 | 1 我刚才做了 twosum，分别用了naive （O(n^2)）和先sort再找（O(nlgn)）的方法，都
过了大小oj，感觉大小oj好像没什么本质区别。
二爷可有何指正？ |
r**h
发帖数: 1288 | 2 因为lc上的大oj还不够大。。。
【在 B*****7 的大作中提到】
: 我刚才做了 twosum，分别用了naive （O(n^2)）和先sort再找（O(nlgn)）的方法，都
: 过了大小oj，感觉大小oj好像没什么本质区别。
: 二爷可有何指正？
|
g**G
发帖数: 767 | 3 给你推荐一道题叫surrounded regions,
来感受一下大小的差别 |
B*****7
发帖数: 137 | 4 刚做了surrounded regions. 点了十下 Judge Large, 过了一次，用了 796 ms.
后来拷了一个别人貌似优化的solution，看看能不能大oj。发现也没过。
哪位大牛发一个肯定能过的solution让大家学习学习呗.
先谢谢啦～
【在 g**G 的大作中提到】
: 给你推荐一道题叫surrounded regions,
: 来感受一下大小的差别
|
f*******t
发帖数: 7549 | 5 我写的java过不了surrounded region的large，但印象中以前有人能过 |
g*********e
发帖数: 14401 | 6 surround region 你首先把连接在边缘上的O都染成别的颜色r
再把剩下的o都染成X
再把r换回来O就行了 |
r*******e
发帖数: 7583 | 7 C++的surrounded regions，用BFS四周往中间搜。large 64ms
class Solution {
public:
void solve(vector> &board) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (board.size() == 0) return;
if (board[0].size() == 0) return;
int m = board.size();
int n = board[0].size();
queue > q;
for (int i = 0; i < m; ++i) {
if (board[i][0] == 'O') {
q.push(make_pair(i, 0));
}
if (board[i][n - 1] == 'O') {
q.push(make_pair(i, n - 1));
}
}
for (int j = 0; j < n; ++j) {
if (board[0][j] == 'O') {
q.push(make_pair(0, j));
}
if (board[m - 1][j] == 'O') {
q.push(make_pair(m - 1, j));
}
}
while (!q.empty()) {
int i = q.front().first;
int j = q.front().second;
q.pop();
board[i][j] = 'G';
if (i > 0 && board[i - 1][j] == 'O') q.push(make_pair(i - 1, j));
if (i < m - 1 && board[i + 1][j] == 'O') q.push(make_pair(i + 1,
j));
if (j > 0 && board[i][j - 1] == 'O') q.push(make_pair(i, j - 1));
if (j < n - 1 && board[i][j + 1] == 'O') q.push(make_pair(i, j +
1));
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == 'G') {
board[i][j] = 'O';
}
}
}
}
};
【在 B*****7 的大作中提到】
: 刚做了surrounded regions. 点了十下 Judge Large, 过了一次，用了 796 ms.
: 后来拷了一个别人貌似优化的solution，看看能不能大oj。发现也没过。
: 哪位大牛发一个肯定能过的solution让大家学习学习呗.
: 先谢谢啦～
|
d*******y
发帖数: 27 | 8 LZ还没做到不一样的。oj很多题可以用DFS递归，也可以DP，小集合DFS可以过，大集合
肯定过不了。我记得几道是Unique Paths I & II，Decode Ways， Climbing Stairs，
Distinct Subsequences。surround region那道题大集合很严格。我找了一个从四周搜
索，BFS标记O的解，和我的算法一样，就是实现不同，它的就能过，我的一直过不了。 |
