-
Notifications
You must be signed in to change notification settings - Fork 38
Expand file tree
/
Copy pathSolution.java
More file actions
87 lines (83 loc) · 2.95 KB
/
Copy pathSolution.java
File metadata and controls
87 lines (83 loc) · 2.95 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
* Time : O(m * n) ; Space: O(m * n)
* @tag : Dynamic Programming
* @by : Steven Cooks
* @date: Sep 24, 2015
***************************************************************************
* Description:
*
* Given a 2D binary matrix filled with 0's and 1's, find the largest square
* containing all 1's and return its area.
*
* For example, given the following matrix:
* 1 0 1 0 0
* 1 0 1 1 1
* 1 1 1 1 1
* 1 0 0 1 0
*
* Return 4.
*
***************************************************************************
* {@link https://leetcode.com/problems/maximal-square/ }
*/
package _221_MaximalSquare;
/** see test {@link _221_MaximalSquare.SolutionTest } */
public class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int res = 0;
int rows = matrix.length;
int cols = matrix[0].length;
// f[i][j] = min(number of continuous 1s along x-direction from (i,k),
// number of continuous 1s along y-direction)
int[][] f = new int[rows + 1][cols + 1];
for (int i = rows - 1; i >= 0; i--) {
for (int j = cols - 1; j >= 0; j--) {
if (matrix[i][j] == '1') {
f[i][j] = 1 + Math.min(f[i + 1][j + 1], Math.min(f[i][j + 1], f[i + 1][j]));
res = Math.max(res, f[i][j]);
}
}
}
return res * res;
}
public int maximalSquare2(char[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int res = 0;
int rows = matrix.length;
int cols = matrix[0].length;
int[][] x = new int[rows + 1][cols + 1]; // how many continuous 1s along
// row i from column j
int[][] y = new int[rows + 1][cols + 1]; // how many continuous 1s from
// (i,j) along direction to
// bottom
int[][] f = new int[rows + 1][cols + 1];
for (int i = rows; i >= 0; i--) {
for (int j = cols; j >= 0; j--) {
int area = 0;
if (i == rows && j == cols) {
area = 0;
} else if (i == rows) {
area = 0;
} else if (j == cols) {
area = 0;
} else {
if (matrix[i][j] == '1') {
int len = (int) Math.min(Math.sqrt(f[i + 1][j + 1]),
Math.min(x[i][j + 1], y[i + 1][j]));
area = (len + 1) * (len + 1);
x[i][j] = 1 + x[i][j + 1];
y[i][j] = 1 + y[i + 1][j];
}
}
res = Math.max(res, area);
f[i][j] = area;
}
}
return res;
}
}