没人发这消息？？？？？？？？？？？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>PDA - 掌中宝

没人发这消息？？？？？？？？？？？

没人发这消息？？？？？？？？？？？# PDA - 掌中宝

h*k2011-12-09 08:12

1 楼

Have a matrix, where each cell is filled with either 1 or 0. Design an
algorithm to find the maximum subsquare such that all four borders are
filled with 1.
For example
0 0 0 0 0 0
0 1 1 1 0 0
0 1 0 1 0 0
0 1 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
The cell inside the subsquare may be filled by 1 or 0.

F*e2011-12-09 08:12

2 楼

果子在德国跟moto的官司输了哈哈哈哈哈哈哈大小三声等着moto给果子提建议
★ 发自iPhone App: ChineseWeb - 中文网站浏览器

t*a2011-12-09 08:12

3 楼

只能想到 DFS or BFS填空
O(n^2)
有人可以有好办法么？

j*l2011-12-09 08:12

4 楼

俺们果子还看不上德国市场，哼
--果粉

h*k2011-12-09 08:12

5 楼

如果是O(n^2)，肯定是最优解了。
请问怎么用DFS填空？

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

: 只能想到 DFS or BFS填空
: O(n^2)
: 有人可以有好办法么？

g*g2011-12-09 08:12

6 楼

烂果子折腾了一整年，貌似逼迫三星在德国市场稍微修改了
Gtab的外形设计，其余的官司全输了。

【在 F*********e 的大作中提到】

: 果子在德国跟moto的官司输了哈哈哈哈哈哈哈大小三声等着moto给果子提建议
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

q*r2011-12-09 08:12

7 楼

是不是把所有的全是0的行或列去掉就是了

【在 h**k 的大作中提到】

: Have a matrix, where each cell is filled with either 1 or 0. Design an
: algorithm to find the maximum subsquare such that all four borders are
: filled with 1.
: For example
: 0 0 0 0 0 0
: 0 1 1 1 0 0
: 0 1 0 1 0 0
: 0 1 1 1 0 0
: 0 0 0 0 0 0
: 0 0 0 0 0 0

t*a2011-12-09 08:12

8 楼

想法很简单。
随便从某个为0的位置开始做BFS，访问到的地方置2（被1包起来的），记录下本次所有
访问的节
点，如果遇到非1非2的数字或者遇到外围边界就把本次所有访问到的置3（没办法包起
来的），如
果本次搜索仅仅碰到了0或者1那很好就是包起来的，记录下填空的个数。反复填空直到
填满为
止，选出最大的那个。

【在 h**k 的大作中提到】

: 如果是O(n^2)，肯定是最优解了。
: 请问怎么用DFS填空？

h*k2011-12-09 08:12

9 楼

不是，在给出的例子里可以这么做。但是别的例子里这个方法不对。

【在 q**r 的大作中提到】

: 是不是把所有的全是0的行或列去掉就是了

h*62011-12-09 08:12

10 楼

可以这样，沿着边界走一圈，把边界上的所有0和与之相邻的所有0全部改为3，然后把
其余的0改为1，这样就变成找由1构成的最大的正方形问题。

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

: 想法很简单。
: 随便从某个为0的位置开始做BFS，访问到的地方置2（被1包起来的），记录下本次所有
: 访问的节
: 点，如果遇到非1非2的数字或者遇到外围边界就把本次所有访问到的置3（没办法包起
: 来的），如
: 果本次搜索仅仅碰到了0或者1那很好就是包起来的，记录下填空的个数。反复填空直到
: 填满为
: 止，选出最大的那个。

P*t2011-12-09 08:12

11 楼

This wrong. e.g:
1110
1011
1001
1111

【在 h**6 的大作中提到】

: 可以这样，沿着边界走一圈，把边界上的所有0和与之相邻的所有0全部改为3，然后把
: 其余的0改为1，这样就变成找由1构成的最大的正方形问题。

P*t2011-12-09 08:12

12 楼

How to find the biggest? If you fill 0's I don't think it will work...
e.g.:
110
101
110

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

h*k2011-12-09 08:12

13 楼

对，这正是我想问的。你必须只能填充正方形框里的0。

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

