大家有么有见过鸡毛菜种子？# gardening - 拈花惹草
w*x
1 楼
careercup上的一道题：
Imagine you have a square matrix, where each cell is filled with either
black or white. Design an algorithm to find the maximum subsquare such that
all four borders are filled with black pixels.
Assumption: Square is of size NxN.
This algorithm does the following:
1. Iterate through every (full) column from left to right.
2. At each (full) column (call this currentColumn), look at the subcolumns (
from biggest to smallest).
3. At each subcolumn, see if you can form a square with the subcolumn as the
left side. If so, update currentMaxSize and go to the next (full) column.
4. If N - currentColumn <= currentMaxSize, then break completely. We’ve
found the largest square possible. Why? At each column, we’re trying to
create a square with that column as the left side. The largest such square
we could possibly create is N - currentColumn. Thus, if N-currentColumn <=
currentMaxSize, then we have no need to proceed.
Time complexity: O(N^2).
Time complexity: O(N^2).
1 public static Subsquare findSquare(int[][] matrix){
2 assert(matrix.length > 0);
3 for (int row = 0; row < matrix.length; row++){
4 assert(matrix[row].length == matrix.length);
5 }
6
7 int N = matrix.length;
8
9 int currentMaxSize = 0;
10 Subsquare sq = null;
11 int col = 0;
12
13 // Iterate through each column from left to right
14 while (N - col > currentMaxSize) { // See step 4 above
15 for (int row = 0; row < matrix.length; row++){
16 // starting from the biggest
17 int size = N - Math.max(row, col);
18 while (size > currentMaxSize){
19 if (isSquare(matrix, row, col, size)){
20 currentMaxSize = size;
21 sq = new Subsquare(row, col, size);
22 break; // go to next (full) column
23 }
24 size--;
25 }
26 }
27 col++;
28 }
29 return sq;
30 }
31
32 private static boolean isSquare(int[][] matrix, int row, int col,
33 int size) {
34 // Check top and bottom border.
35 for (int j = 0; j < size; j++){
36 if (matrix[row][col+j] == 1) {
37 return false;
38 }
39 if (matrix[row+size-1][col+j] == 1){
40 return false;
41 }
42 }
43
44 // Check left and right border.
45 for (int i = 1; i < size - 1; i++){
46 if (matrix[row+i][col] == 1){
47 return false;
48 }
49 if (matrix[row+i][col+size-1] == 1){
50 return false;
51 }
52 }
53 return true;
54 }
Imagine you have a square matrix, where each cell is filled with either
black or white. Design an algorithm to find the maximum subsquare such that
all four borders are filled with black pixels.
Assumption: Square is of size NxN.
This algorithm does the following:
1. Iterate through every (full) column from left to right.
2. At each (full) column (call this currentColumn), look at the subcolumns (
from biggest to smallest).
3. At each subcolumn, see if you can form a square with the subcolumn as the
left side. If so, update currentMaxSize and go to the next (full) column.
4. If N - currentColumn <= currentMaxSize, then break completely. We’ve
found the largest square possible. Why? At each column, we’re trying to
create a square with that column as the left side. The largest such square
we could possibly create is N - currentColumn. Thus, if N-currentColumn <=
currentMaxSize, then we have no need to proceed.
Time complexity: O(N^2).
Time complexity: O(N^2).
1 public static Subsquare findSquare(int[][] matrix){
2 assert(matrix.length > 0);
3 for (int row = 0; row < matrix.length; row++){
4 assert(matrix[row].length == matrix.length);
5 }
6
7 int N = matrix.length;
8
9 int currentMaxSize = 0;
10 Subsquare sq = null;
11 int col = 0;
12
13 // Iterate through each column from left to right
14 while (N - col > currentMaxSize) { // See step 4 above
15 for (int row = 0; row < matrix.length; row++){
16 // starting from the biggest
17 int size = N - Math.max(row, col);
18 while (size > currentMaxSize){
19 if (isSquare(matrix, row, col, size)){
20 currentMaxSize = size;
21 sq = new Subsquare(row, col, size);
22 break; // go to next (full) column
23 }
24 size--;
25 }
26 }
27 col++;
28 }
29 return sq;
30 }
31
32 private static boolean isSquare(int[][] matrix, int row, int col,
33 int size) {
34 // Check top and bottom border.
35 for (int j = 0; j < size; j++){
36 if (matrix[row][col+j] == 1) {
37 return false;
38 }
39 if (matrix[row+size-1][col+j] == 1){
40 return false;
41 }
42 }
43
44 // Check left and right border.
45 for (int i = 1; i < size - 1; i++){
46 if (matrix[row+i][col] == 1){
47 return false;
48 }
49 if (matrix[row+i][col+size-1] == 1){
50 return false;
51 }
52 }
53 return true;
54 }
