[转载] CS Algorithm Interview question - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Programming - 葵花宝典

[转载] CS Algorithm Interview question

[转载] CS Algorithm Interview question# Programming - 葵花宝典

l*t2004-12-07 08:12

1 楼

【以下文字转载自 JobHunting 讨论区】
【原文由 lhict 所发表】
1. Create a function findZeroArraySize() that takes a 2-dimensions int array
, its width and its height as arguments. The array is filled with 0 and 1. T
he function returns the size (in int) of the biggest 2-dimensions sub-array
filled only with 0. This function should be as fast as possible.
Ex:
If argument is , function returns 9.
001011110
110001100
010000011
110001100
111011100

X*r2004-12-07 08:12

2 楼

看看这个\Theta(m^2 n)的对不
br />
/* find the max size of zero-filled 1-D array of integers
in \Theta(n) time
*/
int findZeroArraySize1D( int *x, int n ) {
int i, mx, mxp ;
mx = mxp = 0 ;
for( i = 0 ; i < n ; i ++ ) {
if( x[i] ) {
mxp = 0 ;
}else if( ++mxp > mx ) {
mx = mxp ;
}
}
return mx ;
}
/* find the max size of zero-filled 2-D array of non-negative integers
in \Theta(m^2 n) time
*/
int findZeroArraySize( int **x, int m, int n ) {
int **s, *d, i, j, ia, ib

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

: 【以下文字转载自 JobHunting 讨论区】
: 【原文由 lhict 所发表】
: 1. Create a function findZeroArraySize() that takes a 2-dimensions int array
: , its width and its height as arguments. The array is filled with 0 and 1. T
: he function returns the size (in int) of the biggest 2-dimensions sub-array
: filled only with 0. This function should be as fast as possible.
: Ex:
: If argument is , function returns 9.
: 001011110
: 110001100

X*r2004-12-07 08:12

3 楼

我的思路是这样的，预处理对每列作自上到下的部分和。
主循环取所有可能的两列为上下底的子矩阵，由部分和相减就能算出这个子矩阵
每列数不是全零，这样就是个一维的子问题很容易在\Theta(n)内解决。

X*r2004-12-07 08:12

4 楼

你这个思路好！正如netghost所说，第二步可以改进。
每行的一维问题不用O(mn), 只要O(n)就可以，这样最后的总复杂度就是O(mn)。
思路是维持一个栈，每个元素是高度和位置。
从左到右扫描一遍，对每个新遇到的高度，
将栈处理到栈顶元素的高度不比当前高度高为止——这些矩阵已经无法扩展了。
然后如果当前高度比栈顶元素高的话将当前高度和某一适当位置压栈。
原数组后要加0 以使最后栈能自动清空。
用如下子程序，在for(y=0;yint maxSize1D( const vector& v ) {
int best = 0 ;
vector vx(v), positions, heights;
vx.push_back( 0 );
for( int i = 0 ; i < vx.size() ; i ++ ) {
int leftest = i ;
while( heights.size() && heights[heights.size()-1] > vx[i] ) {