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

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

看看这个\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 ;
}

【 在 lhict (至少还有我) 的大作中提到: 】
: O(n^2 m^2)算法怎么做?
: 还是想不通。。。
: 【 在 netghost (dormdaze) 的大作中提到: 】
: : 感觉要利用0,1做文章.
: : 否则一般情况,我觉得不好作.


--
我还在想猪的事

※ 修改:.Xentar 于 Dec  8 09:53:00 修改本文.[FROM: 128.220.]
※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 128.220.]

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

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

友情链接


 

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

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