马伊琍非常难过ZT - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

马伊琍非常难过ZT

马伊琍非常难过ZT# Joke - 肚皮舞运动

s*32014-03-30 07:03

1 楼

Given a matrix, each cell having only 0's or 1's, find the largest sub-
matrix with equal number of 0's and 1's in it.
求指导！

c*o2014-03-30 07:03

2 楼

不建议交易打印胖子；胖子是免费的，收费的是服务:
出售/交换物品的名称:
coach retail store $100 off toward $300 card。在coach retail store可以使
用，不能用在outlet。过期日期是06/20/11.
物品类别（coupon：mfc等；血糖仪等）:
mfc
物品来源（报纸夹页，厂家邮寄等）:
厂家邮寄
可接受的价格（必须明码标价，必填）:
交换RA 3off15 胖子5-8张 and/or
enfamil or similac一段奶票或胖子
我想要的胖子有:
quite flexible, we can discuss over the mail
邮寄损失方式哪方承担（若需邮寄，必填）:
互担
付款方式说明:
本贴有效期（必填）:
till gone
联系方式（例：站内）:
站内信箱

G*d2014-03-30 07:03

3 楼

g*12014-03-30 07:03

4 楼

马伊琍非常难过，去拜访一位禅师，到达寺庙时天色已晚，马伊琍只得和同行的人一起
在庙里住下，晚上有蚊子她很晚才睡着。第二天早上马伊琍恍然大悟：“禅师，您故意
让我被蚊子咬以肉体的痛苦减轻心灵的痛苦吗？”禅师摇摇头说
“不，我是想告诉你，没有蚊帐你一样能睡得着觉。

f*u2014-03-30 07:03

5 楼

这题目测应该用dp吧。回头写个代码看看。

【在 s*******3 的大作中提到】

: Given a matrix, each cell having only 0's or 1's, find the largest sub-
: matrix with equal number of 0's and 1's in it.
: 求指导！

w*12014-03-30 07:03

6 楼

突然想起来我也有两张这个。

f*r2014-03-30 07:03

7 楼

LOL

【在 g**1 的大作中提到】

: 马伊琍非常难过，去拜访一位禅师，到达寺庙时天色已晚，马伊琍只得和同行的人一起
: 在庙里住下，晚上有蚊子她很晚才睡着。第二天早上马伊琍恍然大悟：“禅师，您故意
: 让我被蚊子咬以肉体的痛苦减轻心灵的痛苦吗？”禅师摇摇头说
: “不，我是想告诉你，没有蚊帐你一样能睡得着觉。

C*e2014-03-30 07:03

8 楼

暂时想到用dp，时间复杂度O((mn)^2)
求更好的算法。。

【在 s*******3 的大作中提到】

: Given a matrix, each cell having only 0's or 1's, find the largest sub-
: matrix with equal number of 0's and 1's in it.
: 求指导！

c*r2014-03-30 07:03

9 楼

lol

k*a2014-03-30 07:03

10 楼

每个元素是一个0或一个1，还是多个？？？

z*t2014-03-30 07:03

11 楼

能到O(n*n*m)
跟二维矩阵地最大字段和类似, 先把问题简化到一维数组(x到y行拍扁成一行，也就是
a[col] = sum(m[i][col] for i in range(x,y)) )。a再做个前缀和 a[i] = sum(a[0:
i])
h = y-x+1 矩形的高度。
问题转化为 a[i] - a[j-1] = h*(i-j)/2 ==> a[i] = a[j+1] + h*(i-j)/2
随j递
增递减可用类似杨氏矩阵的搜索办法。

D*r2014-03-30 07:03

12 楼

