邻居说生物男猥琐 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Biology - 生物学

邻居说生物男猥琐

邻居说生物男猥琐# Biology - 生物学

k*r2017-09-28 07:09

1 楼

2维matrix装水问题，就是那个一维数组装水问题的扩展，求2维数组围成的池子能装
水的最大体积。
比方矩阵
333
303
333
装的最大水体积为3
这题怎么做，因为2维matrix围出的面积可以是各种各样的，凸的凹的都有可能，感觉
不容易找trival 算法阿

r*u2017-09-28 07:09

2 楼

详细资料可参考网站：
http://www.koretmuseumdays.org/pages/museums.html
更多资料也UPDATE在我的TWITTER上：http://twitter.com/aplan4life
just FOLLOW ME
17家免费的博物馆，如下
Asian Art Museum
Bay Area Discovery Museum
Chabot Space & Science Center
Children’s Discovery Museum of San Jose
Contemporary Jewish Museum
Exploratorium
Judah L. Magnes Museum
Lawrence Hall of Science
Legion of Honor
M. H. de Young Museum
Museum of the African Diaspora
Oakland Museum of California
San Francisco Museum of Modern Art
San Francisco Zoo
San

e*22017-09-28 07:09

3 楼

小留为何能这么趾高气扬？日日把妹？

p*22017-09-28 07:09

4 楼

你现在总研究高难题呀。

【在 k*******r 的大作中提到】

: 2维matrix装水问题，就是那个一维数组装水问题的扩展，求2维数组围成的池子能装
: 水的最大体积。
: 比方矩阵
: 333
: 303
: 333
: 装的最大水体积为3
: 这题怎么做，因为2维matrix围出的面积可以是各种各样的，凸的凹的都有可能，感觉
: 不容易找trival 算法阿

k*r2017-09-28 07:09

5 楼

hehe, 刚从leetcode上看到的，也是一线IT公司的面试题阿

H*r2017-09-28 07:09

6 楼

此题偶碰上过，没写code,搞半天整了个算法好像还不是最优...

【在 k*******r 的大作中提到】

w*y2017-09-28 07:09

7 楼

看不懂题目囧不知道example里那个3怎么来的......
我遇上这种题目就直接认死好了

S*t2017-09-28 07:09

8 楼

直接对边界floodfill一下，注意控制不要走到水里去(cells with 0 heights)，然后
对每个连通分量求值最小的元素就可以了。

g*i2017-09-28 07:09

9 楼

这以前是竞赛题了，网上搜下有标准解法的，面试的时候说出个思路（可以装着沉思一
会）我觉得就差不多了。

s*n2017-09-28 07:09

10 楼

怎么floodfill法？

【在 S******t 的大作中提到】

: 直接对边界floodfill一下，注意控制不要走到水里去(cells with 0 heights)，然后
: 对每个连通分量求值最小的元素就可以了。

S*t2017-09-28 07:09

11 楼

就直接四连通的floodfill啊...就是个DFS嘛
大概类似于
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};
bool valid(int r,int c) {
return 0<=r&&r}
void dfs(int x, int y)
visited[x][y] = true;
for(int i=0;i<4;i++) {
int nx=x+dx[i],ny=y+dy[i];
if(valid(nx,ny)&&!visited[nx][ny]&&d[nx][ny]!=0)
dfs(nx,ny);
}
}

【在 s******n 的大作中提到】

: 怎么floodfill法？

s*n2017-09-28 07:09

12 楼

floodfill怎么用来测积水?

【在 S******t 的大作中提到】

: 就直接四连通的floodfill啊...就是个DFS嘛
: 大概类似于
: const int dx[4] = {-1,1,0,0};
: const int dy[4] = {0,0,-1,1};
: bool valid(int r,int c) {
: return 0<=r&&r: }
: void dfs(int x, int y)
: visited[x][y] = true;
: for(int i=0;i<4;i++) {

S*t2017-09-28 07:09

13 楼

floodfill是找连通分量的
找完之后我们就知道池子的形状以及最低点的高度了

【在 s******n 的大作中提到】

: floodfill怎么用来测积水?

w*x2017-09-28 07:09

14 楼

以后leetcode能不能不贴这么难得题,每啥意思, ihasleetcode, 给你提点意见哈

b*t2017-09-28 07:09

15 楼

不过leetcode上的online judge最近新的题好像有变简单了的趋势

【在 w****x 的大作中提到】

: 以后leetcode能不能不贴这么难得题,每啥意思, ihasleetcode, 给你提点意见哈

d*u2017-09-28 07:09

16 楼

谁能普及一下一维数组装水，或者给个link?
谢谢

p*22017-09-28 07:09

17 楼

同意。

【在 w****x 的大作中提到】

: 以后leetcode能不能不贴这么难得题,每啥意思, ihasleetcode, 给你提点意见哈

H*r2017-09-28 07:09

18 楼

求标准解法！

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

: 这以前是竞赛题了，网上搜下有标准解法的，面试的时候说出个思路（可以装着沉思一
: 会）我觉得就差不多了。

t*e2017-09-28 07:09

19 楼

刘汝佳的《算法艺术与信息学竞赛》书上的例题，好像是在讲排序的那一章，这本书网
上有下载。面试考这题实在没意思，都是拿现成题目抄来抄去。

【在 H****r 的大作中提到】

: 求标准解法！

H*r2017-09-28 07:09

20 楼

强大，先谢后看

【在 t******e 的大作中提到】

: 刘汝佳的《算法艺术与信息学竞赛》书上的例题，好像是在讲排序的那一章，这本书网
: 上有下载。面试考这题实在没意思，都是拿现成题目抄来抄去。

m*k2017-09-28 07:09

21 楼

33333
34443
34343
34443
33333
for example, in this case, how do you define "找完之后"?
how about 金字塔顶上有一个小坑, but we have to start from the bottom.

【在 S******t 的大作中提到】

: floodfill是找连通分量的
: 找完之后我们就知道池子的形状以及最低点的高度了

t*e2017-09-28 07:09

22 楼

Can we solve one dimensional problem first for every row and column and
choose the smaller value at each intersection of row and column?
For example, the answer should be 2 for the middle point i.e smaller one
between row column.
323
303
333
I thought of counter example to my proposal. Need to consider the
neighbor's low as well. For example, answer is 1 instead 2 of both middle
point.
3213
3003
3333

i*r2017-09-28 07:09

23 楼

在这个matrix里面，有一些格子是禁止积水的
每次从禁止积水的格子里面取最低的一个做floodfill，同时扩展一些格子作为禁止积
水的格子
第一次从边缘上最低的格子开始
用一个binary heap来存放所有禁止积水的格子，复杂度mnlog(mn)

B*12017-09-28 07:09

24 楼

1337的online judge里面没有这题啊。难道我看错了？

【在 k*******r 的大作中提到】

f*22017-09-28 07:09

25 楼

没读懂题，求科普