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的解,和我的算法一样,就是实现不同,它的就能过,我的一直过不了。 |