建一个同size的matrix，先把原matrix里的第一排和第一列copy到新matrix里。
然后其它各点，如果原matrix里是1，到新matrix里，就是1 + min(上方，左方，左斜
上方在新matrix里的值）；如果原matrix里是0，就copy 0到新matrix里。
最后新matrix里最大的那个数，就是所要找的sub-matrix的右下角，这个数，就是
submatrix的size。
复杂度是n*n.

【在 s*******3 的大作中提到】

: Given a matrix, each cell having only 0's or 1's, find the largest sub-
: matrix with equal number of 0's and 1's in it.
: 求指导！

x*k2014-03-30 07:03

13 楼

1 1
1 1
这个按你的算法对应的新矩阵是
1 1
1 2
吧？不知道理解的对不对。

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

: 建一个同size的matrix，先把原matrix里的第一排和第一列copy到新matrix里。
: 然后其它各点，如果原matrix里是1，到新matrix里，就是1 + min(上方，左方，左斜
: 上方在新matrix里的值）；如果原matrix里是0，就copy 0到新matrix里。
: 最后新matrix里最大的那个数，就是所要找的sub-matrix的右下角，这个数，就是
: submatrix的size。
: 复杂度是n*n.

r*72014-03-30 07:03

14 楼

http://www.geeksforgeeks.org/largest-subarray-with-equal-number

【在 s*******3 的大作中提到】

: Given a matrix, each cell having only 0's or 1's, find the largest sub-
: matrix with equal number of 0's and 1's in it.
: 求指导！

D*r2014-03-30 07:03

15 楼

哦，把题目看偏了，以为是要找最大的全是1的sub-matrix，原来是要找最大的0和1数
目相等的sub-matrix。

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

: 1 1
: 1 1
: 这个按你的算法对应的新矩阵是
: 1 1
: 1 2
: 吧？不知道理解的对不对。

s*32014-03-30 07:03

16 楼

求问 “问题转化为 a[i] - a[j-1] = h*(i-j)/2 ==> a[i] = a[j+1] + h*(i-j)/2
随j递增递减，可用类似杨氏矩阵的搜索办法。”
转化为一维问题之后如何在O(M)时间内求出最大值。

是
0:

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

: 能到O(n*n*m)
: 跟二维矩阵地最大字段和类似, 先把问题简化到一维数组(x到y行拍扁成一行，也就是
: a[col] = sum(m[i][col] for i in range(x,y)) )。a再做个前缀和 a[i] = sum(a[0:
: i])
: h = y-x+1 矩形的高度。
: 问题转化为 a[i] - a[j-1] = h*(i-j)/2 ==> a[i] = a[j+1] + h*(i-j)/2
: 随j递
: 增递减可用类似杨氏矩阵的搜索办法。

p*p2014-03-30 07:03

17 楼

我写的java code O(m*m*n) 实现：
本质上跟max sub-matrix sum 差不多，就是把二维问题转化为一维。
public int getSubMatrixWithEqual0And1(int[][] matrix) {
int m, n;
if(matrix == null || (m = matrix.length) == 0 || (n = matrix[0].
length) == 0) {
return 0;
}

int overallMax = 0;
for(int i = 0; i < m; i++) {
int[] rowSum = new int[n];
for(int j = i; j < m; j++) {
for(int k = 0; k < n; k++) {
rowSum[k] += matrix[j][k] == 0 ? -1 : 1;
}

int maxSofar = (j-i+1) * getMaxLenWithEqual0And1(rowSum);
if(maxSofar > overallMax) {
overallMax = maxSofar;
}
}
}
return overallMax;
}

private int getMaxLenWithEqual0And1(int[] arr) {
int n = arr.length;
int[] leftSum = new int[n];
Map map = new HashMap();
int max = 0;
for(int i = 0; i < n; i++) {
leftSum[i] = i == 0 ? arr[i] : leftSum[i-1]+arr[i];
if(leftSum[i] == 0) {
max = i+1;
}
if(map.containsKey(leftSum[i])) {
int len = i - map.get(leftSum[i]);
if(len > max) {
max = len;
}
} else {
map.put(leftSum[i], i);
}
}
return max;
}

C*e2014-03-30 07:03

18 楼

为什么要leftSum[i] == leftSum[j] ?
这意味着i ~ j 之间都是0，并不是要找的subarray啊

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

: 我写的java code O(m*m*n) 实现：
: 本质上跟max sub-matrix sum 差不多，就是把二维问题转化为一维。
: public int getSubMatrixWithEqual0And1(int[][] matrix) {
: int m, n;
: if(matrix == null || (m = matrix.length) == 0 || (n = matrix[0].
: length) == 0) {
: return 0;
: }
:
: int overallMax = 0;

T*u2014-03-30 07:03

19 楼

这样的一个社区的必要非充分条件是boundary全部是1或者0，并且boundary不属于除了
这个社区的其他社区。并且这样的社区不是唯一的。照这个思路，先找boundary,然后
一个一个的submap排除试试？

p*p2014-03-30 07:03

20 楼

Not sure how you got that from the code.
But the code is there, you probably should try to run it with your example.

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

: 为什么要leftSum[i] == leftSum[j] ?
: 这意味着i ~ j 之间都是0，并不是要找的subarray啊

C*e2014-03-30 07:03

21 楼

你的是对的，我看错了
另外，如果直接进行把你的函数getMaxLenWithEqual0And1()转换到二维，可以O(m * n
)实现，
空间复杂度升到O(m*n)

.

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

: Not sure how you got that from the code.
: But the code is there, you probably should try to run it with your example.