You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

60 lines
1.5 KiB

package class03;
// 本题测试链接 : https://leetcode.com/problems/largest-1-bordered-square/
public class Code03_Largest1BorderedSquare {
public static int largest1BorderedSquare(int[][] m) {
int[][] right = new int[m.length][m[0].length];
int[][] down = new int[m.length][m[0].length];
setBorderMap(m, right, down);
for (int size = Math.min(m.length, m[0].length); size != 0; size--) {
if (hasSizeOfBorder(size, right, down)) {
return size * size;
}
}
return 0;
}
public static void setBorderMap(int[][] m, int[][] right, int[][] down) {
int r = m.length;
int c = m[0].length;
if (m[r - 1][c - 1] == 1) {
right[r - 1][c - 1] = 1;
down[r - 1][c - 1] = 1;
}
for (int i = r - 2; i != -1; i--) {
if (m[i][c - 1] == 1) {
right[i][c - 1] = 1;
down[i][c - 1] = down[i + 1][c - 1] + 1;
}
}
for (int i = c - 2; i != -1; i--) {
if (m[r - 1][i] == 1) {
right[r - 1][i] = right[r - 1][i + 1] + 1;
down[r - 1][i] = 1;
}
}
for (int i = r - 2; i != -1; i--) {
for (int j = c - 2; j != -1; j--) {
if (m[i][j] == 1) {
right[i][j] = right[i][j + 1] + 1;
down[i][j] = down[i + 1][j] + 1;
}
}
}
}
public static boolean hasSizeOfBorder(int size, int[][] right, int[][] down) {
for (int i = 0; i != right.length - size + 1; i++) {
for (int j = 0; j != right[0].length - size + 1; j++) {
if (right[i][j] >= size && down[i][j] >= size && right[i + size - 1][j] >= size
&& down[i][j + size - 1] >= size) {
return true;
}
}
}
return false;
}
}