由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Programming版 - [转载] CS Algorithm Interview question
相关主题
问个面试题目An interview question. Thanks.
Check if the sum of two integers in an integer array eqauls to the given number Re: amazon onsite interview question (转载)
在C/Fortran之间传递2维数组a probability interview question.
Θ(n)是什么意思?这个怎么allocate memory?
C/C++函数调用和栈内存一FG家常见题 (转载)
如何在fortran中定义一个动态的数组?问一个defining array 的问题
讨论几个面试题Java 的算法题:怎样把missing value替换成0 放在新生成的2D array里面?
If using C++, please avoid the use of STL for these questio (转载)这两种写法面試时候你喜欢哪种?
相关话题的讨论汇总
话题: int话题: array话题: interview话题: cs话题: algorithm
进入Programming版参与讨论
1 (共1页)
l***t
发帖数: 81
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****r
发帖数: 3557
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****r
发帖数: 3557
3
我的思路是这样的,预处理对每列作自上到下的部分和。
主循环取所有可能的两列为上下底的子矩阵,由部分和相减就能算出这个子矩阵
每列数不是全零,这样就是个一维的子问题很容易在\Theta(n)内解决。
X****r
发帖数: 3557
4
你这个思路好!正如netghost所说,第二步可以改进。
每行的一维问题不用O(mn), 只要O(n)就可以,这样最后的总复杂度就是O(mn)。
思路是维持一个栈,每个元素是高度和位置。
从左到右扫描一遍,对每个新遇到的高度,
将栈处理到栈顶元素的高度不比当前高度高为止——这些矩阵已经无法扩展了。
然后如果当前高度比栈顶元素高的话将当前高度和某一适当位置压栈。
原数组后要加0 以使最后栈能自动清空。
用如下子程序,在for(y=0;y int 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] ) {
1 (共1页)
进入Programming版参与讨论
相关主题
这两种写法面試时候你喜欢哪种?C/C++函数调用和栈内存
请问一个Python的问题。如何在fortran中定义一个动态的数组?
an interview question讨论几个面试题
An algorithm questionIf using C++, please avoid the use of STL for these questio (转载)
问个面试题目An interview question. Thanks.
Check if the sum of two integers in an integer array eqauls to the given number Re: amazon onsite interview question (转载)
在C/Fortran之间传递2维数组a probability interview question.
Θ(n)是什么意思?这个怎么allocate memory?
相关话题的讨论汇总
话题: int话题: array话题: interview话题: cs话题: algorithm