二叉树的中序遍历-力扣94 中序遍历
Gaein nidb Lv5

题干

力扣-最大正方形

题干详见 LeetCode ,图片过多不在此赘述。

暴力

思路

暴力算嘛,计算每一个最大的正方形的边长并存储,遍历一轮。

代码

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
public int MaximalSquare(char[][] matrix)
{
var maxSide = 0;

// 判空
if (matrix is null || matrix.Length == 0 || matrix[0].Length == 0)
return 0;

var rows = matrix.Length;
var columns = matrix[0].Length;

for (var i = 0; i < rows; i++)
{
for (var j = 0; j < columns; j++)
{
if (matrix[i][j] == '1')
{
// 遇到一个 1 作为正方形的左上角
maxSide = maxSide > 1 ? maxSide : 1;

// 计算可能的最大正方形边长
var currentMaxSide = rows - i > columns - j ? columns - j : rows - i;
for (var k = 1; k < currentMaxSide; k++)
{
// 判断新增的一行一列是否均为 1
var flag = true;
if (matrix[i + k][j + k] == '0')
break;

for (var m = 0; m < k; m++)
{
if (matrix[i + k][j + m] == '0' || matrix[i + m][j + k] == '0')
{
flag = false;
break;
}
}

if (flag)
{
maxSide = maxSide > k + 1 ? maxSide : k + 1;
}
else
{
break;
}
}
}
}
}

return maxSide * maxSide;
}