l***t
发帖数: 81 | 1 1. Create a function findZeroArraySize() that takes a 2-dimensions int array
, its width and its height as arguments. The array is filled with 0 and 1. T
he function returns the size (in int) of the biggest 2-dimensions sub-array
filled only with 0. This function should be as fast as possible.
Ex:
If argument is , function returns 9.
001011110
110001100
010000011
110001100
111011100
Thanks a lot. |
c********y
发帖数: 13 | 2 return 3吧？
【在 l***t 的大作中提到】
: 1. Create a function findZeroArraySize() that takes a 2-dimensions int array
: , its width and its height as arguments. The array is filled with 0 and 1. T
: he function returns the size (in int) of the biggest 2-dimensions sub-array
: filled only with 0. This function should be as fast as possible.
: Ex:
: If argument is , function returns 9.
: 001011110
: 110001100
: 010000011
: 110001100
|
z*****n
发帖数: 7639 | 3 I guess so.
【在 c********y 的大作中提到】
: return 3吧？
|
l***t
发帖数: 81 | 4 No, it is 9.
the largest 0 sub matrix has 9 zeros :
000
000
000
【在 z*****n 的大作中提到】
: I guess so.
|
z*****n
发帖数: 7639 | 5 hehe, got it.
【在 l***t 的大作中提到】
: No, it is 9.
: the largest 0 sub matrix has 9 zeros :
: 000
: 000
: 000
|
s******e
发帖数: 92 | 6 I think I have an algorithm in mind. Suppose the size of the original matrix
is a * b. The complexity of my algorithm is O(ab). Not very fast ...
【在 l***t 的大作中提到】
: 1. Create a function findZeroArraySize() that takes a 2-dimensions int array
: , its width and its height as arguments. The array is filled with 0 and 1. T
: he function returns the size (in int) of the biggest 2-dimensions sub-array
: filled only with 0. This function should be as fast as possible.
: Ex:
: If argument is , function returns 9.
: 001011110
: 110001100
: 010000011
: 110001100
|
a******t
发帖数: 100 | 7
There are a*b elements in the matrix. You have to access each at least once.
If your algorithm is O(ab), it is pretty fast, I think.
【在 s******e 的大作中提到】
: I think I have an algorithm in mind. Suppose the size of the original matrix
: is a * b. The complexity of my algorithm is O(ab). Not very fast ...
|
g******a
发帖数: 730 | 8 当年我们的算法作业题啊
【在 s******e 的大作中提到】
: I think I have an algorithm in mind. Suppose the size of the original matrix
: is a * b. The complexity of my algorithm is O(ab). Not very fast ...
|
m****h
发帖数: 261 | 9 I think it can be solved by scanning the matrix column by column while
maintaning a measure, say, T(i), which is the maximum all 0 sub matirx before
scanning to column i, and then update T(i). The complexity should be
O(ab).
array
T
sub-array
【在 s******e 的大作中提到】
: I think I have an algorithm in mind. Suppose the size of the original matrix
: is a * b. The complexity of my algorithm is O(ab). Not very fast ...
|
a******t
发帖数: 100 | 10
How can you gaurantee the solution in T(i) is the largest?
1111001111
1110000111
1100000011
1000000001
0000000000
1000000001
.......
【在 m****h 的大作中提到】
: I think it can be solved by scanning the matrix column by column while
: maintaning a measure, say, T(i), which is the maximum all 0 sub matirx before
: scanning to column i, and then update T(i). The complexity should be
: O(ab).
:
: array
: T
: sub-array
|
|
|
s*****v
发帖数: 360 | |
a******t
发帖数: 100 | 12 Where did you find these problems? homework?
These problems are listed at
http://trikuare.cx/mt/archives/000718.php
【在 l***t 的大作中提到】
: 1. Create a function findZeroArraySize() that takes a 2-dimensions int array
: , its width and its height as arguments. The array is filled with 0 and 1. T
: he function returns the size (in int) of the biggest 2-dimensions sub-array
: filled only with 0. This function should be as fast as possible.
: Ex:
: If argument is , function returns 9.
: 001011110
: 110001100
: 010000011
: 110001100
|
m****h
发帖数: 261 | 13 It's like induction. It is simple when scanning the first column. Then, in the
folowing steps, we need only check the new column, to see if T(i) can be made
any larger.
before
matrix
【在 a******t 的大作中提到】
: Where did you find these problems? homework?
: These problems are listed at
: http://trikuare.cx/mt/archives/000718.php
|
S*******t
发帖数: 97 | 14 i think these are all basic programming problems
once i was participating ACM/ICPC, i could solve
these 3 problem in 5 min
【在 a******t 的大作中提到】
: Where did you find these problems? homework?
: These problems are listed at
: http://trikuare.cx/mt/archives/000718.php
|
a******t
发帖数: 100 | 15 If these are homework problems, the instructor is too lazy. That's the point.
【在 S*******t 的大作中提到】
: i think these are all basic programming problems
: once i was participating ACM/ICPC, i could solve
: these 3 problem in 5 min
|
S*******t
发帖数: 97 | 16 re
but maybe that guy is just interested in programming, hehe
【在 a******t 的大作中提到】
: If these are homework problems, the instructor is too lazy. That's the point.
|
