w***y
发帖数: 6251 | 1 很紧张啊......
集中准备也就是3月份的事情, 越复习越发现不会的多 55555555
希望4月份能有好运气啊^_^ |
t******e
发帖数: 98 | |
H**********y
发帖数: 7928 | 3 bless
【在 w***y 的大作中提到】
: 很紧张啊......
: 集中准备也就是3月份的事情, 越复习越发现不会的多 55555555
: 希望4月份能有好运气啊^_^
|
w***y
发帖数: 6251 | 4 多谢楼上了!
又看到一道不会做的题目//囧
"N*N 的正方形内有黑白两色，求四边都是黑色的最大的子正方形"
这个题怎么做? 版上有讨论么? 我好像没有看到过. 我只见过那种, 所有'1' 围成的最
大方形, 不知道这种只要求'四边'的怎么做呀 |
p*****2
发帖数: 21240 | |
p*****2
发帖数: 21240 | 6
面试的时候我可能这么说。
1. brute force
2. binary search
3. 把横边和竖边纪录下来，去match ＋ 剪枝
4. 要hint
【在 w***y 的大作中提到】
: 多谢楼上了!
: 又看到一道不会做的题目//囧
: "N*N 的正方形内有黑白两色，求四边都是黑色的最大的子正方形"
: 这个题怎么做? 版上有讨论么? 我好像没有看到过. 我只见过那种, 所有'1' 围成的最
: 大方形, 不知道这种只要求'四边'的怎么做呀
|
z****u
发帖数: 241 | 7 Be sure know how to talk in the interview.
Prepare technical questions;
Prepare behavior questions.
The most important, only say what they want to hear in the interview.
Listen how the experienced people answer interview questions.
我主持的 FREE 华人周三晚找工周会，就是为你这样的朋友们开的，Will answer any
of your interview questions. Come join the weekly meeting or listen the
meeting record.
Here is the website for Weekly meeting:
http://bbs.wenxuecity.com/career/428047.html
我就是想让你的面试能准备的更充分一些，听周会录音， 是很多朋友一致暂不绝口的
好方法．谁对此不满，随他去吧！ |
c*******o
发帖数: 21 | |
p*****2
发帖数: 21240 | 9
我觉得可以DP吧？
【在 c*******o 的大作中提到】
: 所有'1' 围成的最大方形,怎么做?
|
t******e
发帖数: 98 | 10 这是我当年考过的面试题，可以负责的告诉你这题面试中不会再考到了，不过拿来练
coding还是很好的，topcoder上面也考过类似的问题。解法如下：
Let the input matrix be x[n][n]. The idea is to calculate two auxiliary
matrices a[n][n], where a[i][j] records the length of the all 1 horizontal
edge to the right of a[i][j], and b[n][n], where b[i][j] records the length
of the all 1 vertical edge above a[i][j]. Then the size of the largest all 1
boundary sub-square whose left bottom corner is a[i][j] is t = max{0≤t≤
min(a[i][j], b[i][j])|a[i-t+1][j]≥t and b[i][j+t-1]≥t}.
Obviously, a[i][j] and b[i][j] can be calculated recursively:
a[i][j] = 0; if x[i][j] == 0
a[i][j] = 1 + a[i][j+1]; if x[i][j] == 1
b[i][j] = 0; if x[i][j] == 0
b[i][j] = 1 + b[i-1][j]; if x[i][j] == 1
This is the C++ implementation of the algorithm:
template
int maxAllOneSquare(int (&x)[m][n], pair& output)
{
int a[m][n], b[m][n];
int maxSquare = 0;
output.first = -1;
output.second = -1;
for(int row = 0; row < m; ++row){
for(int col = n - 1; col >= 0; --col){
if(col == n -1){
a[row][col] = x[row][col] == 1 ? 1 : 0;
}
else{
a[row][col] = 0;
if(x[row][col] == 1){
a[row][col] = 1 + a[row][col + 1];
}
}
}
}
for(int row = 0; row < m; ++row){
for(int col = 0; col < n; ++col){
if(row == 0){
b[row][col] = x[row][col] == 1 ? 1 : 0;
}
else{
b[row][col] = 0;
if(x[row][col] == 1){
b[row][col] = 1 + b[row - 1][col];
}
}
}
}
for(int row = 0; row < m; ++row){
for(int col = 0; col < n; ++col){
if(x[row][col] == 1){
int t = min(a[row][col], b[row][col]);
while(t > 0 &&
(a[row - t + 1][col] < t || b[row][col + t - 1] < t)){
t--;
}
if(maxSquare < t){
maxSquare = t;
output.first = row;
output.second = col;
}
//maxSquare = max(maxSquare, t);
}
}
}
return maxSquare;
} |
|
|
w**z
发帖数: 8232 | 11 好奇问一下，这题是你们自己想出来的吗？
还是哪里看来的？
length
1
【在 t******e 的大作中提到】
: 这是我当年考过的面试题，可以负责的告诉你这题面试中不会再考到了，不过拿来练
: coding还是很好的，topcoder上面也考过类似的问题。解法如下：
: Let the input matrix be x[n][n]. The idea is to calculate two auxiliary
: matrices a[n][n], where a[i][j] records the length of the all 1 horizontal
: edge to the right of a[i][j], and b[n][n], where b[i][j] records the length
: of the all 1 vertical edge above a[i][j]. Then the size of the largest all 1
: boundary sub-square whose left bottom corner is a[i][j] is t = max{0≤t≤
: min(a[i][j], b[i][j])|a[i-t+1][j]≥t and b[i][j+t-1]≥t}.
: Obviously, a[i][j] and b[i][j] can be calculated recursively:
: a[i][j] = 0; if x[i][j] == 0
|
t******e
发帖数: 98 | 12 抱歉没说清楚，我是被面试者，题目是面试我的人出的，应该是他原创的，呵呵。 |
w***y
发帖数: 6251 | 13 en 用DP
用右下角去算, 直接推: 从右下角(i,j)看过去, 最大square的边长c(i,j)
【在 p*****2 的大作中提到】
:
: 我觉得可以DP吧？
|
l*********8
发帖数: 4642 | 14 brute force: O(n^4) ?
DP : O(n^2) time, O(n^2) space ?
【在 w***y 的大作中提到】
: en 用DP
: 用右下角去算, 直接推: 从右下角(i,j)看过去, 最大square的边长c(i,j)
|
w***y
发帖数: 6251 | 15 DP是的
brute force, 我还真没想明白怎么做//汗
【在 l*********8 的大作中提到】
: brute force: O(n^4) ?
: DP : O(n^2) time, O(n^2) space ?
|
l*********8
发帖数: 4642 | 16 brute force: Time O(n^4), Space O(1)
for (int x=0; x < N-1; x++)
for (int y=0; y < N-1; y++)
for (int width=1; width < N-1-max(x,y) ; width++)
{
for (int i=0; i
{
check the value of a[x+i][y], a[x][y+i], a[x+width-1][y+i],
a[x+i, y+width-1];
}
}
【在 w***y 的大作中提到】
: DP是的
: brute force, 我还真没想明白怎么做//汗
|
l*********8
发帖数: 4642 | 17 为什么说“这题面试中不会再考到了”？ 因为题目太老了？
length
1
【在 t******e 的大作中提到】
: 这是我当年考过的面试题，可以负责的告诉你这题面试中不会再考到了，不过拿来练
: coding还是很好的，topcoder上面也考过类似的问题。解法如下：
: Let the input matrix be x[n][n]. The idea is to calculate two auxiliary
: matrices a[n][n], where a[i][j] records the length of the all 1 horizontal
: edge to the right of a[i][j], and b[n][n], where b[i][j] records the length
: of the all 1 vertical edge above a[i][j]. Then the size of the largest all 1
: boundary sub-square whose left bottom corner is a[i][j] is t = max{0≤t≤
: min(a[i][j], b[i][j])|a[i-t+1][j]≥t and b[i][j+t-1]≥t}.
: Obviously, a[i][j] and b[i][j] can be calculated recursively:
: a[i][j] = 0; if x[i][j] == 0
|
l*********8
发帖数: 4642 | 18 要修改t的值
t一直表示当前测试的正方形边长。 |
p*****2
发帖数: 21240 | 19
DP can be in-place.
【在 l*********8 的大作中提到】
: brute force: Time O(n^4), Space O(1)
: for (int x=0; x < N-1; x++)
: for (int y=0; y < N-1; y++)
: for (int width=1; width < N-1-max(x,y) ; width++)
: {
: for (int i=0; i: {
: check the value of a[x+i][y], a[x][y+i], a[x+width-1][y+i],
: a[x+i, y+width-1];
: }
|
t********6
发帖数: 348 | 20 明白了。。
谢谢
【在 l*********8 的大作中提到】
: 要修改t的值
: t一直表示当前测试的正方形边长。
|
|
|
l*********8
发帖数: 4642 | 21 Thank your for the hint.
Now I think I can maintain only two length-n arrays instead of two n*n
matrix for DP. But this still needs O(N) extra space. Do you have better
ideas?
【在 p*****2 的大作中提到】
:
: DP can be in-place.
|
p*****2
发帖数: 21240 | 22
我觉得直接改数组就行了吧？O(1) space.
【在 l*********8 的大作中提到】
: Thank your for the hint.
: Now I think I can maintain only two length-n arrays instead of two n*n
: matrix for DP. But this still needs O(N) extra space. Do you have better
: ideas?
|
p*****2
发帖数: 21240 | 23
我觉得直接改数组就行了吧？O(1) space.
【在 l*********8 的大作中提到】
: Thank your for the hint.
: Now I think I can maintain only two length-n arrays instead of two n*n
: matrix for DP. But this still needs O(N) extra space. Do you have better
: ideas?
|
p*****2
发帖数: 21240 | 24 11
11
变成
11
12
111
111
111
变成
111
122
123 |
l*********8
发帖数: 4642 | 25 throttle的程序使用了两个矩阵 a[][], b[][].
我能想到的是， 矩阵a的前一行用过之后，就没有用了。所以可以在上一行用完之后，
生成新的一行，使用同一个n-length array. 类似的，矩阵b的前一列用过之后，就
没有用了....
但O(1) space我真想不出， 请明示：）
【在 p*****2 的大作中提到】
: 11
: 11
: 变成
: 11
: 12
: 111
: 111
: 111
: 变成
: 111
|
p*****2
发帖数: 21240 | 26
上边给了例子了。直接存最大正方形的size。
【在 l*********8 的大作中提到】
: throttle的程序使用了两个矩阵 a[][], b[][].
: 我能想到的是， 矩阵a的前一行用过之后，就没有用了。所以可以在上一行用完之后，
: 生成新的一行，使用同一个n-length array. 类似的，矩阵b的前一列用过之后，就
: 没有用了....
: 但O(1) space我真想不出， 请明示：）
|
l*********8
发帖数: 4642 | 27 你的意思是： 原来矩阵里面只存了0和1，但如果矩阵元素是char或者更大的话， 就可
以直接在原来矩阵上存与当前元素为右下角的最大正方形的size？ 计算完毕之后，可
以恢复恢复原来数据。 但如果是bool矩阵就没法这样做了。
另外，你给的例子是求最大实心黑色方块的吧？ 本题里的黑色正方形，只需要边上为
黑色就行了，不需要实心。
【在 p*****2 的大作中提到】
:
: 上边给了例子了。直接存最大正方形的size。
|
p*****2
发帖数: 21240 | 28 对我说的另一题
★ Sent from iPhone App: iReader Mitbbs Lite 7.52 |
m*********0
发帖数: 1139 | |
f**********r
发帖数: 110 | 30 bless!
【在 w***y 的大作中提到】
: 很紧张啊......
: 集中准备也就是3月份的事情, 越复习越发现不会的多 55555555
: 希望4月份能有好运气啊^_^
|
|
|
w****o
发帖数: 2260 | 31 woomy,
我又两个问题：
1. 在你的问题
"N*N 的正方形内有黑白两色，求四边都是黑色的最大的子正方形"
是不是要求仅仅四边都是'1'的，中间可以是'0'的方形？还有长方形行吗？还是必须是
正方形？
2. 另外你提到的“我只见过那种, 所有'1' 围成的最大方形”
是不是要求正方形的所有点都是'1'? 长方形行吗？
【在 w***y 的大作中提到】
: 多谢楼上了!
: 又看到一道不会做的题目//囧
: "N*N 的正方形内有黑白两色，求四边都是黑色的最大的子正方形"
: 这个题怎么做? 版上有讨论么? 我好像没有看到过. 我只见过那种, 所有'1' 围成的最
: 大方形, 不知道这种只要求'四边'的怎么做呀
|
E**6
发帖数: 219 | 32 bless
【在 w***y 的大作中提到】
: 很紧张啊......
: 集中准备也就是3月份的事情, 越复习越发现不会的多 55555555
: 希望4月份能有好运气啊^_^
|
l*********8
发帖数: 4642 | 33 我越俎代庖回一下：
1. 四边都是'1'的，中间可以是'0'的方形
2. 正方形的所有点都是'1'
一般都是求正方形。
【在 w****o 的大作中提到】
: woomy,
: 我又两个问题：
: 1. 在你的问题
: "N*N 的正方形内有黑白两色，求四边都是黑色的最大的子正方形"
: 是不是要求仅仅四边都是'1'的，中间可以是'0'的方形？还有长方形行吗？还是必须是
: 正方形？
: 2. 另外你提到的“我只见过那种, 所有'1' 围成的最大方形”
: 是不是要求正方形的所有点都是'1'? 长方形行吗？
|
w****o
发帖数: 2260 | 34 thank you so much.
【在 l*********8 的大作中提到】
: 我越俎代庖回一下：
: 1. 四边都是'1'的，中间可以是'0'的方形
: 2. 正方形的所有点都是'1'
: 一般都是求正方形。
|
p*****2
发帖数: 21240 | 35
今天看到careercup上是求长方形。
【在 l*********8 的大作中提到】
: 我越俎代庖回一下：
: 1. 四边都是'1'的，中间可以是'0'的方形
: 2. 正方形的所有点都是'1'
: 一般都是求正方形。
|
l*********8
发帖数: 4642 | 36 是吗？ 长方形的话，DP的中间存起来就更麻烦一些。
【在 p*****2 的大作中提到】
:
: 今天看到careercup上是求长方形。
|
p*****2
发帖数: 21240 | 37
是。复杂度也更高。
【在 l*********8 的大作中提到】
: 是吗？ 长方形的话，DP的中间存起来就更麻烦一些。
|
w****o
发帖数: 2260 | 38 如果是要求长方形的话，如何定义最大？
对于只是边上的点为1的，是要求边长最大的长方形？
对于所有点都要是1的，是要求面积最大的长方形？
【在 p*****2 的大作中提到】
:
: 是。复杂度也更高。
|
h******0
发帖数: 427 | |
d****s
发帖数: 141 | |
|
|
f**********2
发帖数: 2401 | |
