优化方法:
直接判断某个顶点是否为矩阵的左上角。通过辅助数组。该数组负责记录该顶点(包含自身)的右方,和下方1的个数。可以看作是改二维数组中又包含一个二元组。
1 | 1 | 1 | 0 |
1 | 1 | 0 | 1 |
1 | 1 | 0 | 1 |
0 | 1 | 1 | 1 |
其辅助数组为(右,下)
(3,1) | (4,1) | (1,1) | (0,0) |
(2,2) | (1,3) | (0,0) | (1,3) |
(2,1) | (1,2) | (0,0) | (1,2) |
(0,0) | (3,1) | (2,1) | (1,1) |
加了底纹的部分,(2,2)表示包括自身在内右边又2个1,向下有2个1。所以正方形的上边和左边已证明可以构成边框全为1;
(2,1)2表示向右有2个1,构成正方形的下边;(1,3)3表示向下有3个1,构成正方形的右边。所以边框全是1的最大正方形的边长长度为2。
满足这四个部分,就证明可以构成边界全为1的最大正方形。
该部分就是替换上一篇中的内层while的思路。
难点在于辅助数组generateHelpRec的建立。
1.格式为(右,下),所以建立会从右下角开始,一行一行的向上走;
2.可以先初始化最后一行,需要注意的就是数组下标不要越界;
代码如下:
1 public class case4_1 { 2 3 public static void main(String[] args) { 4 /* int arr[][] = { 5 { 1, 1, 1,1}, 6 { 1, 0, 1,1}, 7 { 1, 1, 1,1}, 8 { 1, 0, 1,0}, 9 }; 10 */ 11 int arr[][] = { 12 { 1, 0, 1, 1,1 }, 13 { 1, 1, 1, 1,1 }, 14 { 1, 1, 1, 0,1 }, 15 { 1, 1, 1, 1,1 }, 16 { 1, 1, 1, 1,1 }, 17 }; 18 generateHelpRec(arr, arr.length); 19 // printArr(rec, arr.length);//该方法主要是为了检测三维数组创建的是否正确。 20 int res = max(arr, arr.length); 21 System.out.println(res); 22 23 } 24 25 private static void printArr(int[][][] rec2, int N) { 26 for (int i = 0; i < N; i++) { 27 for (int j = 0; j < N; j++) { 28 System.out.print("(" + rec[i][j][0] + "," + rec[i][j][1] + ")" 29 + "\t"); 30 } 31 System.out.println(); 32 } 33 } 34 35 static int[][][] rec; 36 37 // 创建辅助表;三维数组 38 private static void generateHelpRec(int[][] arr, int N) { 39 rec = new int[N][N][2]; 40 // 先初始化最后一行; 41 int row = N - 1; 42 for (int j = N - 1; j >= 0; j--) { 43 int value = arr[row][j]; 44 if (value == 1) { 45 if (j == N - 1)// 右边1的个数,j增加 46 rec[row][j][0] = 1; 47 else 48 rec[row][j][0] = rec[row][j + 1][0] + 1; 49 50 rec[row][j][1] = 1; 51 } 52 53 } 54 row--; 55 // 构建三维表 56 for (int i = row; i >= 0; i--) { 57 for (int j = N - 1; j >= 0; j--) { 58 int value = arr[i][j]; 59 if (value == 1) { 60 if (j == N - 1) { 61 rec[i][j][0] = 1; 62 } else { 63 rec[i][j][0] = rec[i][j + 1][0] + 1; 64 } 65 rec[i][j][1] = rec[i + 1][j][1] + 1; 66 } 67 } 68 } 69 70 } 71 72 static int max(int[][] matrix, int N) { 73 int n = N; 74 while (n > 0) { 75 for (int i = 0; i < N; i++) { 76 if (i + n > N) 77 break; 78 l3: for (int j = 0; j < N; j++) { 79 if (j + n > N) 80 break; 81 82 if (check(i, j, n) == true) 83 return n; 84 85 } 86 } 87 88 n--; 89 90 } 91 92 return 0; 93 } 94 95 private static boolean check(int i, int j, int n) { 96 if (rec[i][j][0] >= n && rec[i][j][1] >= n && rec[i + n - 1][j][0] >= n 97 && rec[i][j + n - 1][1] >= n) 98 return true; 99 return false; 100 } 101 }
上述代码输出 :4
欢迎大家一起来交流。