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

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

你这个思路好!正如netghost所说,第二步可以改进。
每行的一维问题不用O(mn), 只要O(n)就可以,这样最后的总复杂度就是O(mn)。
思路是维持一个栈,每个元素是高度和位置。
从左到右扫描一遍,对每个新遇到的高度,
将栈处理到栈顶元素的高度不比当前高度高为止——这些矩阵已经无法扩展了。
然后如果当前高度比栈顶元素高的话将当前高度和某一适当位置压栈。
原数组后要加0 以使最后栈能自动清空。

用如下子程序,在for(y=0;y<height;y++)的循环里调:(没有测试和优化过)
int maxSize1D( const vector<int>& v ) {
  int best = 0 ;
  vector<int> 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] ) {
      leftest = positions[positions.size()-1] ;
      best = max(best, heights[heights.size()-1]*(i-leftest));
      heights.pop_back();
      positions.pop_back();
    }
    if( vx[i] && (!heights.size() || vx[i] > heights[heights.size()-1]) ) {
      positions.push_back( leftest );
      heights.push_back( vx[i] );
    }
  }
  return best ;
}
【 在 Pront (阿呆) 的大作中提到: 】
: 因为没有说明,所以我不是很明白你的算法。不过我猜可能跟我的思路差不多。
: 下面是程序,效率为(height* height * width). 基本上,先计算每个位置
: 往上数连续0的个数,然后对每行,计算以该行为底的RECT最大可能的SIZE.
: 如:
: 11000
: 10001
: 01101
: 计算连续0个数为:
: 00111
: 01220
: 10030
: 第一行为底的最大RECT SIZE 为3,
: 第二行,两个连续 2 应该是最大,SIZE=4.
: 第三行,最大的 size=3.
: So max = 4.
: 以下为源程序:
: #ifdef WIN32
: #pragma warning(disable:4786 4101)
: #define min _MIN
: #define max _MAX
: #endif
: #include <vector>
: #include <string>
: #include <iostream>
: using namespace std;
: int maxSize(vector<string>& v)
: {
:     int height = v.size();
:     int width = v.size()? v[0].size() : 0;
:     int y, x;
:     vector<vector<int> > hs(height, vector<int>(width, 0));
:     for(y = 0; y < height; y++)
:         for(x = 0; x < width; x++)
:             if (v[y][x] == '0')
:                 hs[y][x] = (y == 0)? 1 : (hs[y-1][x] + 1);
:     int best = 0;
:     for(y = 0; y < height; y++)
:         for(int mx = 1; mx <= height; mx++)
:         {
:             int start = -1;
:             for(x = 0; x <= width; x++)
:             {
:                 if (x < width && hs[y][x] >= mx)
:                 {
:                     if (start < 0) start = x;
:                 }
:                 else
:                 {
:                     if (start >= 0)
:                     {
:                         int size = (x - start) * mx;
:                         best = max(best, size);
:                         start = -1;
:                     }
:                 }
:             }
:         }
:     return best;
: }
: int main()
: {
:     vector<string> v;
:     v.push_back("0011101001000111");
:     v.push_back("0111000000010111");
:     v.push_back("0011100001000111");
:     v.push_back("0011100001000111");
:     v.push_back("0010100101100111");
:     v.push_back("0011101001000111");
:     cout << maxSize(v) << endl;
:     return 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 ;
: :       }
: :     }
: :   }


--
我还在想猪的事

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

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

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

友情链接


 

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

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