c*z
2 楼
Q1. Describe one of your projects.
Q2. Why the copy constructor pass by reference not by value?
I said I know the general difference between passing by reference (globe
copy) and value (local copy), but I don't know if it applies here.
He told me that if I pass by value and the value is an object of another
class, then there will be an infinite loop.
(I bombed this one I think.)
Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
I started with the naive approach (go along
Q2. Why the copy constructor pass by reference not by value?
I said I know the general difference between passing by reference (globe
copy) and value (local copy), but I don't know if it applies here.
He told me that if I pass by value and the value is an object of another
class, then there will be an infinite loop.
(I bombed this one I think.)
Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
I started with the naive approach (go along
g*s
3 楼
冬去春来，又到了用人之际，线上线下各类招聘活动如火如荼。现在，网络平台已成为
求职应聘的重要途径，但其在带来便利的同时，也使得许多不法分子悄悄混入其中。为
了更好地让大家了解招工诈骗的不同“变种”，我们盘点了一些关于此类犯罪的案例。
接下来，我们就看看最近都有哪些直击灵魂深处的诈骗套路吧！
1、“媒体网络”招聘诈骗
犯罪分子通过邮箱、网站发布虚假招聘信息，诱骗务工者前来应聘，以购买复杂资料、
考试提纲等方式诈骗钱财。由于网络信息量大、范围广，提供了很大的求职空间，成为
越来越多人优先考虑的求职途径。一些网络骗子也就乘虚而入，编织各种美丽的招聘陷
阱，诱骗求职者把钱存入指定的账户以达到诈骗目的。
2、“皮包公司”合伙行骗
一些劳务中介所为了获取应聘者的信任，与一些骗子公司或皮包公司合伙进行诈骗。即
先由中介单位以推荐工作为名收取报名费等，后由骗子公司或皮包公司假装招聘工人，
收取体检费、服装费、押金等费用，再编织种种理由拒绝上岗或中途辞退。
3、收取服务费后借口敷衍
一些中介部门在醒目地点张贴相当诱人的招聘启示吸引应聘人员上门，在收取一定的服
务费后称宣传的职位已满，并承诺尽快联系合适的单位，让应聘者留下联系方式，但其
根本没法兑现，然后寻找各种借口敷衍。一般应聘者求职心切，只能采取一档多投的方
法以尽快上岗，只要能找到工作，且被骗钱财金额不大，也就自认倒霉了。
4、吹嘘有关系要钱疏通
诈骗分子吹嘘自己门路广、关系多，可以通过“关系”帮事主找到“好”工作，但为了
疏通关系需要花钱，但是当事主交钱后，骗子要么逃之夭夭不见踪迹，要么好工作遥遥
无期。
5、群发招工信息骗取费用
“某酒店因业务发展需要，诚招业务员，年龄18~40岁，月薪8000元；某服装公司招聘
女工，月工资3500元……”骗子一般以优厚的工作待遇为诱饵，抓住求职者急于找工作
的心理，通过手机群发招工信息的形式，等待受骗者上钩。如果求职者打电话过去咨询
，往往被要求交报名费、押金等。这些人在骗取钱财时，根据报名者的急切程度来决定
报名费和押金的数额，200元、500元、1000元、2000元不等，得手后便把手机号和银行
账号一同注销。
警方提醒：当前正值招工旺季，一些不法分子利用种种手段设置圈套，引诱应聘者上当
，在网上找工作时，要小心以服装费、伙食费、押金、报名费等为名收取先期费用；劳
务中介信息真假难辨，未经证实前切勿随意泄露个人信息，上网找工作时要慎重，应详
细了解招工单位的资料，要通过正规平台进行求职。
求职应聘的重要途径，但其在带来便利的同时，也使得许多不法分子悄悄混入其中。为
了更好地让大家了解招工诈骗的不同“变种”，我们盘点了一些关于此类犯罪的案例。
接下来，我们就看看最近都有哪些直击灵魂深处的诈骗套路吧！
1、“媒体网络”招聘诈骗
犯罪分子通过邮箱、网站发布虚假招聘信息，诱骗务工者前来应聘，以购买复杂资料、
考试提纲等方式诈骗钱财。由于网络信息量大、范围广，提供了很大的求职空间，成为
越来越多人优先考虑的求职途径。一些网络骗子也就乘虚而入，编织各种美丽的招聘陷
阱，诱骗求职者把钱存入指定的账户以达到诈骗目的。
2、“皮包公司”合伙行骗
一些劳务中介所为了获取应聘者的信任，与一些骗子公司或皮包公司合伙进行诈骗。即
先由中介单位以推荐工作为名收取报名费等，后由骗子公司或皮包公司假装招聘工人，
收取体检费、服装费、押金等费用，再编织种种理由拒绝上岗或中途辞退。
3、收取服务费后借口敷衍
一些中介部门在醒目地点张贴相当诱人的招聘启示吸引应聘人员上门，在收取一定的服
务费后称宣传的职位已满，并承诺尽快联系合适的单位，让应聘者留下联系方式，但其
根本没法兑现，然后寻找各种借口敷衍。一般应聘者求职心切，只能采取一档多投的方
法以尽快上岗，只要能找到工作，且被骗钱财金额不大，也就自认倒霉了。
4、吹嘘有关系要钱疏通
诈骗分子吹嘘自己门路广、关系多，可以通过“关系”帮事主找到“好”工作，但为了
疏通关系需要花钱，但是当事主交钱后，骗子要么逃之夭夭不见踪迹，要么好工作遥遥
无期。
5、群发招工信息骗取费用
“某酒店因业务发展需要，诚招业务员，年龄18~40岁，月薪8000元；某服装公司招聘
女工，月工资3500元……”骗子一般以优厚的工作待遇为诱饵，抓住求职者急于找工作
的心理，通过手机群发招工信息的形式，等待受骗者上钩。如果求职者打电话过去咨询
，往往被要求交报名费、押金等。这些人在骗取钱财时，根据报名者的急切程度来决定
报名费和押金的数额，200元、500元、1000元、2000元不等，得手后便把手机号和银行
账号一同注销。
警方提醒：当前正值招工旺季，一些不法分子利用种种手段设置圈套，引诱应聘者上当
，在网上找工作时，要小心以服装费、伙食费、押金、报名费等为名收取先期费用；劳
务中介信息真假难辨，未经证实前切勿随意泄露个人信息，上网找工作时要慎重，应详
细了解招工单位的资料，要通过正规平台进行求职。
t*4
4 楼
唉，不说了，那么牛的片子硬是听不懂。
还是“功夫”片简单
还是“功夫”片简单
A*y
5 楼
If they want something from you, they will come find you. Unless you have
nothing to offer.
nothing to offer.
s*t
6 楼
第二个完全不懂。。
and
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
and
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
m*i
7 楼
还真有这样的，感谢提醒！
P*s
8 楼
可能还有文化背景的问题吧 就是比如说一个笑话，那笑话得有个context才好笑
【在 t****4 的大作中提到】
: 唉，不说了，那么牛的片子硬是听不懂。
: 还是“功夫”片简单
【在 t****4 的大作中提到】
: 唉，不说了，那么牛的片子硬是听不懂。
: 还是“功夫”片简单
p*l
9 楼
我怎么觉得自己去找别人写更舒服点。找上门的合作，有时候觉得不是特别适合，但是
又不好意思推掉，很难办。
又不好意思推掉，很难办。
p*y
10 楼
thank you for sharing
what kind of position you are applying? SDE?
what kind of position you are applying? SDE?
a*9
11 楼
为啥一定要有人找你? 别总想着靠别人, 有人一开始就有大树靠, 那是运气(无法控制
的), 更多的时候要靠自己. 我属于一直没有大数靠的, 过的也挺好.
【在 d***n 的大作中提到】
: AP 第二年。都是我找别人写proposal. 求爷爷告奶奶的。 怎么没有人找我呢？ 郁闷
: 。
的), 更多的时候要靠自己. 我属于一直没有大数靠的, 过的也挺好.
【在 d***n 的大作中提到】
: AP 第二年。都是我找别人写proposal. 求爷爷告奶奶的。 怎么没有人找我呢？ 郁闷
: 。
c*z
12 楼
SDE.
For objects, I always pass by reference without knowing or thinking why...
For objects, I always pass by reference without knowing or thinking why...
a*y
13 楼
be careful of what you wish for
有时候找你合作，不一定是好事，可能是毒草，参加我前一阵子的帖子
有时候找你合作，不一定是好事，可能是毒草，参加我前一阵子的帖子
m*u
14 楼
第二题的意思是pass by value会调用 copy constructor吧
submatrix?
and
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
submatrix?
and
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
c*d
15 楼
第三题有没有什么好的解法？
and
it
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
and
it
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
H*M
16 楼
这两ID不错，connectedGraph hehe
【在 c*******d 的大作中提到】
: 第三题有没有什么好的解法？
:
: and
: it
【在 c*******d 的大作中提到】
: 第三题有没有什么好的解法？
:
: and
: it
c*f
17 楼
哇 又一轮轰炸开始了
c*d
18 楼
多谢
【在 H*M 的大作中提到】
: 这两ID不错，connectedGraph hehe
【在 H*M 的大作中提到】
: 这两ID不错，connectedGraph hehe
r*u
19 楼
构造一个nxn matrix B，对每一行，B［i,j]是从左面起到这个元素连续0元素的个数。
e.g.,
1 0 0 0 1 --> 0 1 2 3 0
1 1 0 0 1 --> 0 0 1 2 0
0 0 0 0 1 --> 1 2 3 4 0
...
然后对每一列用最大柱状图的算法。
【在 c*******d 的大作中提到】
: 第三题有没有什么好的解法？
:
: and
: it
e.g.,
1 0 0 0 1 --> 0 1 2 3 0
1 1 0 0 1 --> 0 0 1 2 0
0 0 0 0 1 --> 1 2 3 4 0
...
然后对每一列用最大柱状图的算法。
【在 c*******d 的大作中提到】
: 第三题有没有什么好的解法？
:
: and
: it
c*f
20 楼
哇 又一轮轰炸开始了
c*d
21 楼
多谢提示，不过我还是不太明白
什么是最大柱状图的算法？
【在 r**u 的大作中提到】
: 构造一个nxn matrix B，对每一行，B［i,j]是从左面起到这个元素连续0元素的个数。
: e.g.,
: 1 0 0 0 1 --> 0 1 2 3 0
: 1 1 0 0 1 --> 0 0 1 2 0
: 0 0 0 0 1 --> 1 2 3 4 0
: ...
: 然后对每一列用最大柱状图的算法。
什么是最大柱状图的算法？
【在 r**u 的大作中提到】
: 构造一个nxn matrix B，对每一行，B［i,j]是从左面起到这个元素连续0元素的个数。
: e.g.,
: 1 0 0 0 1 --> 0 1 2 3 0
: 1 1 0 0 1 --> 0 0 1 2 0
: 0 0 0 0 1 --> 1 2 3 4 0
: ...
: 然后对每一列用最大柱状图的算法。
l*o
22 楼
同求解释。简单的动态规划可以做到O(MN*min(M,N))的复杂度，希望能有一个O(MN)的
算法。
多谢提示，不过我还是不太明白
什么是最大柱状图的算法？
【在 c*******d 的大作中提到】
: 多谢提示，不过我还是不太明白
: 什么是最大柱状图的算法？
算法。
多谢提示，不过我还是不太明白
什么是最大柱状图的算法？
【在 c*******d 的大作中提到】
: 多谢提示，不过我还是不太明白
: 什么是最大柱状图的算法？
c*d
23 楼
动态规划怎么做？
【在 l******o 的大作中提到】
: 同求解释。简单的动态规划可以做到O(MN*min(M,N))的复杂度，希望能有一个O(MN)的
: 算法。
:
: 多谢提示，不过我还是不太明白
: 什么是最大柱状图的算法？
【在 l******o 的大作中提到】
: 同求解释。简单的动态规划可以做到O(MN*min(M,N))的复杂度，希望能有一个O(MN)的
: 算法。
:
: 多谢提示，不过我还是不太明白
: 什么是最大柱状图的算法？
b*n
24 楼
linear scan应该可以把，
用O(m*n) extra space,
每个点记录原matrix中以该点为右下角的sub matrix的大小，
然后scan，(x, y)只用check (x-1, y-1), (x-1, y), (x,y-1)
复杂度O(NM)
用O(m*n) extra space,
每个点记录原matrix中以该点为右下角的sub matrix的大小，
然后scan，(x, y)只用check (x-1, y-1), (x-1, y), (x,y-1)
复杂度O(NM)
S*n
25 楼
简单的DP就可以做到O(MN), 这个是square
柱状图是用于求rectangle的情形
【在 l******o 的大作中提到】
: 同求解释。简单的动态规划可以做到O(MN*min(M,N))的复杂度，希望能有一个O(MN)的
: 算法。
:
: 多谢提示，不过我还是不太明白
: 什么是最大柱状图的算法？
柱状图是用于求rectangle的情形
【在 l******o 的大作中提到】
: 同求解释。简单的动态规划可以做到O(MN*min(M,N))的复杂度，希望能有一个O(MN)的
: 算法。
:
: 多谢提示，不过我还是不太明白
: 什么是最大柱状图的算法？
l*o
26 楼
这个具体怎么做？右下角为(x,y)的最大sub matrix同(x-1, y-1), (x-1, y), (x,y-1)
有可能完全没有关系。比如
1111101
1111101
1111101
1111101
1111000
0000000
1111000
右下角那个是3x3，(x-1, y), (x,y-1)都是1x7或7x1的那个, (x-1, y-1)是1x6或6x1那
个. 所以不能直接通过(x-1, y-1), (x-1, y), (x,y-1)的结果得到(x,y)的结果.
linear scan应该可以把，
用O(m*n) extra space,
每个点记录原matrix中以该点为右下角的sub matrix的大小，
然后scan，(x, y)只用check (x-1, y-1), (x-1, y), (x,y-1)
【在 b******n 的大作中提到】
: linear scan应该可以把，
: 用O(m*n) extra space,
: 每个点记录原matrix中以该点为右下角的sub matrix的大小，
: 然后scan，(x, y)只用check (x-1, y-1), (x-1, y), (x,y-1)
: 复杂度O(NM)
有可能完全没有关系。比如
1111101
1111101
1111101
1111101
1111000
0000000
1111000
右下角那个是3x3，(x-1, y), (x,y-1)都是1x7或7x1的那个, (x-1, y-1)是1x6或6x1那
个. 所以不能直接通过(x-1, y-1), (x-1, y), (x,y-1)的结果得到(x,y)的结果.
linear scan应该可以把，
用O(m*n) extra space,
每个点记录原matrix中以该点为右下角的sub matrix的大小，
然后scan，(x, y)只用check (x-1, y-1), (x-1, y), (x,y-1)
【在 b******n 的大作中提到】
: linear scan应该可以把，
: 用O(m*n) extra space,
: 每个点记录原matrix中以该点为右下角的sub matrix的大小，
: 然后scan，(x, y)只用check (x-1, y-1), (x-1, y), (x,y-1)
: 复杂度O(NM)
b*n
27 楼
(x,y)存的是以自身为右下角的square submatrix的size，
你的例子里面(x-1, y), (x,y-1)，(x-1, y-1)都是2
就是DP
1)
【在 l******o 的大作中提到】
: 这个具体怎么做？右下角为(x,y)的最大sub matrix同(x-1, y-1), (x-1, y), (x,y-1)
: 有可能完全没有关系。比如
: 1111101
: 1111101
: 1111101
: 1111101
: 1111000
: 0000000
: 1111000
: 右下角那个是3x3，(x-1, y), (x,y-1)都是1x7或7x1的那个, (x-1, y-1)是1x6或6x1那
你的例子里面(x-1, y), (x,y-1)，(x-1, y-1)都是2
就是DP
1)
【在 l******o 的大作中提到】
: 这个具体怎么做？右下角为(x,y)的最大sub matrix同(x-1, y-1), (x-1, y), (x,y-1)
: 有可能完全没有关系。比如
: 1111101
: 1111101
: 1111101
: 1111101
: 1111000
: 0000000
: 1111000
: 右下角那个是3x3，(x-1, y), (x,y-1)都是1x7或7x1的那个, (x-1, y-1)是1x6或6x1那
l*o
28 楼
哦, 没看清题目, 原来要求的是方阵啊, 那就简单多了. 确实可以做到O(MN)
假如, 如果不要求是方阵, 不知道有没有O(MN)的算法?
(x,y)存的是以自身为右下角的square submatrix的size，
你的例子里面(x-1, y), (x,y-1)，(x-1, y-1)都是2
就是DP
1)
【在 b******n 的大作中提到】
: (x,y)存的是以自身为右下角的square submatrix的size，
: 你的例子里面(x-1, y), (x,y-1)，(x-1, y-1)都是2
: 就是DP
:
: 1)
假如, 如果不要求是方阵, 不知道有没有O(MN)的算法?
(x,y)存的是以自身为右下角的square submatrix的size，
你的例子里面(x-1, y), (x,y-1)，(x-1, y-1)都是2
就是DP
1)
【在 b******n 的大作中提到】
: (x,y)存的是以自身为右下角的square submatrix的size，
: 你的例子里面(x-1, y), (x,y-1)，(x-1, y-1)都是2
: 就是DP
:
: 1)
c*z
29 楼
What I finally arrive at before timed out was this:
if there is a 1 on a line or row, change that line or row to all 1;
for each blocks of 0s, min{height, width} is the dimension of the submatrix.
two passes on the matrix, O(MN).
if there is a 1 on a line or row, change that line or row to all 1;
for each blocks of 0s, min{height, width} is the dimension of the submatrix.
two passes on the matrix, O(MN).
c*d
30 楼
对，是方阵的我知道怎么做了，
如果是求面积最大子长方形，有没有O(MN)的算法？
【在 l******o 的大作中提到】
: 哦, 没看清题目, 原来要求的是方阵啊, 那就简单多了. 确实可以做到O(MN)
: 假如, 如果不要求是方阵, 不知道有没有O(MN)的算法?
:
: (x,y)存的是以自身为右下角的square submatrix的size，
: 你的例子里面(x-1, y), (x,y-1)，(x-1, y-1)都是2
: 就是DP
: 1)
如果是求面积最大子长方形，有没有O(MN)的算法？
【在 l******o 的大作中提到】
: 哦, 没看清题目, 原来要求的是方阵啊, 那就简单多了. 确实可以做到O(MN)
: 假如, 如果不要求是方阵, 不知道有没有O(MN)的算法?
:
: (x,y)存的是以自身为右下角的square submatrix的size，
: 你的例子里面(x-1, y), (x,y-1)，(x-1, y-1)都是2
: 就是DP
: 1)
h*x
31 楼
Q2这个问题不错，还真容易没有考虑到。
Q3有更好的办法吗？
and
it
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
Q3有更好的办法吗？
and
it
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
c*d
32 楼
0001
0001
0001
这样就全变成1了吧？
submatrix.
【在 c***z 的大作中提到】
: What I finally arrive at before timed out was this:
: if there is a 1 on a line or row, change that line or row to all 1;
: for each blocks of 0s, min{height, width} is the dimension of the submatrix.
: two passes on the matrix, O(MN).
0001
0001
这样就全变成1了吧？
submatrix.
【在 c***z 的大作中提到】
: What I finally arrive at before timed out was this:
: if there is a 1 on a line or row, change that line or row to all 1;
: for each blocks of 0s, min{height, width} is the dimension of the submatrix.
: two passes on the matrix, O(MN).
s*y
33 楼
steve ballmer. s****[email protected]
and
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
and
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
c*a
34 楼
竟然不全是算法，感觉比较nice啊
and
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
and
【在 c***z 的大作中提到】
: Q1. Describe one of your projects.
: Q2. Why the copy constructor pass by reference not by value?
: I said I know the general difference between passing by reference (globe
: copy) and value (local copy), but I don't know if it applies here.
: He told me that if I pass by value and the value is an object of another
: class, then there will be an infinite loop.
: (I bombed this one I think.)
: Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
: I started with the naive approach (go along
c*z
35 楼
You are right, I was wrong.
Need to study more DP...
【在 c*******d 的大作中提到】
: 0001
: 0001
: 0001
: 这样就全变成1了吧？
:
: submatrix.
Need to study more DP...
【在 c*******d 的大作中提到】
: 0001
: 0001
: 0001
: 这样就全变成1了吧？
:
: submatrix.
c*z
36 楼
I finally made it. Anyone care to check it up? :)
/**************************************************************
Maximum all-0 square submatrix problem -- Compiled under VC++ 2008.
Problem Description:
Given MxN binary matrix M, find the maximum all 0 square submatrix (
denoted by MASS) of it.
Example:
0000100
1100100
0000011 <= an answer is the 3x3 submatrix (row 2~4, col 0~2)
0000010
0000100
0010100
Algorithm Description:
The key idea is Dynamic Programm
/**************************************************************
Maximum all-0 square submatrix problem -- Compiled under VC++ 2008.
Problem Description:
Given MxN binary matrix M, find the maximum all 0 square submatrix (
denoted by MASS) of it.
Example:
0000100
1100100
0000011 <= an answer is the 3x3 submatrix (row 2~4, col 0~2)
0000010
0000100
0010100
Algorithm Description:
The key idea is Dynamic Programm
c*z
37 楼
co-ask, I am really curious...
thanks!
【在 c*******d 的大作中提到】
: 对，是方阵的我知道怎么做了，
: 如果是求面积最大子长方形，有没有O(MN)的算法？
thanks!
【在 c*******d 的大作中提到】
: 对，是方阵的我知道怎么做了，
: 如果是求面积最大子长方形，有没有O(MN)的算法？
c*z
38 楼
It seems that it is better to store total # of 1's.
My idea is first fix column i and column j, try to find the max all 0
rectangular between them.
For that purpose, we need one pass on the rows, keeping track of the longest
rectangular ending at row k (LREK). This is a variant of the max sum
subarray problem.
If row k has an 1, then LREK=0; otherwise add 1 to the previous LREK.
To fast calculate if row k has an 1 or not, it is better to store the total
# of 1's and just do a subtraction.
O(M^2N
【在 r**u 的大作中提到】
: 构造一个nxn matrix B，对每一行，B［i,j]是从左面起到这个元素连续0元素的个数。
: e.g.,
: 1 0 0 0 1 --> 0 1 2 3 0
: 1 1 0 0 1 --> 0 0 1 2 0
: 0 0 0 0 1 --> 1 2 3 4 0
: ...
: 然后对每一列用最大柱状图的算法。
My idea is first fix column i and column j, try to find the max all 0
rectangular between them.
For that purpose, we need one pass on the rows, keeping track of the longest
rectangular ending at row k (LREK). This is a variant of the max sum
subarray problem.
If row k has an 1, then LREK=0; otherwise add 1 to the previous LREK.
To fast calculate if row k has an 1 or not, it is better to store the total
# of 1's and just do a subtraction.
O(M^2N
【在 r**u 的大作中提到】
: 构造一个nxn matrix B，对每一行，B［i,j]是从左面起到这个元素连续0元素的个数。
: e.g.,
: 1 0 0 0 1 --> 0 1 2 3 0
: 1 1 0 0 1 --> 0 0 1 2 0
: 0 0 0 0 1 --> 1 2 3 4 0
: ...
: 然后对每一列用最大柱状图的算法。
c*z
39 楼
I worked out the rectangular algorithm. I feel that I like these problems,
but... I am too slow I think...
/**************************************************************
Maximum All-0 Submatrix Problem (not necessarily square submatrix)
-- compiled under VC++ 2008
Problem Description:
Given MxN binary matrix R, find the maximum all 0 submatrix (not
necessarily square submatrix, denoted by MAS) of it.
Example:
0000100
1100100
0000011 <= an answer is
but... I am too slow I think...
/**************************************************************
Maximum All-0 Submatrix Problem (not necessarily square submatrix)
-- compiled under VC++ 2008
Problem Description:
Given MxN binary matrix R, find the maximum all 0 submatrix (not
necessarily square submatrix, denoted by MAS) of it.
Example:
0000100
1100100
0000011 <= an answer is
相关阅读
说说two brothers昨晚看的中国实验电影张国荣，查无此人推荐Gattaca(Genre: Sci-fi/Drama)欧来给你们浅显地解释一下那个漩涡空洞的产生。推荐几部不错的电影永远的秀兰.邓波儿～～～～～ZTscifi的常见致命伤-刚看equilibrium我爱 Kill Bill无间道IIroad movies 小结闲扯两句《东京故事〉悬念片补充[ZT]再也没有比十面埋伏更好看的喜剧电影了。。。ZZ: 从细节看沈澄和杨锦荣的计中计(<<无间道3>>)The Bourne Supremacyzz《十面埋伏》通过审查--第一段要把人笑死张艺谋：我不会去好莱坞真正的SPOILER: eternal sunshine机器人第零定律(及电影I, Robot)