: This wrong. e.g:
: 1110
: 1011
: 1001
: 1111

t*a2011-12-09 08:12

14 楼

填充完毕检测一下边界

【在 h**k 的大作中提到】

: 对，这正是我想问的。你必须只能填充正方形框里的0。

P*t2011-12-09 08:12

15 楼

Why will fill in help? Will it simplify how you find the max square?

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

: 填充完毕检测一下边界

t*a2011-12-09 08:12

16 楼

你说的有道理。那干脆就BFS 1，顺时针转，检查是不是正方形，之后算面积。

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

: Why will fill in help? Will it simplify how you find the max square?

p*72011-12-09 08:12

17 楼

1 1 1 1 0 1
1 1 1 1 1 1
1 1 0 1 0 1
0 1 1 1 0 1
1 1 0 1 0 1
1 1 1 1 1 1
下面这个表是这么建立的
1 2 3 4 0 1
1 2 3 4 5 6
1 2 0 1 0 1
0 1 2 3 0 1
1 2 0 1 0 1
1 2 3 4 5 6
1 1 1 1 0 1
2 2 2 2 1 2
3 3 0 3 0 3
0 4 1 4 0 4
1 5 0 5 0 5
2 6 1 6 1 6
合并上2个表变成下面这个，用dp
1 1 1 1 0 1 表示从这点到左，以及到上都是1的数量 B1
1 2 2 2 1 2
1 2 0 1 0 1
0 2 1 3 0 1
1 2 0 1 0 1
1 2 1 4 1 6
同理，从下往上，从右往左，获得下面这个表
2 2 2 1 0 1 表示从这点到右，以及到下都是1 的数量 B2
2 5 1 3 1 1
1 1 0 1 0 1
0 3 1 1 0 1
2 1 0 1 0 1
1 1 1 1 1 1
建立 C表
C[i,j] = min(B1[i,j],B2[i-B1[i,j]+1

h*62011-12-09 08:12

18 楼

楼上O(N^2)的解法应该修改一下：
沿45度线上各数字是：2 5 0 1 0 1，对应另一组数字：1 2 0 3 0 6，最终求出5和6的
重叠区域为5。
这个问题可以等效于求一些已根据起始点排序的区间的最大重叠区域长度。
首先，列出正向排序的区间：2 5 0 1 0 1
然后，把反向区间转换成用起始位置和长度表示，并取代同一起始点长度较短的区间，
得到 6 5 0 1 0 1
最后，每个区间只和前面所有区间求交集，方法是用前面所有区间的最后结束位置减去
当前区间的起始位置，可以用O(N)的算法求出最大重叠长度。

h*k2011-12-09 08:12

19 楼

但是这个只是一种可能的对角线；一共有2n-1个对角线需要处理。

【在 h**6 的大作中提到】

: 楼上O(N^2)的解法应该修改一下：
: 沿45度线上各数字是：2 5 0 1 0 1，对应另一组数字：1 2 0 3 0 6，最终求出5和6的
: 重叠区域为5。
: 这个问题可以等效于求一些已根据起始点排序的区间的最大重叠区域长度。
: 首先，列出正向排序的区间：2 5 0 1 0 1
: 然后，把反向区间转换成用起始位置和长度表示，并取代同一起始点长度较短的区间，
: 得到 6 5 0 1 0 1
: 最后，每个区间只和前面所有区间求交集，方法是用前面所有区间的最后结束位置减去
: 当前区间的起始位置，可以用O(N)的算法求出最大重叠长度。

h*62011-12-09 08:12

20 楼

是的，每个对角线用O(N)的时间就能解决，总的复杂度是O(N^2)。

【在 h**k 的大作中提到】

: 但是这个只是一种可能的对角线；一共有2n-1个对角线需要处理。

h*k2011-12-09 08:12

21 楼

how about this case?
1 1 0 1
1 0 0 1
0 0 0 1
1 1 1 1
B1 should be
1 1 0 1
1 0 0 1
0 0 0 1
1 1 1 4
B2 should be
2 1 0 1
1 0 0 1
0 0 0 1
1 1 1 1
right?
c(4,4) should be 2?

【在 p********7 的大作中提到】

: 1 1 1 1 0 1
: 1 1 1 1 1 1
: 1 1 0 1 0 1
: 0 1 1 1 0 1
: 1 1 0 1 0 1
: 1 1 1 1 1 1
: 下面这个表是这么建立的
: 1 2 3 4 0 1
: 1 2 3 4 5 6
: 1 2 0 1 0 1

h*k2011-12-09 08:12

22 楼

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
你需要每个区间都和前面区间进行比较？那这个操作本身就是O(n^2)。另外，你这个算
法能处理上面我给出的那个例子么？

【在 h**6 的大作中提到】

h*62011-12-09 08:12

23 楼

借用paul198247的例子2 5 0 1 0 1和1 2 0 3 0 6来说明一下吧。
2 5 0 1 0 1分别表示长度为这些数字，起始位置为1~6的区间
1 2 0 3 0 6分别表示长度为这些数字，结束位置为1~6的区间，
其起始位置可以算出，是1 1 0 2 0 1
把这些区间全部合并，相同起始位置只保留最长的区间，得到6 5 0 1 0 1
求每个区间与前面所有区间的重叠，只需要把前面所有区间的最后
结束位置减去该区间起始位置即可。而这个所有区间的最后结束位
置是递不减的，每加上一个新区间，最多需要更新一次。
也分析下hock的例子：
B2的主对角线2 0 0 1，B1的主对角线1 0 0 4，合并为4 0 0 1，重叠部分长度为1。

h*k2011-12-09 08:12

24 楼

重叠的含义是什么啊？我猜测是这个意思，6表示从1开始的长度为6的区间，所以指区
间（1，6），第二个位置为5，指区间（2，6），重叠是（2，6）；对么？
你最后的输出是什么？任意两个区间的重叠中的最大值？
所有区间的结束位置是递不减的？这个是什么意思？
再给几个例子，你的算法如何处理
如果B2对角线是3001，B1对角线是1003，你新生成的区间序列是3301，对么？
算法的输出是多少？
如果B2对角线是4001，B1对角线是1004，你新生成的区间序列是4001，对么？
算法的输出是多少？
如果B2对角线是3001，B1对角线是1004，你新生成的区间序列是4001，对么？
算法的输出是多少？

【在 h**6 的大作中提到】

: 借用paul198247的例子2 5 0 1 0 1和1 2 0 3 0 6来说明一下吧。
: 2 5 0 1 0 1分别表示长度为这些数字，起始位置为1~6的区间
: 1 2 0 3 0 6分别表示长度为这些数字，结束位置为1~6的区间，
: 其起始位置可以算出，是1 1 0 2 0 1
: 把这些区间全部合并，相同起始位置只保留最长的区间，得到6 5 0 1 0 1
: 求每个区间与前面所有区间的重叠，只需要把前面所有区间的最后
: 结束位置减去该区间起始位置即可。而这个所有区间的最后结束位
: 置是递不减的，每加上一个新区间，最多需要更新一次。
: 也分析下hock的例子：
: B2的主对角线2 0 0 1，B1的主对角线1 0 0 4，合并为4 0 0 1，重叠部分长度为1。

p*72011-12-09 08:12

25 楼

应该还需要加一个判断
2 2 2 1 0 1 表示从这点到右，以及到下都是1 的数量 B2
2 5 1 3 1 1
1 1 0 1 0 1
0 3 1 1 0 1
2 1 0 1 0 1
1 1 1 1 1 1
在遍历C【I，J】的时候，需要算2次，一次是先找min(B1[i,j],B2[i-B1[i,j]+1,j-B1[i,j]+1]);如果这个值是等于B1【i，j】那么就更新C【I，J】。如果是小于的，那么就不变。
然后再算min（B2【I，J】，B1（I+B2[I,J]-1,J+B2[I,J]-1））如果这个数等于B2【I，J】那么就更新C【I+B2【I，J】-1，J+B2【I，J】-1】
其实我在遍历C【1，1】的时候已经得到C【5，5】 = 5；当遍历C【5，5】获得的数是2，其实是小于6的，所以无效，就不更新了。
你这个例子C【3，3】获得是2，是小于B1【3，3】==4的，所以无效。

B2 should be
2 1 0 1
1 0 0 1
0 0 0 1
1 1 1 1

【在 h**k 的大作中提到】

: how about this case?
: 1 1 0 1
: 1 0 0 1
: 0 0 0 1
: 1 1 1 1
: B1 should be
: 1 1 0 1
: 1 0 0 1
: 0 0 0 1
: 1 1 1 4

h*k2011-12-09 08:12

26 楼

B1[i,j]+1]);如果这个值是等于B1【i，j】那么就更新C【I，J】。如果是小于的，那
么就不变。
I，J】那么就更新C【I+B2【I，J】-1，J+B2【I，J】-1】
你这段是指B1[i,j]<=B2[i-B1[i,j]+1, j-B1[i,j]+1],则 c[i,j]=B1[i,j]? 我理解对
么？那么B1[i,j] > B2[i-B1[i,j]+1, j-B1[i,j]+1]的话，c[i,j]值不变是什么意思，
c[i,j]的值是多少？
你能写个公式，讲讲在各种情况下如何用B1和B2来计算c[i,j]？而且这个计算必须是O(
1)的，否则无法保证整个算法是O(n^2)的。
总的来说，我感觉这么一个公式不存在，因为对每一个点(i,j)，你必须检测边长从2到
B2[i,j]的所有可能正方形，看是否真能构成正方形。而只检测变成为B2[i,j]是肯定不
对的。
是2，其实是小于6的，所以无效，就不更新了。

