j***n 发帖数: 301 | 1 有道题目最近频繁出现,特地总结一下常规解法以及它的变体。有个经典变体我还没看
到一个很经典的答案,希望有人补上,呵呵。
1. The largest rectangle under a histogram
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
Given: An integer array represents a histogram
Goal: Find the largest rectangle under the histogram.
Key observation: 输入为一个整数数组。如果某元素比它两边的邻居都小(比如Ai),
那么高度大于Ai的矩阵要么在该元素左边,要么在该元素右边,不可能穿过Ai。利用这
个性质,想办法遍历所有的矩形。
Complexity O(N) where N is the size of the given array.
2. Maximum subarray with all 1’s. (Generalization of problem 1)
http: |
b******v 发帖数: 1493 | 2 great! thanks
【在 j***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有道题目最近频繁出现,特地总结一下常规解法以及它的变体。有个经典变体我还没看 : 到一个很经典的答案,希望有人补上,呵呵。 : 1. The largest rectangle under a histogram : http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html : Given: An integer array represents a histogram : Goal: Find the largest rectangle under the histogram. : Key observation: 输入为一个整数数组。如果某元素比它两边的邻居都小(比如Ai), : 那么高度大于Ai的矩阵要么在该元素左边,要么在该元素右边,不可能穿过Ai。利用这 : 个性质,想办法遍历所有的矩形。 : Complexity O(N) where N is the size of the given array.
|
c********t 发帖数: 1756 | |
l******4 发帖数: 207 | 4 shou cang
【在 j***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有道题目最近频繁出现,特地总结一下常规解法以及它的变体。有个经典变体我还没看 : 到一个很经典的答案,希望有人补上,呵呵。 : 1. The largest rectangle under a histogram : http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html : Given: An integer array represents a histogram : Goal: Find the largest rectangle under the histogram. : Key observation: 输入为一个整数数组。如果某元素比它两边的邻居都小(比如Ai), : 那么高度大于Ai的矩阵要么在该元素左边,要么在该元素右边,不可能穿过Ai。利用这 : 个性质,想办法遍历所有的矩形。 : Complexity O(N) where N is the size of the given array.
|
w****l 发帖数: 88 | |
j***n 发帖数: 301 | 6 谁来说说这个题的思路?
4. Imagine you have a square matrix, where each cell is filled with either b
lack or white. Design an algorithm to find the maximum subsquare such that a
ll four borders are filled with black pixels. (variation of problem 3)
http://careercup.com/question?id=2445
??? |
r****o 发帖数: 1950 | 7 谢谢你的总结。
能不能说下第2题的直方图是怎么构建的啊?多谢。
b
a
【在 j***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谁来说说这个题的思路? : 4. Imagine you have a square matrix, where each cell is filled with either b : lack or white. Design an algorithm to find the maximum subsquare such that a : ll four borders are filled with black pixels. (variation of problem 3) : http://careercup.com/question?id=2445 : ???
|
j***n 发帖数: 301 | 8 那个链接里面有,只是没叫直方图而已。我现在把那段代码截取注释一下。
输入是一个二维矩阵b,M行N列。
所谓的cache,也就是直方图,存在一个一维数组c里
c[0 .. M-1] = 0
main algorithm:
for x = N-1 .. 0 //从右向左扫描每一列
update_cache(x) //构造直方图
// 对c做直方图算法,找最大矩阵。
end main algorithm
define update_cache(x)
for y = 0 .. M-1
if b[x, y]!=0
c[y] = c[y]+1
else
c[y] = 0
【在 r****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢你的总结。 : 能不能说下第2题的直方图是怎么构建的啊?多谢。 : : b : a
|
m*****g 发帖数: 226 | 9 可以用那个D博士的遍历办法,预处理,然后检查每个可能的方块。O(n3)
b
a
【在 j***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谁来说说这个题的思路? : 4. Imagine you have a square matrix, where each cell is filled with either b : lack or white. Design an algorithm to find the maximum subsquare such that a : ll four borders are filled with black pixels. (variation of problem 3) : http://careercup.com/question?id=2445 : ???
|
m*****g 发帖数: 226 | |
|
|
m*****g 发帖数: 226 | |
m*****g 发帖数: 226 | 12 dobbs上面最后一题有笔误
一开始的c[0 .. M-1] = 0
应为c[0 .. M] =0 |
j**l 发帖数: 2911 | 13 有笔误,x代表列,y代表行,所以应该是b[y, x]而不是b[x, y]
c[0 .. M-1] = 0
main algorithm:
for x = N-1 .. 0 //从右向左扫描每一列
update_cache(x) //构造直方图
// 对c做直方图算法,找最大矩阵。
end main algorithm
define update_cache(x)
for y = 0 .. M-1
if b[y, x]!=0
c[y] = c[y]+1
else
c[y] = 0 |
b***u 发帖数: 61 | 14 第4题 如果只是要求四个顶点是黑的 应该怎么做呢? |
m*****g 发帖数: 226 | 15 硬来
【在 b***u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第4题 如果只是要求四个顶点是黑的 应该怎么做呢?
|