当前在线人数11812
首页 - 分类讨论区 - 电脑网络 - 葵花宝典版 -阅读文章
未名交友
[更多]
[更多]
文章阅读:Re: [转载] CS Algorithm Interview question
[同主题阅读] [版面: 葵花宝典] [作者:Xentar] , 2004年12月09日08:42:55
Xentar
进入未名形象秀
我的博客
[上篇] [下篇] [同主题上篇] [同主题下篇]

发信人: Xentar (好奇猪), 信区: Programming
标  题: Re: [转载] CS Algorithm Interview question
发信站: Unknown Space - 未名空间 (Thu Dec  9 08:46:38 2004), 转信

我的思路是这样的,预处理对每列作自上到下的部分和。
主循环取所有可能的两列为上下底的子矩阵,由部分和相减就能算出这个子矩阵
每列数不是全零,这样就是个一维的子问题很容易在\Theta(n)内解决。
【 在 netghost (dormdaze) 的大作中提到: 】
: 好像程序有点毛病.运行出seg fault.
: 不过你是用的以每一点作螺旋往外旋这个意思么?
: 我想到的做法就是以每点往外旋得到最大的1维的连续条,
: 如果对每行每列作预处理(suffix tree),这样可以转到某行和某列的时候,
: 在某个坐标上能够延伸的长度能够在constant time查出.
: 这样总共的时间应该在m*n的时间求出最大的0矩阵.
: 【 在 Xentar (好奇猪) 的大作中提到: 】
: : 看看这个\Theta(m^2 n)的对不对
: :
: : /* 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, v, mx ;
: :   s = (int**)malloc((m+1)*sizeof(int*));
: :   *s = (int*)malloc((m+1)*n*sizeof(int));
: :   d = (int*)malloc(n*sizeof(int));
: :   for( i = 0 ; i < m ; i ++ ) {
: :     s[i+1] = s[i]+n ;
: :   }
: :   /* calculate partial sums for each column */
: :   for( j = 0 ; j < n ; j ++ ) {
: :     s[0][j] = 0 ;
: :     for( i = 0 ; i < m ; i ++ ) {
: :       s[i+1][j] = s[i][j] + x[i][j] ;
: :     }
: :   }
: :   /* call findZeroArraySize1D for \Theta(m^2) times */
: :   mx = 0 ;
: :   for( ia = 0 ; ia < m ; ia ++ ) {
: :     for( ib = ia+1 ; ib <= m ; ib ++ ) {
: :       for( j = 0 ; j < n ; j ++ ) {
: :         d[j] = s[ib][j] - s[ia][j] ;
: :       }
: :       if( (v = findZeroArraySize1D(d,n)*(ib-ia)) > mx ) {
: :         mx = v ;
: :       }
: :     }
: :   }
: :   free(d);
: :   free(*s);
: :   free(s);
: :   return mx ;
: : }


--
我还在想猪的事

※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 128.220.]

[上篇] [下篇] [同主题上篇] [同主题下篇]
[转寄] [转贴] [回信给作者] [修改文章] [删除文章] [同主题阅读] [从此处展开] [返回版面] [快速返回] [收藏] [举报]
 
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996