居然不怕我 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

居然不怕我

居然不怕我# Joke - 肚皮舞运动

B*72013-05-10 07:05

1 楼

我刚才做了 twosum，分别用了naive （O(n^2)）和先sort再找（O(nlgn)）的方法，都
过了大小oj，感觉大小oj好像没什么本质区别。
二爷可有何指正？

s*o2013-05-10 07:05

2 楼

1.免费的100刀 Chase SapphireSM Card 只需消费一笔
http://bankingbonus.spaces.live.com/blog/
最近申请chase家的这个信用卡会弹出一个页面，写着Before you go…We hope you
will reconsider 难不成他们家最近被人拿太多这个100刀了！不用对它客气，赶
紧点击Return&Apply，拿到落袋为安。
2.免费的250刀 Chase SapphireSM Preferred Card需要满足这个offer的条件
http://bankingbonus.spaces.live.com/blog/
3. Free $100 amazon gift card 申请 starpoints卡，只需消费一笔
4. 免费的12000mile from Miles Card by Discover
http://bankingbonus.spaces.live.com/blog/cns!E581C466612AE7F!306.entry
5. free $150 or air ticket

p*g2013-05-10 07:05

3 楼

r*h2013-05-10 07:05

4 楼

因为lc上的大oj还不够大。。。

【在 B*****7 的大作中提到】

: 我刚才做了 twosum，分别用了naive （O(n^2)）和先sort再找（O(nlgn)）的方法，都
: 过了大小oj，感觉大小oj好像没什么本质区别。
: 二爷可有何指正？

u*a2013-05-10 07:05

5 楼

最后这一下是做什么？熏他？

g*G2013-05-10 07:05

6 楼

给你推荐一道题叫surrounded regions,
来感受一下大小的差别

B*72013-05-10 07:05

7 楼

刚做了surrounded regions. 点了十下 Judge Large, 过了一次，用了 796 ms.
后来拷了一个别人貌似优化的solution，看看能不能大oj。发现也没过。
哪位大牛发一个肯定能过的solution让大家学习学习呗.
先谢谢啦～

【在 g**G 的大作中提到】

: 给你推荐一道题叫surrounded regions,
: 来感受一下大小的差别

f*t2013-05-10 07:05

8 楼

我写的java过不了surrounded region的large，但印象中以前有人能过

g*e2013-05-10 07:05

9 楼

surround region 你首先把连接在边缘上的O都染成别的颜色r
再把剩下的o都染成X
再把r换回来O就行了

r*e2013-05-10 07:05

10 楼

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*y2013-05-10 07:05

11 楼

LZ还没做到不一样的。oj很多题可以用DFS递归，也可以DP，小集合DFS可以过，大集合
肯定过不了。我记得几道是Unique Paths I & II，Decode Ways， Climbing Stairs，
Distinct Subsequences。surround region那道题大集合很严格。我找了一个从四周搜
索，BFS标记O的解，和我的算法一样，就是实现不同，它的就能过，我的一直过不了。