k*******r
发帖数: 355 | 1 2维matrix装水问题， 就是那个一维数组装水问题的扩展，求2维数组围成的池子能装
水的最大体积。
比方矩阵
333
303
333
装的最大水体积为3
这题怎么做，因为2维matrix围出的面积可以是各种各样的，凸的凹的都有可能，感觉
不容易找trival 算法阿 |
p*****2
发帖数: 21240 | 2
你现在总研究高难题呀。
【在 k*******r 的大作中提到】
: 2维matrix装水问题， 就是那个一维数组装水问题的扩展，求2维数组围成的池子能装
: 水的最大体积。
: 比方矩阵
: 333
: 303
: 333
: 装的最大水体积为3
: 这题怎么做，因为2维matrix围出的面积可以是各种各样的，凸的凹的都有可能，感觉
: 不容易找trival 算法阿
|
k*******r
发帖数: 355 | 3 hehe, 刚从leetcode上看到的，也是一线IT公司的面试题阿 |
H****r
发帖数: 2801 | 4 此题偶碰上过，没写code,搞半天整了个算法好像还不是最优...
【在 k*******r 的大作中提到】
: 2维matrix装水问题， 就是那个一维数组装水问题的扩展，求2维数组围成的池子能装
: 水的最大体积。
: 比方矩阵
: 333
: 303
: 333
: 装的最大水体积为3
: 这题怎么做，因为2维matrix围出的面积可以是各种各样的，凸的凹的都有可能，感觉
: 不容易找trival 算法阿
|
w***y
发帖数: 6251 | 5 看不懂题目 囧 不知道example里那个3怎么来的......
我遇上这种题目就直接认死好了 |
S******t
发帖数: 151 | 6 直接对边界floodfill一下，注意控制不要走到水里去(cells with 0 heights)，然后
对每个连通分量求值最小的元素就可以了。 |
g*****i
发帖数: 2162 | 7 这以前是竞赛题了，网上搜下有标准解法的，面试的时候说出个思路（可以装着沉思一
会）我觉得就差不多了。 |
s******n
发帖数: 3946 | 8 怎么floodfill法？
【在 S******t 的大作中提到】
: 直接对边界floodfill一下，注意控制不要走到水里去(cells with 0 heights)，然后
: 对每个连通分量求值最小的元素就可以了。
|
S******t
发帖数: 151 | 9 就直接四连通的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******n
发帖数: 3946 | 10 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******t
发帖数: 151 | 11 floodfill是找连通分量的
找完之后我们就知道池子的形状以及最低点的高度了
【在 s******n 的大作中提到】
: floodfill怎么用来测积水?
|
w****x
发帖数: 2483 | 12 以后leetcode能不能不贴这么难得题,每啥意思, ihasleetcode, 给你提点意见哈 |
b******t
发帖数: 965 | 13 不过leetcode上的online judge最近新的题好像有变简单了的趋势
【在 w****x 的大作中提到】
: 以后leetcode能不能不贴这么难得题,每啥意思, ihasleetcode, 给你提点意见哈
|
d******u
发帖数: 397 | 14 谁能普及一下一维数组装水，或者给个link?
谢谢 |
p*****2
发帖数: 21240 | 15
同意。
【在 w****x 的大作中提到】
: 以后leetcode能不能不贴这么难得题,每啥意思, ihasleetcode, 给你提点意见哈
|
H****r
发帖数: 2801 | 16 求标准解法！
【在 g*****i 的大作中提到】
: 这以前是竞赛题了，网上搜下有标准解法的，面试的时候说出个思路（可以装着沉思一
: 会）我觉得就差不多了。
|
t******e
发帖数: 98 | 17 刘汝佳的《算法艺术与信息学竞赛》书上的例题，好像是在讲排序的那一章，这本书网
上有下载。面试考这题实在没意思，都是拿现成题目抄来抄去。
【在 H****r 的大作中提到】
: 求标准解法！
|
H****r
发帖数: 2801 | 18 强大，先谢后看
【在 t******e 的大作中提到】
: 刘汝佳的《算法艺术与信息学竞赛》书上的例题，好像是在讲排序的那一章，这本书网
: 上有下载。面试考这题实在没意思，都是拿现成题目抄来抄去。
|
m*****k
发帖数: 731 | 19 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********e
发帖数: 143 | 20 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******r
发帖数: 793 | 21 在这个matrix里面，有一些格子是禁止积水的
每次从禁止积水的格子里面取最低的一个做floodfill，同时扩展一些格子作为禁止积
水的格子
第一次从边缘上最低的格子开始
用一个binary heap来存放所有禁止积水的格子，复杂度mnlog(mn) |
B*******1
发帖数: 2454 | 22 1337的online judge里面没有这题啊。 难道我看错了？
【在 k*******r 的大作中提到】
: 2维matrix装水问题， 就是那个一维数组装水问题的扩展，求2维数组围成的池子能装
: 水的最大体积。
: 比方矩阵
: 333
: 303
: 333
: 装的最大水体积为3
: 这题怎么做，因为2维matrix围出的面积可以是各种各样的，凸的凹的都有可能，感觉
: 不容易找trival 算法阿
|
f**********2
发帖数: 2401 | |