【在 p********7 的大作中提到】

: 应该还需要加一个判断
: 2 2 2 1 0 1 表示从这点到右，以及到下都是1 的数量 B2
: 2 5 1 3 1 1
: 1 1 0 1 0 1
: 0 3 1 1 0 1
: 2 1 0 1 0 1
: 1 1 1 1 1 1
: 在遍历C【I，J】的时候，需要算2次，一次是先找min(B1[i,j],B2[i-B1[i,j]+1,j-B1[i,j]+1]);如果这个值是等于B1【i，j】那么就更新C【I，J】。如果是小于的，那么就不变。
: 然后再算min（B2【I，J】，B1（I+B2[I,J]-1,J+B2[I,J]-1））如果这个数等于B2【I，J】那么就更新C【I+B2【I，J】-1，J+B2【I，J】-1】
: 其实我在遍历C【1，1】的时候已经得到C【5，5】 = 5；当遍历C【5，5】获得的数是2，其实是小于6的，所以无效，就不更新了。

h*62011-12-09 08:12

27 楼

这是我的寻找最大重叠区间的代码，复杂度为O(n)。
a为B2对角线平行线，b为B1对角线平行线，n为a和b的长度。
int IntervalOverlap(int* a, int* b, int n)
{
int* c = new int[n];
for(int i=0; ic[i] = a[i];
int maxlen = 0;
for(int i=0; i{
int start = i-b[i]+1;
maxlen = max(maxlen, min(c[start], b[i]));
c[start] = max(c[start], b[i]);
}
int maxend = c[0];
for(int i=1; i{
int curlen = min(maxend, c[i]+i) - i;
maxlen = max(maxlen,

h*62011-12-09 08:12

28 楼

总结一下，矩阵B1和B2共有2n-1条与主对角线平行的线段，可以转化为2n-1个区间最大
重叠问题。
给定任意区间，求两两重叠的最大长度，其复杂度为O(logn)。
但本题的区间较为特殊，
1.所有区间已按照开始位置排序
2.相同开始位置的区间已按照区间长度排序
因此本题的区间最大重叠问题可以在O(n)内解决，如上代码。
总复杂度为O(n^2)。

h*k2011-12-09 08:12

29 楼

假设B2对角线为[2 0 0 1]，B1对角线平行线为[1 0 0 4]，则运行完第一个循环，C为[
4 0 0 1]，maxlen = 2，对么？第二个循环不改变maxlen的值，最后输出是2，对么？
然而对于这个case，正确的答案是1。

【在 h**6 的大作中提到】

: 这是我的寻找最大重叠区间的代码，复杂度为O(n)。
: a为B2对角线平行线，b为B1对角线平行线，n为a和b的长度。
: int IntervalOverlap(int* a, int* b, int n)
: {
: int* c = new int[n];
: for(int i=0; i: c[i] = a[i];
: int maxlen = 0;
: for(int i=0; i: {

p*72011-12-09 08:12

30 楼

1 1 1 1 0 1 表示从这点到左，以及到上都是1的数量 B1
1 2 2 2 1 2
1 2 0 1 0 1
0 2 1 3 0 1
1 2 0 1 0 1
1 2 1 4 1 6
同理，从下往上，从右往左，获得下面这个表
2 2 2 1 0 1 表示从这点到右，以及到下都是1 的数量 B2
2 5 1 3 1 1
1 1 0 1 0 1
0 3 1 1 0 1
2 1 0 1 0 1
1 1 1 1 1 1
////////////// 下面这个是错的，以前写的
C[i,j] = min(B1[i,j],B2[i-B1[i,j]+1,j-B1[i,j]+1]);
复杂度是O(N^2)
/////////////////////////
更新后是这样的
在遍历C【I，J】的时候，需要算2次，一次是先找min(B1[i,j],B2[i-B1[i,j]+1,j-B1[
i,j]+1]);如果这个值是等于B1【i，j】那么就更新C【I，J】。如果是小于的，那么就
不变。
然后再算min（B2【I，J】，B1（I+B2[I,J]-1,J+B2[I,J]-1））如果这个数等于B2【

【在 h**k 的大作中提到】

: 假设B2对角线为[2 0 0 1]，B1对角线平行线为[1 0 0 4]，则运行完第一个循环，C为[
: 4 0 0 1]，maxlen = 2，对么？第二个循环不改变maxlen的值，最后输出是2，对么？
: 然而对于这个case，正确的答案是1。

p*72011-12-09 08:12

31 楼

1 1 1 1 0 1 表示从这点到左，以及到上都是1的数量 B1
1 2 2 2 1 2
1 2 0 1 0 1
0 2 1 3 0 1
1 2 0 1 0 1
1 2 1 4 1 6
同理，从下往上，从右往左，获得下面这个表
2 2 2 1 0 1 表示从这点到右，以及到下都是1 的数量 B2
2 5 1 3 1 1
1 1 0 1 0 1
0 3 1 1 0 1
2 1 0 1 0 1
1 1 1 1 1 1
一个点需要做2次计算，一次是从B1，一次从B2
比如C【1，1】在B1【1，1】 == 2，在B2【0，0】==2所以C【1，1】=2；
B2【1，1】 == 5，B1【1+5-1，1+5-1】==6>=5，所以C【1+5-1，1+5-1】=5 即C【5，5
】=5；
比如C【5，5】在B1【5，5】== 6表示【5，5】这个点往上的边和left side是连续有6
个点，我们需要找到对应对角线那个点就是【0，0】在B2的数值，如果这个数为6，那
么这个正方形就是可以边为6的。但是B2【0，0】==2，所以边不能为6.
C【5，5】在B2【5，5】==1，B【5-1

【在 h**k 的大作中提到】

t*q2011-12-09 08:12

32 楼

不work
00010
01111
01010
11110
01000

【在 p********7 的大作中提到】

: 1 1 1 1 0 1 表示从这点到左，以及到上都是1的数量 B1
: 1 2 2 2 1 2
: 1 2 0 1 0 1
: 0 2 1 3 0 1
: 1 2 0 1 0 1
: 1 2 1 4 1 6
: 同理，从下往上，从右往左，获得下面这个表
: 2 2 2 1 0 1 表示从这点到右，以及到下都是1 的数量 B2
: 2 5 1 3 1 1
: 1 1 0 1 0 1

h*62011-12-09 08:12

33 楼

大家来挑战这个矩阵吧，以下代码生成了一个10000*10000的矩阵，函数GetMaxSquare
返回最大的四边为1的正方形边长，我的计算结果是1807，O(n^2logn)算法耗时96.406
秒，O(n^3)算法耗时1263.265秒。
void main()
{
int n = 10000;
int **A = new int*[n];
for(int i=0; iA[i] = new int[n];
unsigned int seed = 0x59DDC;
for(int i=0; i{
seed = seed*0x343FD + 0x269EC3;
int r = i/(n/16), c = i%(n/16);
for(int j=0; j<16; j++)
A[r][c*16+j] = (seed&(255< 0;
}
int x = GetMaxSquare(A,

p*72011-12-09 08:12

34 楼

B1
00010
04121
01010
12110
01000
B2
00010
01121
01010
12130
01000
C
在遍历1,1的时候B1【1，1】==4，查看B2【1+4-1,1+4-1】==0
SO C【3，3】= 0
在遍历3，3的时候，B2【3，3】==3，查看B1【3-3+1，3-3+1】==4 >=3,SO
C【3，3】= 3；
为何不work？ C【i,j】== x 表示从以【i j】为右下的正方形，边长是x

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

: 不work
: 00010
: 01111
: 01010
: 11110
: 01000

b*n2011-12-09 08:12

35 楼

题目换成找长方形后,会有什么变化?

t*q2011-12-09 08:12

36 楼

B1 B2是怎么计算的？
B1(1,1)难道不是4吗？

【在 p********7 的大作中提到】

: B1
: 00010
: 04121
: 01010
: 12110
: 01000
: B2
: 00010
: 01121
: 01010

p*72011-12-09 08:12

37 楼

sorry, it's 4.
I have added more common in previous algorithm.
please check.
It works.

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

: B1 B2是怎么计算的？
: B1(1,1)难道不是4吗？

p*72011-12-09 08:12

38 楼

在遍历矩阵的时候，你必须check两次，先B1，然后B2，看是否可能有正方形

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

: B1 B2是怎么计算的？
: B1(1,1)难道不是4吗？

p*72011-12-09 08:12

39 楼

我的方法就不work了，不过长方形怎么比较最大？面积？

【在 b*****n 的大作中提到】

: 题目换成找长方形后,会有什么变化?

b*n2011-12-09 08:12

40 楼

对,面积.听说有人被一著名公司问过.

【在 p********7 的大作中提到】

: 我的方法就不work了，不过长方形怎么比较最大？面积？

p*72011-12-09 08:12

41 楼

你说的不是这个题，我知道那个题是不是求矩阵中最大矩形面积，矩形内部都是1吧，
这个题
是空心的也行，不要求内部都是1.不一样的。如果矩形可以是空心，那就没好办法了
。如果
矩形是实心，可以用histogram 最大面积那个方法做，复杂度是O（N*M）N和M是矩阵长宽

【在 b*****n 的大作中提到】

: 对,面积.听说有人被一著名公司问过.

b*n2011-12-09 08:12

42 楼

我听到的是求最大面积的长方形(四边).不要求是实心的.

长宽

【在 p********7 的大作中提到】

: 你说的不是这个题，我知道那个题是不是求矩阵中最大矩形面积，矩形内部都是1吧，
: 这个题
: 是空心的也行，不要求内部都是1.不一样的。如果矩形可以是空心，那就没好办法了
: 。如果
: 矩形是实心，可以用histogram 最大面积那个方法做，复杂度是O（N*M）N和M是矩阵长宽

h*62011-12-09 08:12

43 楼

But B2(3, 3) is 4

【在 p********7 的大作中提到】

: sorry, it's 4.
: I have added more common in previous algorithm.
: please check.
: It works.

t*q2011-12-09 08:12

44 楼

B2(3,3)也是4，老大

【在 p********7 的大作中提到】

: sorry, it's 4.
: I have added more common in previous algorithm.
: please check.
: It works.

p*72011-12-09 08:12

45 楼

sorry, 那复杂度就不是N^2，需要沿着对角线遍历一次。复杂是N^3

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

: B2(3,3)也是4，老大

p*72011-12-09 08:12

46 楼

需要沿着对角线遍历一次，复杂度是N^3

【在 h**6 的大作中提到】

: But B2(3, 3) is 4

p*72011-12-09 08:12

47 楼

N^2 LogN 是怎么搞的

GetMaxSquare
406

【在 h**6 的大作中提到】

: 大家来挑战这个矩阵吧，以下代码生成了一个10000*10000的矩阵，函数GetMaxSquare
: 返回最大的四边为1的正方形边长，我的计算结果是1807，O(n^2logn)算法耗时96.406
: 秒，O(n^3)算法耗时1263.265秒。
: void main()
: {
: int n = 10000;
: int **A = new int*[n];
: for(int i=0; i: A[i] = new int[n];
: unsigned int seed = 0x59DDC;

h*62011-12-09 08:12

48 楼

沿着对角线遍历一次，复杂度仍然是O(N^2)。因为每条对角线都只需要寻找比以前更大
的边长，也就是更大的B1、B2值。虽然遍历单条对角线复杂度是O(N^2)，但对角线的值
都是相关的，因此遍历全部对角线的复杂度也是O(N^2)。
通过运行时间也能看出来，同样是10000*10000的矩阵：
剪枝之前，O(n^2logn)算法耗时96.406秒，O(n^3)算法耗时1263.265秒。
剪枝之后，两个算法运行时间分别为10.156秒和9.375秒。此时复杂度相同，前一个算法因较复杂开销更大故更慢。

【在 p********7 的大作中提到】

: 需要沿着对角线遍历一次，复杂度是N^3

p*72011-12-09 08:12

49 楼

我用10000*10000差点运行死机了，但是5000*5000就很快出结果了，估计4秒。其中执行下面的算法就用了半秒，分配其他几个矩阵用了很多时间
int largest = 0;
for(i = 0;ifor(j=0;j{
if(B[i][j]>largest)
{
int index = B[i][j];
while(index > largest)
{
if(C[i-index+1][j-index+1]>largest)
largest = index;
index--;
}
}
if(C[i][j]>largest)
{

【在 h**6 的大作中提到】

: 沿着对角线遍历一次，复杂度仍然是O(N^2)。因为每条对角线都只需要寻找比以前更大
: 的边长，也就是更大的B1、B2值。虽然遍历单条对角线复杂度是O(N^2)，但对角线的值
: 都是相关的，因此遍历全部对角线的复杂度也是O(N^2)。
: 通过运行时间也能看出来，同样是10000*10000的矩阵：
: 剪枝之前，O(n^2logn)算法耗时96.406秒，O(n^3)算法耗时1263.265秒。
: 剪枝之后，两个算法运行时间分别为10.156秒和9.375秒。此时复杂度相同，前一个算法因较复杂开销更大故更慢。

h*62011-12-09 08:12

50 楼

我的代码是这样的：
int DiagonalOverlap(int* B1, int* B2, int n, int lastresult)
{
int result = lastresult;
for(int i=0; i lastresult)
for(int j=0; j<=i; j++) if(B2[j] > lastresult)
{
if(i-j+1 <= min(B1[i], B2[j]))
result = max(result, i-j+1);
}
return result;
}
其中，B1、B2是两条对角线，n是该对角线长度，lastresult是以前的最大值。
if(B1[i] > lastresult)和if(B2[j] > lastresult)两句话就是剪枝，不加也能得到正
确答案，加了之后能节省几十到上百倍的时间。
最终，DiagonalOverlap这个函数运行时间比生成B1B2矩阵的时间

h*62011-12-09 08:12

51 楼

剪枝的英文是prune/pruning，面试的时候就别说cut branch了。

s*g2011-12-09 08:12

52 楼

6 5 0 1 0 1是如何得到的？谁能解释一下？
——————————————————————————————————————
han6 提到：
借用paul198247的例子2 5 0 1 0 1和1 2 0 3 0 6来说明一下吧。
2 5 0 1 0 1分别表示长度为这些数字，起始位置为1~6的区间
1 2 0 3 0 6分别表示长度为这些数字，结束位置为1~6的区间，
其起始位置可以算出，是1 1 0 2 0 1
把这些区间全部合并，相同起始位置只保留最长的区间，得到6 5 0 1 0 1
求每个区间与前面所有区间的重叠，只需要把前面所有区间的最后
结束位置减去该区间起始位置即可。而这个所有区间的最后结束位
置是递不减的，每加上一个新区间，最多需要更新一次。
也分析下hock的例子：
B2的主对角线2 0 0 1，B1的主对角线1 0 0 4，合并为4 0 0 1，重叠部分长度为1。